Multi-Objective Combinatorial Optimization Using the Cell Mapping Algorithm for Mobile Robots Trajectory Planning

Abstract

The use of optimal control theory for motion planning is a challenging task. Cell mapping offers a way to formulate combinatorial optimization problems, allowing the inclusion of complex cost functions as well as multi-objective optimization problems. This paper presents a suboptimal solution for a trajectory planning problem in a workspace with obstacles, for a differential drive mobile robot. This method relies on the use of any linearization technique that allows the regularization of the combinatorial optimization problem. We explore some classical problems in optimal control, i.e., distance, control effort, and navigation time), as well as the multi-objective optimization problem (MOP). We also performed a comparison with two classical path planning algorithms, namely A∗ and RRT∗, to validate the proposed method when the multi-objective optimization problem includes distance in the cost function, achieving a compromise of less than 2% for the worst-case scenario for our case study.