Stochastic Multi-Objective Kinodynamic Planning Against Adversaries

• URL: http://arxiv.org/abs/2607.19284v1
• Date: Tue, 21 Jul 2026 16:56:34 GMT
• Title: Stochastic Multi-Objective Kinodynamic Planning Against Adversaries
• Abstract summary: This paper addresses multi-objective kinodynamic planning in environments with hybrid adversaries that probabilistically transition to adversarial modes based on the ego state.<n>We introduce Multi-Objective RRT (SMO-RRT), for which we prove probabilistic completeness, followed by Multi-Objective Stable RRT (SMO-SST)<n>For both algorithms, we derive a finite-sample bound on the probability of chance constraint violation for systems with non-Gaussian, state-dependent uncertainty.
• Score: 4.800861909357391
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This paper addresses multi-objective kinodynamic planning in environments with stochastic hybrid adversaries that probabilistically transition to adversarial modes based on the ego state. The goal is to construct the Pareto-front of paths that trade off execution cost and the probability of safety constraint violation (risk). Existing chance-constrained planners evaluate risk over open-loop trajectories, yielding overly conservative solutions that fail to account for ego-agent reactivity. To address this limitation, we shift the planning space to sequences of closed-loop policies, and integrate sample-based risk evaluation directly into tree construction via Monte-Carlo particle rollouts. We first introduce Stochastic Multi-Objective RRT (SMO-RRT), for which we prove probabilistic completeness, followed by Stochastic Multi-Objective Stable Sparse RRT (SMO-SST), which leverages selective pruning to improve numerical performance at the cost of completeness. For both algorithms, we derive a finite-sample bound on the probability of chance constraint violation for systems with non-Gaussian, state-dependent uncertainty, enabling probabilistically safe planning in a broad class of environments applicable to multi-agent systems, social navigation, and autonomous driving.

Related papers

• World Models as Adversaries: Multi-Agent Self-Play Fine-Tuning for Robust Motion Planning [60.88859946006306]
  Adversa World Modeling is a theoretically grounded multi-agent self-play fine-tuning framework.<n>In inner minimization, the planner's predictive world model is converted into a role-conditioned adversary that learns sparse, scene-adaptive attack coalitions.<n> Experiments on the nuPlan and InterPlan benchmarks demonstrate that our method generates transferable adversarial interactions.
  arXiv  Detail & Related papers  (2026-07-12T07:44:16Z)
• Active Timepoint Selection for Learning Measure-Valued Trajectories [55.49809248697036]
  Inferring continuous probability paths from snapshots is a fundamental challenge in domains like single-cell biology.<n>We introduce a framework which extends active experimentation to the space of sparse measures.<n>This yields an acquisition policy that iteratively selects measurement times to minimize uncertainty.
  arXiv  Detail & Related papers  (2026-05-28T22:22:35Z)
• Provably Safe Motion Planning Under Unknown Disturbances [14.551794453957404]
  We present a sampling-based motion planning algorithm for robotic systems affected by random disturbances of unknown distribution.<n>Safety requirements are formulated as chance-constraints.<n>Case studies show our algorithm finds valid plans in cluttered environments under strict safety thresholds, outperforming state-of-the-art methods.
  arXiv  Detail & Related papers  (2026-05-26T07:02:27Z)
• Branch-Stochastic Model Predictive Control for Motion Planning under Multi-Modal Uncertainty with Scenario Clustering [4.456206353869196]
  We present a novel combination of SMPC and the branching structure, enabling the planner to generate distinct trajectories for different possible intentions.<n>A novel scenario clustering is proposed to merge prediction scenarios based on high-level decision similarity, thereby ensuring real-time tractability.<n> Simulation studies in challenging highway scenarios demonstrate that the proposed method improves safety, reduces conservatism, and achieves real-time computational performance.
  arXiv  Detail & Related papers  (2026-05-21T15:15:16Z)
• Statistical Contraction for Chance-Constrained Trajectory Optimization of Non-Gaussian Stochastic Systems [0.0]
  Our framework employs conformal inference to generate confidence sets for the closed-loop dynamics around arbitrary reference trajectories.<n>Via appropriate constraint tightening, chance constraints can be reformulated into tractable, statistically valid deterministic constraints on the reference trajectories.<n>This enables a formal pathway to leverage and validate learning-based motion planners and controllers, such as those with neural contraction metrics, in safety-critical real-world applications.
  arXiv  Detail & Related papers  (2026-03-07T08:01:20Z)
• Probabilistic Reach-Avoid for Bayesian Neural Networks [71.67052234622781]
  We show that an optimal synthesis algorithm can provide more than a four-fold increase in the number of certifiable states. The algorithm is able to provide more than a three-fold increase in the average guaranteed reach-avoid probability.
  arXiv  Detail & Related papers  (2023-10-03T10:52:21Z)
• Dual Formulation for Chance Constrained Stochastic Shortest Path with Application to Autonomous Vehicle Behavior Planning [3.655021726150368]
  The Constrained Shortest Path problem (C-SSP) is a formalism for planning in environments under certain types of operating constraints. This work's first contribution is an exact integer linear formulation for Chance-constrained policies. Third, we show that the CC-SSP formalism can be generalized to account for constraints that span through multiple time steps.
  arXiv  Detail & Related papers  (2023-02-25T16:40:00Z)
• When Demonstrations Meet Generative World Models: A Maximum Likelihood Framework for Offline Inverse Reinforcement Learning [62.00672284480755]
  This paper aims to recover the structure of rewards and environment dynamics that underlie observed actions in a fixed, finite set of demonstrations from an expert agent. Accurate models of expertise in executing a task has applications in safety-sensitive applications such as clinical decision making and autonomous driving.
  arXiv  Detail & Related papers  (2023-02-15T04:14:20Z)
• Modular Deep Reinforcement Learning for Continuous Motion Planning with Temporal Logic [59.94347858883343]
  This paper investigates the motion planning of autonomous dynamical systems modeled by Markov decision processes (MDP) The novelty is to design an embedded product MDP (EP-MDP) between the LDGBA and the MDP. The proposed LDGBA-based reward shaping and discounting schemes for the model-free reinforcement learning (RL) only depend on the EP-MDP states.
  arXiv  Detail & Related papers  (2021-02-24T01:11:25Z)
• Risk-Sensitive Sequential Action Control with Multi-Modal Human Trajectory Forecasting for Safe Crowd-Robot Interaction [55.569050872780224]
  We present an online framework for safe crowd-robot interaction based on risk-sensitive optimal control, wherein the risk is modeled by the entropic risk measure. Our modular approach decouples the crowd-robot interaction into learning-based prediction and model-based control. A simulation study and a real-world experiment show that the proposed framework can accomplish safe and efficient navigation while avoiding collisions with more than 50 humans in the scene.
  arXiv  Detail & Related papers  (2020-09-12T02:02:52Z)
• Online Mapping and Motion Planning under Uncertainty for Safe Navigation in Unknown Environments [3.2296078260106174]
  This manuscript proposes an uncertainty-based framework for mapping and planning feasible motions online with probabilistic safety-guarantees. The proposed approach deals with the motion, probabilistic safety, and online computation constraints by: (i) mapping the surroundings to build an uncertainty-aware representation of the environment, and (ii) iteratively (re)planning to goal that are kinodynamically feasible and probabilistically safe through a multi-layered sampling-based planner in the belief space.
  arXiv  Detail & Related papers  (2020-04-26T08:53:37Z)

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.