Georgia Institute of Technology
Generalized Heuristic Search Algorithms with Applications to Motion Planning and Multi-Agent Path Finding Problems
Abstract
dc:description.abstractThis thesis investigates novel ways of leveraging generalized interpretations of heuristics to solve complex motion planning problems with completeness and bounded suboptimality guarantees. A set of heuristic search algorithms is developed to utilize relaxed notions of relevancy to more efficiently solve path planning, motion planning and multi-agent path finding problems. The main focus of this thesis is to demonstrate how using generalized heuristics based on the relaxed notions of relevancy helps the hereto developed search algorithms focus their computational efforts to make better progress towards finding a solution. The theoretical properties of the developed algorithms are extensively studied, and their numerical performances are benchmarked against state-of-the-art algorithms across various robotic platforms. This thesis proceeds with a brief introduction and background on existing heuristic search algorithms and their limitations in solving real world planning problems, delineating our contributions in Chapter 1. The main contributions of this thesis follow in the consequent four chapters, where four distinct planning frameworks are presented: hierarchically abstracted path planning, lazy replanning, colored planning, and multi-agent path finding. Each framework is dealt in greater detail in each of the four consequent chapters. Chapter 2 considers planning on hierarchically abstracted graphs by utilizing distributed abstract information as heuristics to find a globally refined solution. Chapter 3 considers lazy replanning which utilizes previous search results as heuristics to facilitate a new plan, while delaying expensive edge evaluations. Chapter 4 considers using semantic information as heuristics to guide search in a principled way. Finally, the multi-agent path finding problem is considered in Chapter 5, namely, the problem of finding a set of collision-free paths for a team of agents while minimizing some global cost, focusing on how the ideas presented in the preceding chapters help produce an efficient algorithm. The thesis is concluded in Chapter 6 with a discussion on potential future research directions.
Degree
thesis:*- Level thesis:degree_level
- Doctoral
- Department dc:contributor.department
- Aerospace Engineering
- Grantor dc:publisher
- Georgia Institute of Technology
- Year dc:date.issued
- 2022
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Lim, Jaein
- Advisor dc:contributor.advisor
-
- Tsiotras, Panagiotis
- Committee members dc:contributor.committeemember
-
- Hutchinson, Seth A.
- Vamvoudakis, Kyriakos G.
- Srinivasa, Siddhartha
- Stump, Ethan A.
Subjects
dc:subject × 7Rights
- Language dc:language.iso
- en_US
Identifiers
dc:identifier.*- Handle dc:identifier.uri
- http://hdl.handle.net/1853/67293