welcome: please sign in

Revision 1 as of 2012-11-08 11:23:41

Clear message
location: RicochetRobot

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

Example(s)

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

Problem Peculiarities

Type: Search Competition: Both

Notes and Updates

Author(s)

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