Topology-inspired probabilistic path replanning in dynamic environments

dc.contributor.authorFisher, Richard
dc.date.accessioned2019-04-10T11:58:28Z
dc.date.available2019-04-10T11:58:28Z
dc.date.issued2018
dc.descriptionA thesis submitted to the Faculty of Science, University of the Witwatersrand, in fulfilment of the requirements for the degree of Master of Science, 2018en_ZA
dc.description.abstractPath replanning in high dimensional dynamic environments is critical to the success of interactive and reactive robotic agents. State of the art replanning algorithms typically extend sampling-based methods such as rapidly-exploring random trees (RRT) or probabilistic roadmaps (PRM). However, the speed of replanning in complex configuration spaces is relatively slow, which limits the effectiveness of robotic agents in highly dynamic environments. This thesis proposes DRM-connect, a novel generalisation of the PRM and RRT-connect algorithms, which carries out replanning in dynamic environments by executing graph searches over an underlying graph G, using lazy collision checking. If a path through the graph is not found, DRM-connect will repair the graph using a novel extension to RRT-connect, which we call PRM-connect. Additionally, we investigate using an approximate Reeb graph as the underlying graph G, which attempts to capture the underlying topology of the task manifold from prior experience. DRM-connect is tested with both a Reeb graph and na¨ıve graph in a 2-D domain and compared to RRT, while DRMconnect with a Reeb graph is tested in three 7-D domains, and compared to RRT-connect. Through simulation we show that the combination of DRM-connect and a Reeb graph typically outperforms both RRT/RRT-connect and DRM-connect with a na¨ıve graph in terms of replanning times, with minimal impact on the length of the solution path.en_ZA
dc.description.librarianXL2019en_ZA
dc.format.extentOnline resource (46 leaves)
dc.identifier.citationFisher, Richard Carl, (2018) Topology-inspired probabilistic path replanning in dynamic environments, University of the Witwatersrand, Johannesburg, https://hdl.handle.net/10539/26722.
dc.identifier.urihttps://hdl.handle.net/10539/26722
dc.language.isoenen_ZA
dc.subject.lcshTopology
dc.subject.lcshPath analysis (Statistics)
dc.subject.lcshTopology--Data processing
dc.titleTopology-inspired probabilistic path replanning in dynamic environmentsen_ZA
dc.typeThesisen_ZA
Files
Original bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
researchThesis_RichardFisher_558921.pdf
Size:
4.87 MB
Format:
Adobe Portable Document Format
Description:
License bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
license.txt
Size:
1.71 KB
Format:
Item-specific license agreed upon to submission
Description:
Collections