Robust Stochastic Shortest-Path Planning via Risk-Sensitive Incremental Sampling
With the pervasiveness of Stochastic Shortest-Path (SSP) problems in high-risk industries, such as last-mile autonomous delivery and supply chain management, robust planning algorithms are crucial for ensuring successful task completion while mitigating hazardous outcomes. Mainstream chance-constrained incremental sampling techniques for solving SSP problems tend to be overly conservative and typically do not consider the likelihood of undesirable tail events. We propose an alternative risk-aware approach inspired by the asymptotically-optimal Rapidly-Exploring Random Trees (RRT*) planning algorithm, which selects nodes along path segments with minimal Conditional Value-at-Risk (CVaR). Our motivation rests on the step-wise coherence of the CVaR risk measure and the optimal substructure of the SSP problem. Thus, optimizing with respect to the CVaR at each sampling iteration necessarily leads to an optimal path in the limit of the sample size. We validate our approach via numerical path planning experiments in a two-dimensional grid world with obstacles and stochastic path-segment lengths. Our simulation results show that incorporating risk into the tree growth process yields paths with lengths that are significantly less sensitive to variations in the noise parameter, or equivalently, paths that are more robust to environmental uncertainty. Algorithmic analyses reveal similar query time and memory space complexity to the baseline RRT* procedure, with only a marginal increase in processing time. This increase is offset by significantly lower noise sensitivity and reduced planner failure rates.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Hierarchical Constrained Stochastic Shortest Path Planning via Cost Budget Allocation
Stochastic sequential decision making often requires hierarchical structure in the problem where each high-level action should be further planned with primitive states and actions. In addition, many real-world applicatio…
Decision MakingSequential Decision MakingRisk-Averse Stochastic Shortest Path Planning
We consider the stochastic shortest path planning problem in MDPs, i.e., the problem of designing policies that ensure reaching a goal state from a given initial state with minimum accrued cost. In order to account for r…
Finding Risk-Averse Shortest Path with Time-dependent Stochastic Costs
In this paper, we tackle the problem of risk-averse route planning in a transportation network with time-dependent and stochastic costs. To solve this problem, we propose an adaptation of the A* algorithm that accommodat…
Dual Formulation for Chance Constrained Stochastic Shortest Path with Application to Autonomous Vehicle Behavior Planning
Autonomous vehicles face the problem of optimizing the expected performance of subsequent maneuvers while bounding the risk of collision with surrounding dynamic obstacles. These obstacles, such as agent vehicles, often …
Autonomous VehiclesRisk-aware Stochastic Shortest Path
We treat the problem of risk-aware control for stochastic shortest path (SSP) on Markov decision processes (MDP). Typically, expectation is considered for SSP, which however is oblivious to the incurred risk. We present …