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

The target fold is encoded by means of the following facts:

• a fact length(n), where n is a positive integer;

• n facts of the form fold(i,x_i,y_i), where i = 1,...,n and (x_i,y_i) is a point in a 2D Cartesian plane.

A fact of the form time(t) is used for specifying the number of moves in the output sequence.

Output format

A sequence of t moves leading the initial straight line fold into the fold assigned as input. Such a sequence should be encoded by means of predicate pivot/3, where the first argument is a time step, the second argument is the ID of a point of the fold, and the last argument is either clock or anticlock.

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