Back to search

Georgia Institute of Technology

Generalized Heuristic Search Algorithms with Applications to Motion Planning and Multi-Agent Path Finding Problems

Abstract

dc:description.abstract

This 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 × 7

Rights

Language dc:language.iso
en_US

Identifiers

dc:identifier.*
Handle dc:identifier.uri
http://hdl.handle.net/1853/67293

Chain of custody

source
Harvested from
Georgia Tech
Base URL
repository.gatech.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Lim, Jaein. Generalized Heuristic Search Algorithms with Applications to Motion Planning and Multi-Agent Path Finding Problems. Doctoral thesis, Georgia Institute of Technology, 2022. http://hdl.handle.net/1853/67293