Autonomous robot path planning

[摘要] In this thesis we consider the dynamic path planning problem for robotics. The dynamic pathplanning problem, in short, is the task of determining an optimal path, in terms of minimisinga given cost function, from one location to another within a known environment of movingobstacles.Our goal is to investigate a number of well-known path planning algorithms, to determine forwhich circumstances a particular algorithm is best suited, and to propose changes to existingalgorithms to make them perform better in dynamic environments.At this stage no thorough comparison of theoretical and actual running times of path planningalgorithms exist. Our main goal is to address this shortcoming by comparing some of the wellknownpath planning algorithms and our own improvements to these path planning algorithmsin a simulation environment.We show that the visibility graph representation of the environment combined with the A*algorithm provides very good results for both path length and computational cost, for a relativelysmall number of obstacles. As for a grid representation of the environment, we showthat the A* algorithm produces good paths in terms of length and the amount of rotation andit requires less computation than dynamic algorithms such as D* and D* Lite.

[发布机构] Stellenbosch University