Multi-Objective Kinodynamic Motion Planning with Asymptotic Pareto Optimality

• URL: http://arxiv.org/abs/2607.15508v1
• Date: Thu, 16 Jul 2026 23:32:59 GMT
• Title: Multi-Objective Kinodynamic Motion Planning with Asymptotic Pareto Optimality
• Abstract summary: We address the challenge of multi-objective motion planning for systems under kinodynamic constraints.<n>We propose a unified algorithmic framework built upon the Stable Sparse-RRT (SST) algorithm.
• Score: 8.518351216651062
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• Multi-Objective Bayesian Optimization via Adaptive \varepsilon-Constraints Decomposition [19.76344805798142]
  We propose textitSTAGE-BO, Sequential Targeting Adaptive Gap-Filling $varepsilon$-Constraint Bayesian Optimization.<n>By analyzing the coverage of the approximate Pareto front, our method identifies the largest geometric gaps.<n>These gaps are then used as constraints, which transforms the problem into a sequence of inequality-constrained subproblems.
  arXiv  Detail & Related papers  (2026-04-17T11:24:56Z)
• Bounded Rationality for LLMs: Satisficing Alignment at Inference-Time [52.230936493691985]
  We propose SITAlign, an inference framework that addresses the multifaceted nature of alignment by maximizing a primary objective while satisfying threshold-based constraints on secondary criteria.<n>We provide theoretical insights by deriving sub-optimality bounds of our satisficing based inference alignment approach.
  arXiv  Detail & Related papers  (2025-05-29T17:56:05Z)
• Efficient First-Order Optimization on the Pareto Set for Multi-Objective Learning under Preference Guidance [41.24995294376129]
  Multi-objective learning under user-specified preference is common in real-world problems such as multi-lingual speech recognition under fairness.<n>We frame such a problem as a semivectorial bilevel optimization problem, whose goal is to optimize a pre-defined preference function.<n>We propose algorithms to solve the reformulated single-level problem, and establish its convergence guarantees.
  arXiv  Detail & Related papers  (2025-03-26T16:41:07Z)
• Scalable Min-Max Optimization via Primal-Dual Exact Pareto Optimization [66.51747366239299]
  We propose a smooth variant of the min-max problem based on the augmented Lagrangian.<n>The proposed algorithm scales better with the number of objectives than subgradient-based strategies.
  arXiv  Detail & Related papers  (2025-03-16T11:05:51Z)
• Optimization on Pareto sets: On a theory of multi-objective optimization [7.907376287850398]
  In multi-objective optimization, a single decision vector must balance the trade-offs between many objectives. We consider a more practically significant optimization problem, where the goal is to optimize a constrained set.
  arXiv  Detail & Related papers  (2023-08-04T05:55:52Z)
• Nesterov Meets Optimism: Rate-Optimal Separable Minimax Optimization [108.35402316802765]
  We propose a new first-order optimization algorithm -- AcceleratedGradient-OptimisticGradient (AG-OG) Ascent. We show that AG-OG achieves the optimal convergence rate (up to a constant) for a variety of settings. We extend our algorithm to extend the setting and achieve the optimal convergence rate in both bi-SC-SC and bi-C-SC settings.
  arXiv  Detail & Related papers  (2022-10-31T17:59:29Z)
• Algorithm for Constrained Markov Decision Process with Linear Convergence [55.41644538483948]
  An agent aims to maximize the expected accumulated discounted reward subject to multiple constraints on its costs. A new dual approach is proposed with the integration of two ingredients: entropy regularized policy and Vaidya's dual. The proposed approach is shown to converge (with linear rate) to the global optimum.
  arXiv  Detail & Related papers  (2022-06-03T16:26:38Z)
• Faster Algorithm and Sharper Analysis for Constrained Markov Decision Process [56.55075925645864]
  The problem of constrained decision process (CMDP) is investigated, where an agent aims to maximize the expected accumulated discounted reward subject to multiple constraints. A new utilities-dual convex approach is proposed with novel integration of three ingredients: regularized policy, dual regularizer, and Nesterov's gradient descent dual. This is the first demonstration that nonconcave CMDP problems can attain the lower bound of $mathcal O (1/epsilon)$ for all complexity optimization subject to convex constraints.
  arXiv  Detail & Related papers  (2021-10-20T02:57:21Z)
• On Constraints in First-Order Optimization: A View from Non-Smooth Dynamical Systems [99.59934203759754]
  We introduce a class of first-order methods for smooth constrained optimization. Two distinctive features of our approach are that projections or optimizations over the entire feasible set are avoided. The resulting algorithmic procedure is simple to implement even when constraints are nonlinear.
  arXiv  Detail & Related papers  (2021-07-17T11:45:13Z)
• Trilevel and Multilevel Optimization using Monotone Operator Theory [5.927983571004003]
  We consider a trilevel optimization problem, where the objective of the two lower layers consists of a sum of a smooth and a non-smooth term. We present a natural first-order algorithm and analyze its convergence and rates of convergence in several regimes of parameters.
  arXiv  Detail & Related papers  (2021-05-19T21:31:18Z)
• Unified Convergence Analysis for Adaptive Optimization with Moving Average Estimator [75.05106948314956]
  We show that an increasing large momentum parameter for the first-order moment is sufficient for adaptive scaling.<n>We also give insights for increasing the momentum in a stagewise manner in accordance with stagewise decreasing step size.
  arXiv  Detail & Related papers  (2021-04-30T08:50:24Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.