Motion planning consists of finding a valid, collision-free path for a robot from a start configuration to a goal configuration. Planning in an dynamic environment is complicated by the need for constant adjustments of plans to account for moving obstacles. Yet, it is critical in real-world applications such as flight coordination, assistive robots and autonomous vehicles. In these dynamic environments, the precise future position of obstacles is often unobtainable due to either robot sensor noise or stochasticity of obstacles dynamics (such as pedestrians). It is therefore important and an active area of research to produce collision-free trajectories in the presence of these uncertainties in real-time.
We focus on developing real-time motion planners with high navigation success rates for environments with a large number (up to 900) of stochastically moving obstacles and robot sensor uncertainty. We developed methods that works even when moving obstacles have strongly-interacting stochastic dynamics or completely unknown dynamics.
Non-interacting obstacles and stochastic, yet known dynamics
We employ formal control theory in order to address stochastic, yet known dynamics. Stochastic Reachability (SR) analysis computes the optimal robot action to avoid stochastically moving obstacles. However, to the high computation cost, the analysis has not been previously practical to integrate with online motion planning. In order to employ SR sets for real-time motion planning, we developed APF-SR [WAFR 14, video below], which combines SR sets, computed offline, with a online motion planning method, Artificial Potential Fields (APF). This method is a real-time capable and achieves high probability of success (up to 95%) when navigating in environments with up to 300 stochastically moving obstacles. We also extended APF-SR to work in the presence of complex static obstacles via offline generated global guidance paths [ICRA 15, video].
Lastly, we also integrated SR sets directly with roadmaps [HSCC 14, video].
On the other hand, it is well-known that the stochastic obstacle dynamics poses a significant challenge for motion planning since the predicted obstacle distribution may occupy a large space, causing the "freezing robot" problem.
To address this, we developed the Dynamic Risk Tolerance.
By dynamically changing the probability of collision threshold, this formulism allows tree-based motion planners to balance between short-term path safety and the discovery of long-term paths.
This method is also real-time capable and achieves 46% higher success rate than the current state of the art method. [ICRA 17, video]
Strongly-Interacting obstacles with known stochastic dynamics, imperfect robot sensors
We have utilized Monte Carlo simulations to predict the position of stochastically moving obstacles in order to better inform tree-based motion planning methods with the method called Stochastic Ensemble Simulation (SES) based planning.
This simulation can be done online [IROS 16, video below] for predictions of obstacles with strongly-interacting stochastic dynamics, or offline [IROS 15, video], for non-interacting obstacles.
Both methods have higher success rates (up to 40% higher than comparison methods) in environments with 50 strongly-interacting obstacles and imperfect robot sensors.
Unknown obstacle dynamics
When obstacle dynamics are unknown, the navigation problem can be even more difficult. We have tackled this problem through the use of reinforcement learning where the learned goal is to arrive at the goal while maximizing distance from obstacles.
This can be seen as a preference balancing task where manual derivation of optimal robot motions for these opposing preferences is difficult.
PrEference Appraisal Reinforcement Learning (PEARL) [ICRA 16, video below] automatically learns near optimal motions, which solves task with opposing preferences for acceleration controlled robots. PEARL projects the high-dimensional continuous robot state space to a low dimensional preference feature space resulting in efficient and adaptable planning. PEARL can be used for dynamic obstacle avoidance robotic tasks, where an agent must navigate to the goal without collision with moving obstacles. The agent is trained with 4 static obstacles, while the trained agent avoids up to 900 moving obstacles with complex hybrid stochastic obstacle dynamics. Our results indicate PEARL has comparable success rates with state of the art methods that can require manual tuning.
Nick Malone, Hao-Tien (Lewis) Chiang, Kendra Lesser, Meeko Oishi, Lydia Tapia, "Hybrid Dynamic Moving Obstacle Avoidance Using a Stochastic Reachable Set-Based Potential Field", IEEE Transactions on Robotics, 33(8), pp. 1124-1138, Oct. 2017. (pdf, Bibtex)
Hao-Tien (Lewis) Chiang, Baisravan HomChaudhuri, Abraham Vinod, Meeko Oishi, Lydia Tapia, "Dynamic Risk Tolerance: Motion Planning by Balancing Short-Term and Long-Term Stochastic Dynamic Predictions", In Proceedings of IEEE International Conference on Robotics and Automation (ICRA), pp. 1023-1030, Singapore, May 2017. (pdf, Bibtex)
Hao-Tien Chiang, Nathanael Rackley, Lydia Tapia, "Runtime SES Planning: Online Motion Planning in Environments with Stochastic Dynamics and Uncertainty", In Proceedings of the IEEE International Conference on Intelligent Robots and Systems (IROS), pp. 4802-4809, Deajon, South Korea, Oct. 2016. (pdf, Bibtex)
Aleksandra Faust, Hao-Tien Chiang, Nathanael Rackley, Lydia Tapia, "Avoiding Moving Obstacles with Stochastic Hybrid Dynamics using PEARL:PrEference Appraisal Reinforcement Learning", In Proc. of IEEE International Conference on Robotics and Automation (ICRA), pp. 484-490, Stockholm, Sweeden, May 2016. (pdf, Bibtex)
Hao-Tien Chiang, Nathanael Rackley, Lydia Tapia, "Stochastic Ensemble Simulation Motion Planning in Stochastic Dynamic Environments", In International Conference on Intelligent Robots and Systems (IROS), pp 2347-2354, Hamburg, Germany, Oct. 2015. (pdf, Bibtex)
Hao-Tien Chiang, Nick Malone, Kendra Lesser, Meeko Oishi, Lydia Tapia, "Path-Guided Artificial Potential Fields with Stochastic Reachable Sets for Motion Planning in Highly Dynamic Environments", In International Conference on Robotics and Automation (ICRA), pp. 2347-2354, Seattle, WA, U.S.A., May 2015. (pdf, Bibtex)
Hao-Tien Chiang, Nick Malone, Kendra Lesser, Meeko Oishi, Lydia Tapia, "Aggressive Moving Obstacle Avoidance Using a Stochastic Reachable Set Based Potential Field", In International Workshop on the Algorithmic Foundations of Robotics (WAFR), Istanbul, Turkey, 3-5 Aug. 2014. (pdf, Bibtex)
Nick Malone, Kendra Lesser, Meeko Oishi, Lydia Tapia, "Stochastic Reachability Based Motion Planning for Multiple Moving Obstacle Avoidance", In Proc. International Conference on Hybrid Systems: Computation and Control (HSCC), pp. 51-60, Berlin, Germany, Apr. 2014. (pdf, Bibtex, Video)