Probabilistically safe motion planning to avoid dynamic obstacles with uncertain motion patterns
This paper presents a real-time path planning algorithm that guarantees probabilistic feasibility for autonomous robots with uncertain dynamics operating amidst one or more dynamic obstacles with uncertain motion patterns. Planning safe trajectories under such conditions requires both accurate predi...
| Main Authors: | , , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Springer-Verlag
2013
|
| Online Access: | http://hdl.handle.net/1721.1/81864 https://orcid.org/0000-0001-8576-1930 https://orcid.org/0000-0002-8293-0492 |
| _version_ | 1826189963212881920 |
|---|---|
| author | Aoude, Georges Roy, Nicholas How, Jonathan P. Luders, Brandon Douglas Joseph, Joshua Mason |
| author2 | Massachusetts Institute of Technology. Department of Aeronautics and Astronautics |
| author_facet | Massachusetts Institute of Technology. Department of Aeronautics and Astronautics Aoude, Georges Roy, Nicholas How, Jonathan P. Luders, Brandon Douglas Joseph, Joshua Mason |
| author_sort | Aoude, Georges |
| collection | MIT |
| description | This paper presents a real-time path planning algorithm that guarantees probabilistic feasibility for autonomous robots with uncertain dynamics operating amidst one or more dynamic obstacles with uncertain motion patterns. Planning safe trajectories under such conditions requires both accurate prediction and proper integration of future obstacle behavior within the planner. Given that available observation data is limited, the motion model must provide generalizable predictions that satisfy dynamic and environmental constraints, a limitation of existing approaches. This work presents a novel solution, named RR-GP, which builds a learned motion pattern model by combining the flexibility of Gaussian processes (GP) with the efficiency of RRT-Reach, a sampling-based reachability computation. Obstacle trajectory GP predictions are conditioned on dynamically feasible paths identified from the reachability analysis, yielding more accurate predictions of future behavior. RR-GP predictions are integrated with a robust path planner, using chance-constrained RRT, to identify probabilistically feasible paths. Theoretical guarantees of probabilistic feasibility are shown for linear systems under Gaussian uncertainty; approximations for nonlinear dynamics and/or non-Gaussian uncertainty are also presented. Simulations demonstrate that, with this planner, an autonomous vehicle can safely navigate a complex environment in real-time while significantly reducing the risk of collisions with dynamic obstacles. |
| first_indexed | 2024-09-23T08:32:35Z |
| format | Article |
| id | mit-1721.1/81864 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T08:32:35Z |
| publishDate | 2013 |
| publisher | Springer-Verlag |
| record_format | dspace |
| spelling | mit-1721.1/818642022-09-23T12:47:56Z Probabilistically safe motion planning to avoid dynamic obstacles with uncertain motion patterns Aoude, Georges Roy, Nicholas How, Jonathan P. Luders, Brandon Douglas Joseph, Joshua Mason Massachusetts Institute of Technology. Department of Aeronautics and Astronautics Aoude, Georges Luders, Brandon Douglas Joseph, Joshua Mason Roy, Nicholas How, Jonathan P. This paper presents a real-time path planning algorithm that guarantees probabilistic feasibility for autonomous robots with uncertain dynamics operating amidst one or more dynamic obstacles with uncertain motion patterns. Planning safe trajectories under such conditions requires both accurate prediction and proper integration of future obstacle behavior within the planner. Given that available observation data is limited, the motion model must provide generalizable predictions that satisfy dynamic and environmental constraints, a limitation of existing approaches. This work presents a novel solution, named RR-GP, which builds a learned motion pattern model by combining the flexibility of Gaussian processes (GP) with the efficiency of RRT-Reach, a sampling-based reachability computation. Obstacle trajectory GP predictions are conditioned on dynamically feasible paths identified from the reachability analysis, yielding more accurate predictions of future behavior. RR-GP predictions are integrated with a robust path planner, using chance-constrained RRT, to identify probabilistically feasible paths. Theoretical guarantees of probabilistic feasibility are shown for linear systems under Gaussian uncertainty; approximations for nonlinear dynamics and/or non-Gaussian uncertainty are also presented. Simulations demonstrate that, with this planner, an autonomous vehicle can safely navigate a complex environment in real-time while significantly reducing the risk of collisions with dynamic obstacles. 2013-10-30T13:29:19Z 2013-10-30T13:29:19Z 2013-05 2011-08 Article http://purl.org/eprint/type/JournalArticle 0929-5593 1573-7527 http://hdl.handle.net/1721.1/81864 Aoude, Georges S., Brandon D. Luders, Joshua M. Joseph, Nicholas Roy, and Jonathan P. How. “Probabilistically safe motion planning to avoid dynamic obstacles with uncertain motion patterns.” Autonomous Robots 35, no. 1 (July 3, 2013): 51-76. https://orcid.org/0000-0001-8576-1930 https://orcid.org/0000-0002-8293-0492 en_US http://dx.doi.org/10.1007/s10514-013-9334-3 Autonomous Robots Creative Commons Attribution-Noncommercial-Share Alike 3.0 http://creativecommons.org/licenses/by-nc-sa/3.0/ application/pdf Springer-Verlag MIT web domain |
| spellingShingle | Aoude, Georges Roy, Nicholas How, Jonathan P. Luders, Brandon Douglas Joseph, Joshua Mason Probabilistically safe motion planning to avoid dynamic obstacles with uncertain motion patterns |
| title | Probabilistically safe motion planning to avoid dynamic obstacles with uncertain motion patterns |
| title_full | Probabilistically safe motion planning to avoid dynamic obstacles with uncertain motion patterns |
| title_fullStr | Probabilistically safe motion planning to avoid dynamic obstacles with uncertain motion patterns |
| title_full_unstemmed | Probabilistically safe motion planning to avoid dynamic obstacles with uncertain motion patterns |
| title_short | Probabilistically safe motion planning to avoid dynamic obstacles with uncertain motion patterns |
| title_sort | probabilistically safe motion planning to avoid dynamic obstacles with uncertain motion patterns |
| url | http://hdl.handle.net/1721.1/81864 https://orcid.org/0000-0001-8576-1930 https://orcid.org/0000-0002-8293-0492 |
| work_keys_str_mv | AT aoudegeorges probabilisticallysafemotionplanningtoavoiddynamicobstacleswithuncertainmotionpatterns AT roynicholas probabilisticallysafemotionplanningtoavoiddynamicobstacleswithuncertainmotionpatterns AT howjonathanp probabilisticallysafemotionplanningtoavoiddynamicobstacleswithuncertainmotionpatterns AT ludersbrandondouglas probabilisticallysafemotionplanningtoavoiddynamicobstacleswithuncertainmotionpatterns AT josephjoshuamason probabilisticallysafemotionplanningtoavoiddynamicobstacleswithuncertainmotionpatterns |