Efficient Robot Motion Planning in Cluttered Environments

Robotics has become a part of the solution in various applications today: autonomous vehicles navigating busy streets, articulated robots tirelessly sorting packages in warehouses, feeding people in care homes and mobile robots assisting in rescue operations. Central to any robot that needs to navigate its environment, is Motion Planning: the task of computing a collision-free motion for a (robotic) system between given start and goal states in an environment cluttered with obstacles. As tasks become more complex, there is a need to develop more sophisticated motion planning algorithms that can compute high quality solutions for the robot quickly. This thesis primarily address the challenge in three phases: First, we approximate the optimal motion planning problem in a continuous space to a search for the shortest path on a discrete graph abstraction. We investigate the computational bottlenecks in search: graph operations and collision evaluations and propose GLS, an algorithmic framework to balance the computational effort between the two operations. In addition to showing that GLS captures an oracular behaviour that minimizes planning time, we propose strategies to balance the computational effort and approximate such an oracle. Second, we focus on the graph abstraction. A desirable graph is sparse allowing for fast search (fewer graph operations and edge evaluations) but locally dense in cluttered regions such that a feasible low-cost path exists. We note that there is structural similarity in the environments that a robot typically operates in. To this end, we propose LEGO, to leverage a robot's experience in similar environments and learn to generate sparse graphs that adequately sample bottleneck regions in the environment while ensuring a high quality solution exists. Third, we relax the assumption of a fixed discrete graph abstraction to compute the optimal solution in the continuous space. We extend the computational efficiency that GLS provides to an incremental asymptotically-optimal sampling-based algorithm. IGLS computes the optimal solution in an anytime manner by iteratively sampling increasingly dense graphs and minimizing the planning time at each iteration. We further investigate improving the convergence rate of such algorithms. Asymptotically-optimal planners typically compute an initial solution and subsequently focus sampling graphs in an Informed Set defined by the current solution cost. We propose GuILD which leverages the search tree constructed in every iteration to further inform sampling for a faster convergence to optimality. Finally, we test our algorithms and evaluate their efficacy on a suite of robotic platforms and planning problems. Our results demonstrate our algorithms to significantly reduce planning times across domains and outperform competing planners.

Author dc:creator

• Mandalika, Aditya Vamsikrishna

Advisor dc:contributor.advisor

• Srinivasa, Siddhartha

• Motion Planning
• Robotics
• Search and Planning
• Artificial intelligence

Statement dc:rights

• none

Language dc:language.iso

en_US

Handle dc:identifier.uri

http://hdl.handle.net/1773/47042

OAI identifier oai:identifier

oai:digital.lib.washington.edu:1773/47042