**Contact Info**

Department of Applied Mathematics

University of Waterloo

Waterloo, Ontario

Canada N2L 3G1

Phone: 519-888-4567, ext. 32700

Fax: 519-746-4319

PDF files require Adobe Acrobat Reader

Tuesday, March 27, 2018 — 3:30 PM EDT

MC 6460

Chuanzheng Wang | Applied Math, University of Waterloo

Motion Planning Under Uncertainty

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.

**Contact Info**

Department of Applied Mathematics

University of Waterloo

Waterloo, Ontario

Canada N2L 3G1

Phone: 519-888-4567, ext. 32700

Fax: 519-746-4319

PDF files require Adobe Acrobat Reader

University of Waterloo

University of Waterloo

43.471468

-80.544205

200 University Avenue West

Waterloo,
ON,
Canada
N2L 3G1