Differences between revisions 1 and 10 (spanning 9 versions)

Reverse Folding

Contents

Reverse Folding

Problem Description

This is a simplification of an important Biological problem. A string (e.g., representing a protein) composed of N consecutive elements (defined by the predicate length(N)) at a fixed unitary distance lays on a 2D (cartesian) plane. Admissible angles are 0 (straight line), -90 (left turn) and +90 (right turn). We refer to each placement of the string as a folding. A folding is represented by a predicate fold(I,X,Y) where I in {1,...,N} is the I-th element of the string, and (X,Y) are its coordinates in the plane. You can assume X and Y in {0,...,2N}.

A pivot move is defined by selecting an element i in {2,...,N-1} and its effect is to turn clockwise or counter-clockwise of 90 degrees the part of the string related to the elements i+1,...,N. A move at time t is represented by pivot(t,i,clock) or pivot(t,i,anticlock). Exactly one move occurs at a time t. Different elements must occupy different positions at any of the discrete time points considered: that is, each intermediate layout of the string must not have overlapping points in the 2D plane.

The goal is to find (if it exists) a sequence of T moves (T is defined by the predicate time(T)) such that lead the initial straight line fold

fold(1,N,N). fold(2,N,N+1). fold(2,N,N+2). ... fold(N,N,2N-1).

into the fold assigned as input.

Ideas on modeling with variants of ASP can be found in:
A. Dovier, A. Formisano, E. Pontelli.
Perspectives on Logic-based Approaches for Reasoning About Actions and Change.
To appear in LNCS 6565, Essay in honour of Michael Gelfond
(paper draft available on line)

Predicates

Input: fold/3, length/1, time/1
Output: pivot/3

Input format

Output format

Example(s)

Assume the input is:

fold(1,9,9). 
fold(2,9,10). 
fold(3,9,11). 
fold(4,10,11). 
fold(5,11,11). 
fold(6,11,10). 
fold(7,11,9). 
fold(8,10,9). 
fold(9,10,10). 

length(9). 
time(4).

This means that the the final form of the protein is

   _ _
  |   | 
  | |_|

Starting from the straight line fold, it is possible to reach that folding with the application of the following pivot moves (which is the expected output from the system):

pivot(1,3,clock). 
pivot(2,5,clock). 
pivot(3,8,clock). 
pivot(4,7,clock).

Effects of pivot moves

 | 
 | 
 | 
 | 
 | 
 |    _ _ _ _ _ _    _ _     _ _     _ _ 
 |   |              |   |   |   |   |   | 
 |   |              |   |   |   |   | |_| 
                        |      _| 
                        |

Notes and Updates

Different elements must occupy different positions only at discrete time points. The case in which elements overlap during rotation from one time point to another is not to be considered.

Problem peculiarities

Type: Search/NP Competition: M&S only

Author(s)

Author: Agostino Dovier
- Affiliation: University of Udine, Italy
Author: Andrea Formisano
- Affiliation: University of Perugia, Italy
Author: Enrico Pontelli
- Affiliation: New Mexico State University, USA

ASP Competition 2011: FinalProblemDescriptions/ReverseFolding (last edited 2011-02-07 19:49:50 by MarioAlviano)

-  ⇤ ← Revision 1 as of 2011-01-19 10:02:09 → 
  Size: 2366
  Editor: CarmenSantoro
  Comment:
+   ← Revision 10 as of 2011-02-03 16:49:49 → ⇥
  Size: 3279
  Editor: GiovambattistaIanni
  Comment:
-Deletions are marked like this.
+Additions are marked like this.
 Line 7:
-* Input predicates: fold/3, length/1, time/1
+This is a simplification of an important Biological problem. A string (e.g., representing a protein) composed of N consecutive elements (defined by the predicate {{{length(N)}}}) at a fixed unitary distance lays on a 2D (cartesian) plane. Admissible angles are 0 (straight line), -90 (left turn) and +90 (right turn). 
We refer to each placement of the string as a folding. A folding is represented by a predicate {{{fold(I,X,Y)}}} where I in {1,...,N} is the I-th element of the string, and {{{(X,Y)}}} are its coordinates in the plane. You can assume X and Y in {0,...,2N}.
-Line 9:
+Line 10:
-* Output predicates: pivot/3

This is a simplification of an important Biological problem. A string (e.g., representing a protein) composed of N consecutive elements (defined by the predicate length(N)) at a fixed unitary distance lays on a 2D (cartesian) plane. Admissible angles are 0 (straight line), .90. (left turn) and +90. (right turn). Different elements must occupy different positions. We refer to each placement of the string as a folding. A folding is represented by a predicate fold(I,X,Y) where I in {1,...,N} is the Ith element of the string, and (X,Y) are its coordinates in the plane. You can assume X and Y in {0,...,2N}.

A pivot move is defined by selecting an element i in {2,...,N-1} and its effect is to turn clockwise or counter-clockwise of 90 degrees the part of the string related to the elements i+1,...,N.

A move at time t is represented by pivot(t,i,clock) or pivot(t,i,anticlock). Exactly one move occurs at a time t.
+A pivot move is defined by selecting an element i in {2,...,N-1} and its effect is to turn clockwise or counter-clockwise of 90 degrees the part of the string related to the elements i+1,...,N. A move at time t is represented by {{{pivot(t,i,clock)}}} or {{{pivot(t,i,anticlock)}}}. Exactly one move occurs at a time t.
Different elements must occupy different positions at any of the discrete time points considered: that is, each intermediate layout of the string must not have overlapping points in the 2D plane.
-Line 18:
+Line 14:
-fold(1,N,N). fold(2,N,N+1). fold(2,N,N+2). ... fold(N,N,2N-1).
+{{{fold(1,N,N). fold(2,N,N+1). fold(2,N,N+2). ... fold(N,N,2N-1).}}}
-Line 21:
+Line 19:
-Assume the input is:

fold(1,9,9).
fold(2,9,10).
fold(3,9,11).
fold(4,10,11).
fold(5,11,11).
fold(6,11,10).
fold(7,11,9).
fold(8,10,9).
fold(9,10,10).

length(9).
time(4).
+Ideas on modeling with variants of ASP can be found in: <<BR>>
A. Dovier, A. Formisano, E. Pontelli. <<BR>>
Perspectives on Logic-based Approaches for Reasoning About Actions and Change. <<BR>>
To appear in LNCS 6565, Essay in honour of Michael Gelfond <<BR>>
(paper draft available on line)
-Line 37:
+Line 26:
+== Predicates ==

 * '''Input''': {{{fold/3, length/1, time/1}}}

 * '''Output''': {{{pivot/3}}}

== Input format ==

== Output format ==

== Example(s) ==

Assume the input is:
{{{
fold(1,9,9). 
fold(2,9,10). 
fold(3,9,11). 
fold(4,10,11). 
fold(5,11,11). 
fold(6,11,10). 
fold(7,11,9). 
fold(8,10,9). 
fold(9,10,10). 

length(9). 
time(4). 
}}}
-Line 38:
+Line 54:
+{{{
-Line 40:
+Line 56:
   |   |
-Line 42:
+Line 58:
+}}}
-Line 47:
+Line 63:
+{{{
pivot(1,3,clock). 
pivot(2,5,clock). 
pivot(3,8,clock). 
pivot(4,7,clock). 
}}}
Effects of pivot moves
{{{
 | 
 | 
 | 
 | 
 | 
 |    _ _ _ _ _ _    _ _     _ _     _ _ 
 |   |              |   |   |   |   |   | 
 |   |              |   |   |   |   | |_| 
                        |      _| 
                        | 
}}}
-Line 48:
+Line 83:
-pivot(1,3,clock).
pivot(2,5,clock).
pivot(3,8,clock).
pivot(4,7,clock).
+== Notes and Updates ==
-Line 53:
+Line 85:
-Effects of pivot moves
+Different elements must occupy different positions only at discrete time points. 
The case in which elements overlap during rotation from one time point to another is not to be considered.
-Line 55:
+Line 88:
- |
 |
 |
 |
 |
 |    _ _ _ _ _ _    _ _     _ _     _ _
 |   |              |   |   |   |   |   |
 |   |              |   |   |   |   | |_|
                        |      _|
                        |
+== Problem peculiarities ==
-Line 66:
+Line 90:
-Ideas on modeling with variants of ASP can be found in:
A. Dovier, A. Formisano, E. Pontelli.
Perspectives on Logic-based Approaches for Reasoning About Actions and Change.
To appear in LNCS 6565, Essay in honour of Michael Gelfond
(paper draft available on line)
+'''Type''': Search/NP
'''Competition''': M&S only

== Author(s) ==
 * Author:  Agostino Dovier 	
   * Affiliation: University of Udine, Italy
 * Author: Andrea Formisano 	
   * Affiliation: University of Perugia, Italy
 * Author: Enrico Pontelli	
   * Affiliation: New Mexico State University, USA

ASP Competition 2011

Quick Links

Search Wiki

Page Tools