Optimal Navigation for a Differential Drive Disc Robot: A Game Against the Polygonal Environment

This paper considers the problem of globally optimal navigation with respect to minimizing Euclidean distance traveled by a disc-shaped, differential-drive robot (DDR) to reach a landmark. The robot is equipped with a gap sensor, which indicates depth discontinuities and allows the robot to move toward them. In this work we assume that a topological representation of the environment called GNT has already been built, and that the landmark has been encoded in the GNT. A motion strategy is presented that optimally navigates the robot to any landmark in the environment, without the need of using a previously known geometric map of the environment. To our knowledge this is the first time that the shortest path for a DDR (underactuated system) is found in the presence of obstacle constraints without knowing the complete geometric representation of the environment. The robot’s planner or navigation strategy is modeled as a Moore Finite State Machine (FSM). This FSM includes a sensor-feedback motion policy. The motion policy is based on the paradigm of avoiding the state estimation to carry out two consecutive mappings, that is, from observation to state and then from state to control, but instead of that, there is a direct mapping from observation to control. Optimality is proved and the method is illustrated in simulation.