We present robot games, and we give the simplest definitions for which decidability is not known.

1. Definition. Let U,V ⊆ ℤ² be two finite sets of two-dimensional integer vectors. A robot game is played in rounds from an initial configuration x₀ ∈ ℤ² as follows. In each round, player 2 chooses a vector v ∈ V, then player 1 chooses a vector u ∈ U, and the configuration in the next round is x+v+u where x is the configuration in the current round. The objective of player 1 is to reach the configuration (0,0). r50mm

(55,40)(0,0)

(5,-10)(10,0)5 [AHnb=0, linegray=.8](0,0)(0,50)

(0,-5)(0,10)5 [AHnb=0, linegray=.8](0,0)(50,0)

(35,-10)(35,40) (0,25)(50,25)

Nh=2, Nw=2 [Nmarks=n, Nmr=0, ExtNL=y, NLdist=1, NLangle=270](q)(5,-5)(−3,−3) [Nmarks=n, Nmr=2](r)(15,15) [Nmarks=n, Nmr=2](s)(25,-5) [Nmarks=n, Nh=1, Nw=1, Nmr=2, fillgray=0, NLdist=5, NLangle=32](t)(35,25)(0,0)

[ELpos=50, ELside=l, ELdist=.5, curvedepth=0](q,r) [ELpos=50, ELside=l, ELdist=.5, curvedepth=0](q,s) [ELpos=50, ELside=l, ELdist=.5, curvedepth=0](r,t) [ELpos=50, ELside=l, ELdist=.5, curvedepth=0](s,t)

A strategy for player 1 is a function σ: ℤ² → U and a strategy for player 2 is a function π: ℤ² → V. The play according to σ and π from initial configuration x₀ is the infinite sequence x₀ x₁ … such that for all i≥ 0, we have x_i+1 = x_i + v + u where v = π(x_i) and u = σ(x_i + v).

A configuration x₀ is winning for player 1 if there exists a strategy σ such that for all strategies π, in the resulting play from x₀ there exists i ≥ 0 such that x_i = (0,0).

2. Example. Let U = {(1,3),(2,1)} and V={(2,0),(1,2)}. The initial configuration (−3,−3) is winning for player 1. The set of winning configurations for player 1 is {(−3k,−3k) ∣ k ≥ 0}. Note that the set of winning configurations is closed under sum (i.e., x+y is a winning configuration if x and y are winning configurations).

3. Decision problem. Given an initial configuration x₀ ∈ ℤ² and two finite sets U,V ⊆ ℤ², the problem is to decide whether x₀ is a winning configuration in the robot game defined by U,V. Whether this problem is decidable and what is its complexity are open questions.

The problem is undecidable if the game is played on a graph with states of player 1 and states of player 2, with ℤ² or ℕ² as the vector space (as in games on VASS, vector-addition systems with states) [1, 2].

The one-player version of robot games (i.e., where V={(0,0)}) is decidable in polynomial time by a reduction to linear programming. The robot games defined in one dimension (with U,V ⊆ ℤ and x₀ ∈ ℤ) are also decidable.

4. Extension. Extensions can be considered in several directions:

• Robot games in dimension d ≥ 3.
• Reachability objectives can be defined by a (possibly upward-closed) set of target configurations.
• Players have internal states (e.g., for player 1 the set U of available moves may change as the game is played, according to some finite-state machine).
• And many others.

5. Partial results.

• The problem is undecidable in dimension d ≥ 9, and in dimension d ≥ 3 if player 1 has internal states [3]. In general, robot games in dimension d and internal states for player 1 can be reduced to games in dimension d+6 and no states [3].

References

[1]

Parosh Aziz Abdulla, Ahmed Bouajjani, and Julien d’Orso. Deciding monotonic games. In Proc. of CSL: Computer Science Logic, LNCS 2803, pages 1–14. Springer, 2003.

[2]

T. Brázdil, P. Jancar, and A. Kucera. Reachability games on extended vector addition systems with states. In Proc. of ICALP, LNCS 6199, pages 478–489. Springer, 2010.

[3]

Y. Velner. Personal communication, June 2011.

Contact

This document was translated from L^AT_EX by H^EV^EA.