Stochastic Multi-Objective Kinodynamic Planning Against Adversaries
2026-07-21 • Robotics
Robotics
AI summaryⓘ
The authors study how to plan safe and efficient paths for robots or vehicles that must deal with other unpredictable, possibly adversarial agents. Instead of just planning fixed paths that don't adapt to changes, they propose planning sequences of adaptable actions and use simulations to estimate the risk of failure. They develop two new algorithms that balance finding all good solutions and running efficiently, with mathematical guarantees about safety under uncertain conditions. Their work aims to improve planning in complex environments like autonomous driving or social robot navigation.
kinodynamic planningPareto-frontchance-constrained planningMonte-Carlo rolloutsstochastic hybrid systemsclosed-loop policiesprobabilistic completenessnon-Gaussian uncertaintymulti-agent systemsautonomous driving
Authors
Thomas Marshall Vielmetti, Daniel Cherenson, Dimitra Panagou
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.