Navigation of a mobile robot formulated in terms of discrete optimization problems

Harukazu Igarashi, Kiyoshi Ioi

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)


The problem of navigation of an autonomous mobile robot has a great variety of solutions, depending on the premise conditions regarding the properties of the robot, the surrounding environment, and the user specifications. In support of a navigation scheme that can cope flexibly with this variety, this paper proposes a method that formulates the problem in terms of discrete optimization problems. In the proposed method, the problem of robot position/posture estimation from map and sensor data and the problem of deciding the action at each instant are formulated as separate discrete optimization problems. In the former, our approach is an approximation of the Markov localization algorithm. The proposed method is then applied to a navigation problem in a known environment with fixed obstacles, and the effectiveness and feasibility of the method are verified by simulation results.

Original languageEnglish
Pages (from-to)59-68
Number of pages10
JournalSystems and Computers in Japan
Issue number6
Publication statusPublished - 2003 Jun 15
Externally publishedYes


  • Autonomous mobile robot
  • Discrete optimization problem
  • Markov localization
  • Navigation
  • Trajectory planning

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Information Systems
  • Hardware and Architecture
  • Computational Theory and Mathematics


Dive into the research topics of 'Navigation of a mobile robot formulated in terms of discrete optimization problems'. Together they form a unique fingerprint.

Cite this