A Plan language for Sokoban

In classical computing the first step before a software application can be realized an algorithm has to identified which can solve the problem. In case of Artificial Intelligence no dedicated AI algorithm are available and the given one for example A* graph search are not working very well. The best practice method in solving AI problem is to invent a plan language as the first step. A plan notation is a human machine interface and can be used for plan recognition and plan execution as well.

The example game, Sokoban, is an easy one. It contains of a single robot plus a single box which can be pushed by the robot. Obstacles in the maze are not available. A possible planning language contains of the following syntax:

1. moveto (100,100)
2. pushto (100,200)
3. pushto (200,200)
4. moveto (0,0)

The plan contains of a sequence of single steps which can be either moveto or pushto. Additional the pixel coordinates are given. Such a plan is stored in a Python list, the first parameter is the actionname and the second one the point-coordinate. The surprising information is, that apart from this plan notation no further algorithms are needed to solve Sokoban, because the plan notation itself is powerful enought. We can do with the plan two different things. The first one is, to observe a human player and write down which plan he executes. This is equal to a formalized game log recording. And second, the given plan can be used as a subgoal list for replay the actions of the robot.

The plan can't executed like a normal computer program. Because the information are vague and they are not fit exactly to the given map. But each step in the plan can be interpreted as a subgoal which can guide the solver. If we now, that the robot should go to (100,100) then a solver can figure out how to do this task exactly. In case of Sokoban the plan notation is not very complicated. It contains of two single commands plus a coordinate information. Different domains will require a different plan notation. What we can say for sure is, that any game can be solved much easier if a plan notation is available, for example Lemmings, Mario AI, Starcraft or Pong.

The plan notation is a step inbetween a teleoperated robot which is controlled by the human and an autonomous AI which is working without a human. It helps to make this transition possible:

1. Teleoperated robot

2. Teleoperated robot who regonizes plan from humans

3. teleoperated robot who can execute plans partly

4. Fully autonomous robot

A plan guided teleoperating system is located between a vanilla human controlled system and a fully autonomous robot.