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