Dealing with Geometric Constraints in Game-Theoretic Planning

Abstract

Tracking a partially predictable moving object in a workspace cluttered by obstacles is a challenging combination of two planning problems. The planner must take into account on the one hand the visibility and motion constraints imposed by the obstacles and on the other hand the uncertainties in both the robot's position and the future trajectory of the target. Game theory is proposed as an appropriate framework to solve this twofold problem. At each time step, a probability distribution models the positioning uncertainties of the robot and the target and a utility function represents the reward associated with the possible goal states of the motion decision problem. This approach allows the simple modeling of different tracking strategies, one of which has been implemented and tested successfully with two mobile robots. By considering simultaneously target visibility a nd position uncertainty, the tracking robot can take advantage of landmarks scattered in the workspace to better localize itself so as to better track the target afterward. Future extensions seem possible in order to introduce useful symbolic inferences within the game -th eor et ic framework.