PhD Comprehensive Seminar | Chuanzheng Wang, Motion Planning Under Uncertainty

MC 6460

Speaker

Chuanzheng Wang | Applied Math, University of Waterloo

Title

Motion Planning Under Uncertainty 

Abstract

Motion planning that takes into consideration of uncertainty is important for autonomous robots to operate more reliably. Uncertainty is mainly in three aspects: environment, dynamics and measurements. Environment uncertainty is usually caused by moving obstacles which result in dynamical maps or static but imperfect maps. Stochastic noise affecting the robot dynamics is a critical reason for dynamical uncertainty. Measurement uncertainty is usually caused by sensors that are subject to noise. My current work is mainly focusing on uncertainty in environment. Our environment model consists of multiple environments that the robot might be working in. The set of all possible environments is assigned a probability distribution, based on which a policy has to be calculated for the robot to reach the goal while minimizing the expected cost. Some previous solutions to such problems require a cost-map that stores all the shortest paths starting from one point to every other point in all environments. The Dijkstra algorithm is efficient in providing the shortest path from one point to every other point in one environment. As a result, one naive way of computing the cost-map is by running Dijkstra algorithm in each environment. However, this is very inefficient as the number of environments becomes large. In this talk, a novel algorithm will be discussed that computes the cost-map more efficiently by using the idea of critical obstacles. Theoretical analysis guarantees that the algorithm can compute the cost-map in polynomial time. Simulation results show that it can save more than 90% computing time compared to previous methods.