Topology-inspired probabilistic path replanning in dynamic environments

A thesis submitted to the Faculty of Science, University of the Witwatersrand, in fulfilment of the requirements for the degree of Master of Science, 2018Path 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.XL201