2016/07/22 by Brian Ichter, Ichter, Brian, Edward Schmerling +5
Computer Science · Decision Sciences · Engineering · #Air Traffic Management and Optimization #FOS: Computer and information sciences #Probabilistic and Robust Engineering Design #Robotic Path Planning Algorithms #Robotics (cs.RO)
paper · pdf · doi:10.48550/arxiv.1607.06886
openalex publication_date 2016/07/22 · openalex created_date 2022/09/22 · openalex updated_date 2026/08/04
In this paper we present the PUMP (Parallel Uncertainty-aware Multiobjective\nPlanning) algorithm for addressing the stochastic kinodynamic motion planning\nproblem, whereby one seeks a low-cost, dynamically-feasible motion plan subject\nto a constraint on collision probability (CP). To ensure exhaustive evaluation\nof candidate motion plans (as needed to tradeoff the competing objectives of\nperformance and safety), PUMP incrementally builds the Pareto front of the\nproblem, accounting for the optimization objective and an approximation of CP.\nThis is performed by a massively parallel multiobjective search, here\nimplemented with a focus on GPUs. Upon termination of the exploration phase,\nPUMP searches the Pareto set of motion plans to identify the lowest cost\nsolution that is certified to satisfy the CP constraint (according to an\nasymptotically exact estimator). We introduce a novel particle-based CP\napproximation scheme, designed for efficient GPU implementation, which accounts\nfor dependencies over the history of a trajectory execution. We present\nnumerical experiments for quadrotor planning wherein PUMP identifies solutions\nin ~100 ms, evaluating over one hundred thousand partial plans through the\ncourse of its exploration phase. The results show that this multiobjective\nsearch achieves a lower motion plan cost, for the same CP constraint, compared\nto a safety buffer-based search heuristic and repeated RRT trials.\n