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

Rigoberto Lopez-Padilla, Rafael Murrieta-Cid, Israel Becerra, Guillermo Laguna, Steven M. LaValle

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish (US)
Pages (from-to)211-250
Number of pages40
JournalJournal of Intelligent and Robotic Systems: Theory and Applications
Issue number1-2
StatePublished - Jan 1 2018


  • Combinatorial filters
  • Environment constraints
  • Feedback motion strategies
  • Optimal navigation
  • Underactuated system

ASJC Scopus subject areas

  • Software
  • Control and Systems Engineering
  • Mechanical Engineering
  • Industrial and Manufacturing Engineering
  • Electrical and Electronic Engineering
  • Artificial Intelligence


Dive into the research topics of 'Optimal Navigation for a Differential Drive Disc Robot: A Game Against the Polygonal Environment'. Together they form a unique fingerprint.

Cite this