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
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
The University of Waterloo acknowledges that much of our work takes place on the traditional territory of the Neutral, Anishinaabeg and Haudenosaunee peoples. Our main campus is situated on the Haldimand Tract, the land granted to the Six Nations that includes six miles on each side of the Grand River. Our active work toward reconciliation takes place across our campuses through research, learning, teaching, and community building, and is co-ordinated within the Office of Indigenous Relations.