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). 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.

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.

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

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

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)

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