= Ricochet Robots =


== Problem Description ==

Ricochet Robots is a board game played on an NxN
grid with predefined horizontal and vertical barriers between some of
the adjacent board positions. Board positions may be occupied by robots
of distinct colors, and the goal is to guide some robot to a target
position via a sequence of robot moves. A robot can move horizontally
or vertically from its current position; once a direction is chosen,
the robot moves in that direction until encountering an obstacle, i.e.
a barrier, another robot, or the edge of the board, precluding that the
robot moves further. While the original objective of the game is to
achieve the goal with a minimum number of moves, we consider a decision
version, viz. whether the goal can be established via some sequence (a
plan) consisting of a predefined number of robot moves. (More details
and insights about Ricochet Robots can, for instance, be found in [1].)

== Predicates ==

 * '''Input''': {{{dim/1, pos/3, barrier/3, target/3, length/1}}}

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

== Input format ==

The dimensions of a quadratic board are given by {{{dim/1}}},
e.g. {{{dim(1). dim(2). dim(3).}}} for a 3x3 board. The start positions of
robots are given by {{{pos/3}}, e.g. {{{pos(red,2,3).}}} states that a red robot
starts at position (2,3). The locations and orientations of barriers
are given by {{{barrier/3}}}, e.g. {{{barrier(4,3,east).}}} states that there is
a barrier between position (4,3) and position (5,3); note that the same
barrier is also represented by {{{barrier(5,3,west).}}}, and a problem
instance may include either or both representations. In any atom of the
form {{{barrier(x,y,d)}}}, a value "east", "west", "south", or "north" of d
indicates a neighboring position (x+1,y), (x-1,y), (x,y+1), or (x,y-1),
respectively, of position (x,y) on the board. The color and location of
a target are given by {{{target/3}}}, e.g. {{{target(red,4,3).}}} states that the
red robot should be guided to position (4,3). The number of moves in a
plan is given by {{{length/1}}}, e.g. {{{length(3).}}} for a plan of three moves.
A problem instance contains exactly one fact of the form {{{length(l).}}}
and exactly one fact of the form {{{target(c,x,y).}}}; the color name c
appears also in some fact of the form {{{pos(c,x',y').}}}, and there is
exactly one fact {{{pos(c',x',y').}}} per color name c' such that no
distinct colors share the same start position (x',y').

== Output format ==
The predicate {{{go/3}}} represents the moves of a plan. Atoms
are of the form {{{go(c,d,i)}}}, where c is a color name, d is a direction,
i.e. "east", "west", "south", or "north", and i is a sequence number.

For example, 
{{{ 
go(blue,north,1). go(blue,east,2). go(red,east,3). 
}}}
represents a plan of length 3 according to which the blue robot moves
northwards and then eastwards before the red robot moves eastwards.
Exactly one atom {{{go(c,d,i)}}} must hold for each positive integer i up
to l given by {{{length(l).}}}, and c must be a color appearing in a fact
of the form {{{pos(c,x,y).}}}


== Example(s) ==

The following example (depicted below):

{{{
dim(1). dim(2). dim(3).
dim(4). dim(5).

pos(red,   1,1). pos(blue,  1,5).
pos(green, 5,1). pos(yellow,5,5).

barrier(1,2,south). barrier(4,3,east).
barrier(2,5,east).

target(red,4,4).

length(5).

}}}

encodes a 5x5 board with the red robot (R) in the
upper-left, the green robot in the upper-right, the blue robot (B) in
the lower-left and the yellow (Y) robot in the lower-right corner.
The Target (T) is placed in cell (4,4) is colored red. There are 3
barriers (#) at cell (1,2) heading south, at cell (4,3) heading east
and at cell (2,5) heading east.

{{{
###########
#R . . . G#
#      	  #
#. . . . .#
##        #
#. . . .#.#
#         #
#. . . T .#
#         #
#B .#. . Y#
###########
}}}

There exist 11 minimal plans (5 moves) to lead the red robot to the target:

Answer: 1
{{{
go(red,east,1). go(red,south,2). go(blue,north,3). go(blue,east,4). go(red,north,5). 
}}}
Answer: 2
{{{
go(red,east,1). go(blue,north,2). go(red,south,3). go(blue,east,4). go(red,north,5). 
}}}
Answer: 3
{{{
go(red,east,1). go(yellow,west,2). go(green,south,3). go(yellow,east,4). go(red,south,5). 
}}}
Answer: 4
{{{
go(red,east,1). go(yellow,west,2). go(green,south,3). go(green,west,4). go(red,south,5). 
}}}
Answer: 5
{{{
go(red,east,1). go(blue,north,2). go(blue,east,3). go(blue,south,4). go(red,south,5). 
Answer: 6
{{{
go(blue,north,1). go(red,east,2). go(blue,east,3). go(blue,south,4). go(red,south,5). 
}}}
Answer: 7
{{{
go(blue,north,1). go(red,east,2). go(red,south,3). go(blue,east,4). go(red,north,5). 
}}}
Answer: 8
{{{
go(yellow,west,1). go(red,east,2). go(green,south,3). go(green,west,4). go(red,south,5). 
}}}
Answer: 9
{{{
go(yellow,west,1). go(red,east,2). go(green,south,3). go(yellow,east,4). go(red,south,5). 
}}}
Answer: 10
{{{
go(blue,north,1). go(blue,east,2). go(blue,south,3). go(red,east,4). go(red,south,5). 
}}}
Answer: 11
{{{
go(blue,north,1). go(blue,east,2). go(red,east,3). go(blue,south,4). go(red,south,5). 
}}}


== Problem Peculiarities ==

'''Type''': Search
'''Competition''': Both


== Notes and Updates ==



== Author(s) ==
 * Author: Julius Höfler, Martin Gebser, Philipp Obermeier, Roland Kaminski, Torsten Schaub
  * Affiliation: University of Potsdam, Germany

== References ==

[1] Ricochet Robots - A Case Study for Human Complex Problem Solving. N. Butko, K. A. Lehmann, and V. Ramenzoni, Project Thesis from the Complex Systems Summer School. Santa Fe Institute, 2005. PDF link: http://www-pr.informatik.uni-tuebingen.de/mitarbeiter/katharinazweig/downloads/ButkoLehmannRamenzoni.pdf