Motion planning for robots is a general problem which requires the knowledge of many fields (robotics, control theory, computation theory, mathematics). The topic of this paper is a game-theoretical approach to this problem. The advantage of this solution is that multiple motion planning problems with different properties can be combined easily (e.g. multiple robots with sensing uncertainty).
This paper will start with the theoretical foundation of motion planning, and with the methods used to describe given strategies (forward projection and performance preimage). Then the simplest form of motion planning will be discussed, followed by some possible extensions, for example motion planning with sensing and controlling uncertainty, or motion planning with environment uncertainty. At last, the problem of multi-agent motion planning will be presented through three different types of methodologies: the case of a fixed roadmap, the case of independent roadmaps, and the unconstrained motion planning.