Multi-Agent Pathfinding is an NP-Complete search problem with a branching factor that is exponential in the number of agents. Because of this exponential feature, it can be difficult to solve optimally using traditional search techniques, even for relatively small problems. Many recent optimal solvers have attempted to reduce the complexity of the problem by resolving the conflicts between agent paths separately. Very little of this research has focused on creating quality heuristics to help solve the problem. In this thesis, we create heuristics using sub-problems created by removing agents from a complete problem instance. We combine this with the Independence Detection technique for solving the problem by separating agents into independent (non-conflicting) groups. The results showed moderate improvements in state expansions and computation time in problems with a large number of conflicting agents.
","abstract_html":"<p>Multi-Agent Pathfinding is an NP-Complete search problem with a branching factor that is exponential in the number of agents. Because of this exponential feature, it can be difficult to solve optimally using traditional search techniques, even for relatively small problems. Many recent optimal solvers have attempted to reduce the complexity of the problem by resolving the conflicts between agent paths separately. Very little of this research has focused on creating quality heuristics to help solve the problem. In this thesis, we create heuristics using sub-problems created by removing agents from a complete problem instance. We combine this with the Independence Detection technique for solving the problem by separating agents into independent (non-conflicting) groups. The results showed moderate improvements in state expansions and computation time in problems with a large number of conflicting agents.</p>","abstract_has_math":false,"creators":["Kraft, Aaron R."],"institution":null,"degree_name":"M.S.","degree_level":"Masters Thesis","degree_discipline":null,"degree_department":null,"school":null,"contributors":["Nathan Sturtevant, Ph.D.","Mario Lopez","Jun Zhang"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2017,"date_issued":"2017-01-01T08:00:00Z","date_published":"2017-01-01T08:00:00Z","updated_at":"2026-07-24T02:02:38Z","subjects":["Heuristic","Heuristic search","MAPF","Multi-agent pathfinding","Pathfinding","Path planning","Computer Engineering"],"languages":["en"],"rights":["Copyright is held by the author. User is responsible for all copyright compliance.
"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"https://digitalcommons.du.edu/etd/1247","outbound_label":"Repository record","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Nathan Sturtevant, Ph.D.","Mario Lopez","Jun Zhang"]},{"key":"dc:creator","label":"Author","values":["Kraft, Aaron R."]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.available","label":"Dc Date Available","values":["2017-06-06T07:00:00Z"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Masters Thesis"]},{"key":"thesis:degree_name","label":"Degree Name","values":["M.S."]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Heuristic","Heuristic search","MAPF","Multi-agent pathfinding","Pathfinding","Path planning","Computer Engineering"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright is held by the author. User is responsible for all copyright compliance.
"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["https://digitalcommons.du.edu/etd/1247"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["Multi-Agent Pathfinding is an NP-Complete search problem with a branching factor that is exponential in the number of agents. Because of this exponential feature, it can be difficult to solve optimally using traditional search techniques, even for relatively small problems. Many recent optimal solvers have attempted to reduce the complexity of the problem by resolving the conflicts between agent paths separately. Very little of this research has focused on creating quality heuristics to help solve the problem. In this thesis, we create heuristics using sub-problems created by removing agents from a complete problem instance. We combine this with the Independence Detection technique for solving the problem by separating agents into independent (non-conflicting) groups. The results showed moderate improvements in state expansions and computation time in problems with a large number of conflicting agents.
"]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Abstraction Hierarchies for Multi-Agent Pathfinding"]}]}],"canonical_facts":{"dc:contributor":["Nathan Sturtevant, Ph.D.","Mario Lopez","Jun Zhang"],"dc:creator":["Kraft, Aaron R."],"dc:date.available":["2017-06-06T07:00:00Z"],"dc:description.abstract":["Multi-Agent Pathfinding is an NP-Complete search problem with a branching factor that is exponential in the number of agents. Because of this exponential feature, it can be difficult to solve optimally using traditional search techniques, even for relatively small problems. Many recent optimal solvers have attempted to reduce the complexity of the problem by resolving the conflicts between agent paths separately. Very little of this research has focused on creating quality heuristics to help solve the problem. In this thesis, we create heuristics using sub-problems created by removing agents from a complete problem instance. We combine this with the Independence Detection technique for solving the problem by separating agents into independent (non-conflicting) groups. The results showed moderate improvements in state expansions and computation time in problems with a large number of conflicting agents.
"],"dc:format":["application/pdf"],"dc:identifier":["https://digitalcommons.du.edu/etd/1247"],"dc:language":["en"],"dc:rights":["Copyright is held by the author. User is responsible for all copyright compliance.
"],"dc:subject":["Heuristic","Heuristic search","MAPF","Multi-agent pathfinding","Pathfinding","Path planning","Computer Engineering"],"dc:title":["Abstraction Hierarchies for Multi-Agent Pathfinding"],"thesis:degree_level":["Masters Thesis"],"thesis:degree_name":["M.S."]},"updated_at":"2026-07-24T02:02:38Z"}