Field D* pathfinding in weighted simplicial complexes

Simple item page
dc.contributor.advisorMarais, Patricken_ZA
dc.contributor.advisorGain, Jamesen_ZA
dc.contributor.authorPerkins, Simonen_ZA
dc.date.accessioned2014-08-13T19:34:02Z
dc.date.available2014-08-13T19:34:02Z
dc.date.issued2013en_ZA
dc.descriptionIncludes abstract.en_ZA
dc.descriptionIncludes bibliographical references.en_ZA
dc.description.abstractThe development of algorithms to efficiently determine an optimal path through a complex environment is a continuing area of research within Computer Science. When such environments can be represented as a graph, established graph search algorithms, such as Dijkstra’s shortest path and A*, can be used. However, many environments are constructed from a set of regions that do not conform to a discrete graph. The Weighted Region Problem was proposed to address the problem of finding the shortest path through a set of such regions, weighted with values representing the cost of traversing the region. Robust solutions to this problem are computationally expensive since finding shortest paths across a region requires expensive minimisation. Sampling approaches construct graphs by introducing extra points on region edges and connecting them with edges criss-crossing the region. Dijkstra or A* are then applied to compute shortest paths. The connectivity of these graphs is high and such techniques are thus not particularly well suited to environments where the weights and representation frequently change. The Field D* algorithm, by contrast, computes the shortest path across a grid of weighted square cells and has replanning capabilites that cater for environmental changes. However, representing an environment as a weighted grid (an image) is not space-efficient since high resolution is required to produce accurate paths through areas containing features sensitive to noise. In this work, we extend Field D* to weighted simplicial complexes – specifically – triangulations in 2D and tetrahedral meshes in 3D.en_ZA
dc.identifier.apacitationPerkins, S. (2013). <i>Field D* pathfinding in weighted simplicial complexes</i>. (Thesis). University of Cape Town ,Faculty of Science ,Department of Computer Science. Retrieved from http://hdl.handle.net/11427/6433en_ZA
dc.identifier.chicagocitationPerkins, Simon. <i>"Field D* pathfinding in weighted simplicial complexes."</i> Thesis., University of Cape Town ,Faculty of Science ,Department of Computer Science, 2013. http://hdl.handle.net/11427/6433en_ZA
dc.identifier.citationPerkins, S. 2013. Field D* pathfinding in weighted simplicial complexes. University of Cape Town.en_ZA
dc.identifier.ris TY - Thesis / Dissertation AU - Perkins, Simon AB - The development of algorithms to efficiently determine an optimal path through a complex environment is a continuing area of research within Computer Science. When such environments can be represented as a graph, established graph search algorithms, such as Dijkstra’s shortest path and A*, can be used. However, many environments are constructed from a set of regions that do not conform to a discrete graph. The Weighted Region Problem was proposed to address the problem of finding the shortest path through a set of such regions, weighted with values representing the cost of traversing the region. Robust solutions to this problem are computationally expensive since finding shortest paths across a region requires expensive minimisation. Sampling approaches construct graphs by introducing extra points on region edges and connecting them with edges criss-crossing the region. Dijkstra or A* are then applied to compute shortest paths. The connectivity of these graphs is high and such techniques are thus not particularly well suited to environments where the weights and representation frequently change. The Field D* algorithm, by contrast, computes the shortest path across a grid of weighted square cells and has replanning capabilites that cater for environmental changes. However, representing an environment as a weighted grid (an image) is not space-efficient since high resolution is required to produce accurate paths through areas containing features sensitive to noise. In this work, we extend Field D* to weighted simplicial complexes – specifically – triangulations in 2D and tetrahedral meshes in 3D. DA - 2013 DB - OpenUCT DP - University of Cape Town LK - https://open.uct.ac.za PB - University of Cape Town PY - 2013 T1 - Field D* pathfinding in weighted simplicial complexes TI - Field D* pathfinding in weighted simplicial complexes UR - http://hdl.handle.net/11427/6433 ER - en_ZA
dc.identifier.urihttp://hdl.handle.net/11427/6433
dc.identifier.vancouvercitationPerkins S. Field D* pathfinding in weighted simplicial complexes. [Thesis]. University of Cape Town ,Faculty of Science ,Department of Computer Science, 2013 [cited yyyy month dd]. Available from: http://hdl.handle.net/11427/6433en_ZA
dc.language.isoengen_ZA
dc.publisher.departmentDepartment of Computer Scienceen_ZA
dc.publisher.facultyFaculty of Scienceen_ZA
dc.publisher.institutionUniversity of Cape Town
dc.subject.otherComputer Scienceen_ZA
dc.titleField D* pathfinding in weighted simplicial complexesen_ZA
dc.typeDoctoral Thesis
dc.type.qualificationlevelDoctoral
dc.type.qualificationnamePhDen_ZA
uct.type.filetypeText
uct.type.filetypeImage
uct.type.publicationResearchen_ZA
uct.type.resourceThesisen_ZA
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
thesis_sci_2013_perkins_simon.pdf
Size:
5.08 MB
Format:
Adobe Portable Document Format
Description:
Download
Collections
PhD / Doctoral