Multi-Objective Kinodynamic Motion Planning with Asymptotic Pareto Optimality
Robotics
Summary
The authors tackled the problem of planning movements for systems that must follow certain physics or rules while considering multiple goals at once. They studied three cases: prioritizing goals in order, minimizing one goal while keeping others within limits, and finding all best trade-offs among goals. They showed that common methods don't work well for continuous systems with guarantees, so they created a new method based on an existing algorithm called SST. Their approach keeps several best options instead of one, resulting in three new algorithms, each designed for one of the goal types. They proved these algorithms are correct and tested them successfully.
Authors
Yusif Razzaq, Anne Theurkauf, Nisar Ahmed, Morteza Lahijanian
Abstract
In this paper, we address the challenge of multi-objective motion planning for systems under kinodynamic constraints. We consider three problem classes: (i) lexicographic optimization, in which objectives are minimized according to a strict priority ordering, (ii) constrained optimization, in which a primary objective is minimized subject to bounds on the remaining costs, and (iii) Pareto front optimization, in which the goal is to approximate the full set of optimal trade-offs among competing objectives. We first show that established cost scalarization methods for multi-objective problems cannot be extended to continuous-domain systems with correctness guarantees. Then, we propose a unified algorithmic framework built upon the Stable Sparse-RRT (SST) algorithm, in which the single representative maintained at each witness neighborhood is replaced by a representative set of locally Pareto-optimal nodes. This structure gives rise to three distinct algorithms: lexSST for lexicographic minimization, coSST for constrained optimization, and poSST for Pareto-front approximation. We provide theoretical guarantees for the completeness and optimality of our algorithms and demonstrate their effectiveness through extensive empirical evaluations.