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

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.