Thesis (MSc (Mathematical Sciences. Computer SCience))--University of Stellenbosch, 2009. / In this thesis we consider the dynamic path planning problem for robotics. The dynamic path
planning problem, in short, is the task of determining an optimal path, in terms of minimising
a given cost function, from one location to another within a known environment of moving
obstacles.
Our goal is to investigate a number of well-known path planning algorithms, to determine for
which circumstances a particular algorithm is best suited, and to propose changes to existing
algorithms to make them perform better in dynamic environments.
At this stage no thorough comparison of theoretical and actual running times of path planning
algorithms exist. Our main goal is to address this shortcoming by comparing some of the wellknown
path planning algorithms and our own improvements to these path planning algorithms
in 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 relatively
small number of obstacles. As for a grid representation of the environment, we show
that the A* algorithm produces good paths in terms of length and the amount of rotation and
it requires less computation than dynamic algorithms such as D* and D* Lite.
| Identifer | oai:union.ndltd.org:netd.ac.za/oai:union.ndltd.org:sun/oai:scholar.sun.ac.za:10019.1/2519 |
| Date | 03 1900 |
| Creators | Crous, C. B. |
| Contributors | Van der Merwe, A. B., University of Stellenbosch. Faculty of Science. Dept. of Mathematical Sciences. Institute for Applied Computer Science. |
| Publisher | Stellenbosch : University of Stellenbosch |
| Source Sets | South African National ETD Portal |
| Language | English |
| Detected Language | English |
| Type | Thesis |
| Rights | University of Stellenbosch |
Page generated in 0.0018 seconds