A Hierarchical Algorithm for Probabilistically Complete Path Planning in Multi-Floor Environments

Navigation in multi-floor, multi-building environments is increasingly important in robotics. For wheeled robots, these environments can be conveniently modeled as a set of 2D maps, representing floors, connected by “wormholes”, which represent elevators and other between-floor connections. The full topological structure of the space can thus be described as a weighted graph. However, existing planning algorithms for multi-floor environments modeled in this way do not extend the guarantees on completeness and optimality provided by the underlying motion planning algorithms used within the 2D maps. This work proposes a new algorithm, HRG*, for probabilistically complete and asymptotically optimal multi-floor path planning that carries these guarantees, together with a reference implementation whose performance is characterized in comparison to the native version.

Name thesis:degree_name

Master

Department dc:contributor.department

Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2021

Author dc:creator

• Curtis, Shiloh

Advisor dc:contributor.advisor

• Kaelbling, Leslie P.

Statement dc:rights

• In Copyright - Educational Use Permitted
• Copyright MIT

Licence dc:rights.uri

• http://rightsstatements.org/page/InC-EDU/1.0/

Handle dc:identifier.uri

https://hdl.handle.net/1721.1/139106

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/139106