Full Text Available
Note: Clicking the button above will open the full text document at the original institutional repository in a new window.
Field D* pathfinding in weighted simplicial complexes
Includes abstract.
Saved in:
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | English |
| Published: |
Department of Computer Science
2014
|
| Subjects: | |
| Tags: |
No Tags, Be the first to tag this record!
|
| _version_ | 1867613190321340416 |
|---|---|
| access_status_str | Open Access |
| author | Perkins, Simon |
| author2 | Marais, Patrick |
| author_browse | Marais, Patrick Perkins, Simon |
| author_facet | Marais, Patrick Perkins, Simon |
| author_sort | Perkins, Simon |
| collection | Thesis |
| description | Includes abstract. |
| format | Thesis |
| id | oai:open.uct.ac.za:11427/6433 |
| institution | University of Cape Town (South Africa) |
| language | eng |
| last_indexed | 2026-06-10T12:32:12.136Z |
| license_str | Not specified — see source repository |
| provenance_str_mv | Harvested via OAI-PMH from UCTD — University of Cape Town Open Access Repository |
| publishDate | 2014 |
| publishDateRange | 2014 |
| publishDateSort | 2014 |
| publisher | Department of Computer Science |
| publisherStr | Department of Computer Science |
| record_format | dspace |
| source_str | UCTD — University of Cape Town Open Access Repository |
| spelling | oai:open.uct.ac.za:11427/6433 Field D* pathfinding in weighted simplicial complexes Perkins, Simon Marais, Patrick Gain, James Computer Science Includes abstract. Includes bibliographical references. 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. 2014-08-13T19:34:02Z 2014-08-13T19:34:02Z 2013 Doctoral Thesis Doctoral PhD http://hdl.handle.net/11427/6433 eng application/pdf Department of Computer Science Faculty of Science University of Cape Town |
| spellingShingle | Computer Science Perkins, Simon Field D* pathfinding in weighted simplicial complexes |
| thesis_degree_str | Doctoral |
| title | Field D* pathfinding in weighted simplicial complexes |
| title_full | Field D* pathfinding in weighted simplicial complexes |
| title_fullStr | Field D* pathfinding in weighted simplicial complexes |
| title_full_unstemmed | Field D* pathfinding in weighted simplicial complexes |
| title_short | Field D* pathfinding in weighted simplicial complexes |
| title_sort | field d pathfinding in weighted simplicial complexes |
| topic | Computer Science |
| url | http://hdl.handle.net/11427/6433 |
| work_keys_str_mv | AT perkinssimon fielddpathfindinginweightedsimplicialcomplexes |