2015/04/29 by Lucas Janson, Janson, Lucas, Edward Schmerling +3 · 5 citations
Computer Science · Decision Sciences · Engineering · Mathematics · #Algorithm #Artificial intelligence #Computation #Computer science #Controller (irrigation) #Correctness #Detector #FOS: Computer and information sciences #Formal Methods in Verification #Importance sampling #Mathematical optimization #Mathematics #Monte Carlo method #Motion planning #Path (computing) #Probabilistic and Robust Engineering Design #Probabilistic logic #Reliability and Maintenance Optimization #Robot #Robotic Path Planning Algorithms #Robotics (cs.RO) #Sampling (signal processing) #Software Reliability and Analysis Research #Trajectory #Variance reduction #cs.RO
paper · pdf · doi:10.48550/arxiv.1504.08053
published in arXiv (Cornell University) (Cornell University)
openalex publication_date 2015/04/29 · arxiv created 2015/05/29 · arxiv updated 2015/06/01 · openalex created_date 2022/10/03 · openalex updated_date 2026/08/05
This article presents a novel approach, named MCMP (Monte Carlo Motion\nPlanning), to the problem of motion planning under uncertainty, i.e., to the\nproblem of computing a low-cost path that fulfills probabilistic collision\navoidance constraints. MCMP estimates the collision probability (CP) of a given\npath by sampling via Monte Carlo the execution of a reference tracking\ncontroller (in this paper we consider LQG). The key algorithmic contribution of\nthis paper is the design of statistical variance-reduction techniques, namely\ncontrol variates and importance sampling, to make such a sampling procedure\namenable to real-time implementation. MCMP applies this CP estimation procedure\nto motion planning by iteratively (i) computing an (approximately) optimal path\nfor the deterministic version of the problem (here, using the FMT* algorithm),\n(ii) computing the CP of this path, and (iii) inflating or deflating the\nobstacles by a common factor depending on whether the CP is higher or lower\nthan a target value. The advantages of MCMP are threefold: (i) asymptotic\ncorrectness of CP estimation, as opposed to most current approximations, which,\nas shown in this paper, can be off by large multiples and hinder the\ncomputation of feasible plans; (ii) speed and parallelizability, and (iii)\ngenerality, i.e., the approach is applicable to virtually any planning problem\nprovided that a path tracking controller and a notion of distance to obstacles\nin the configuration space are available. Numerical results illustrate the\ncorrectness (in terms of feasibility), efficiency (in terms of path cost), and\ncomputational speed of MCMP.\n