{"id":{"repo_id":"denver","oai_identifier":"oai:digitalcommons.du.edu:etd-3081"},"canonical_url":"https://search.ndltd.org/etd/denver/oai:digitalcommons.du.edu:etd-3081","repository":{"repo_id":"denver","name":"University of Denver","base_url":"https://digitalcommons.du.edu/do/oai/"},"display":{"title":"Multi-Agent Pathfinding in Mixed Discrete-Continuous Time and Space","abstract":"In the multi-agent pathfinding (MAPF) problem, agents must move from their current locations to their individual destinations while avoiding collisions. Ideally, agents move to their destinations as quickly and efficiently as possible. MAPF has many real-world applications such as navigation, warehouse automation, package delivery and games. Coordination of agents is necessary in order to avoid conflicts, however, it can be very computationally expensive to find mutually conflict-free paths for multiple agents – especially as the number of agents is increased. Existing state-ofthe- art algorithms have been focused on simplified problems on grids where agents have no shape or volume, and each action executed by the agents have the same duration, resulting in simplified collision detection and synchronous, timed execution. In the real world agents have a shape, and usually execute actions with variable duration. This thesis re-formulates the MAPF problem definition for continuous actions, designates specific techniques for continuous-time collision detection, re-formulates two popular algorithms for continuous actions and formulates a new algorithm called Conflict-Based Increasing Cost Search (CBICS) for continuous actions.","abstract_html":"In the multi-agent pathfinding (MAPF) problem, agents must move from their current locations to their individual destinations while avoiding collisions. Ideally, agents move to their destinations as quickly and efficiently as possible. MAPF has many real-world applications such as navigation, warehouse automation, package delivery and games. Coordination of agents is necessary in order to avoid conflicts, however, it can be very computationally expensive to find mutually conflict-free paths for multiple agents – especially as the number of agents is increased. Existing state-ofthe- art algorithms have been focused on simplified problems on grids where agents have no shape or volume, and each action executed by the agents have the same duration, resulting in simplified collision detection and synchronous, timed execution. In the real world agents have a shape, and usually execute actions with variable duration. This thesis re-formulates the MAPF problem definition for continuous actions, designates specific techniques for continuous-time collision detection, re-formulates two popular algorithms for continuous actions and formulates a new algorithm called Conflict-Based Increasing Cost Search (CBICS) for continuous actions.","abstract_has_math":false,"creators":["Walker, Thayne T."],"institution":null,"degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":null,"degree_department":null,"school":null,"contributors":["Nathan R. Sturtevant","Scott T. Leutenegger","Matthew J. Rutherford"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":null,"date_issued":"","date_published":null,"updated_at":"2026-11-19T07:54:59Z","subjects":["Artificial intelligence","Automated planning","Heuristic search","Multi-agent systems","Optimization","Robotics","Artificial Intelligence and Robotics","Computer Sciences"],"languages":["en"],"rights":["<p>Copyright is held by the author. User is responsible for all copyright compliance.</p>","Thayne T. Walker"],"rights_urls":[],"identifier_entries":[],"person_identifier_entries":[]},"links":{"outbound_url":"https://digitalcommons.du.edu/etd/2086","outbound_label":"Repository record","outbound_source":"dc:identifier","record_url":"https://digitalcommons.du.edu/etd/2086","record_label":"Repository record","record_kind":"record","record_source":"dc:identifier","download_url":null,"download_label":null,"download_source":null,"access_status":null,"embargo_until":null,"access_note":null},"source_record":{"url":"https://digitalcommons.du.edu/do/oai/?verb=GetRecord&metadataPrefix=oai_etdms&identifier=oai%3Adigitalcommons.du.edu%3Aetd-3081","prefix":"oai_etdms"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Nathan R. Sturtevant","Scott T. Leutenegger","Matthew J. Rutherford"]},{"key":"dc:creator","label":"Author","values":["Walker, Thayne T."]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.available","label":"Dc Date Available","values":["2022-08-30T07:00:00Z"]},{"key":"dc:date.copyright","label":"Dc Date Copyright","values":["2022-01-01T08:00:00Z"]},{"key":"dc:date.created","label":"Dc Date Created","values":["2022-01-01T08:00:00Z"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph.D."]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Artificial intelligence","Automated planning","Heuristic search","Multi-agent systems","Optimization","Robotics","Artificial Intelligence and Robotics","Computer Sciences"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["<p>Copyright is held by the author. User is responsible for all copyright compliance.</p>"]},{"key":"dc:rights.holder","label":"Dc Rights Holder","values":["Thayne T. Walker"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["https://digitalcommons.du.edu/etd/2086"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["In the multi-agent pathfinding (MAPF) problem, agents must move from their current locations to their individual destinations while avoiding collisions. Ideally, agents move to their destinations as quickly and efficiently as possible. MAPF has many real-world applications such as navigation, warehouse automation, package delivery and games. Coordination of agents is necessary in order to avoid conflicts, however, it can be very computationally expensive to find mutually conflict-free paths for multiple agents – especially as the number of agents is increased. Existing state-ofthe- art algorithms have been focused on simplified problems on grids where agents have no shape or volume, and each action executed by the agents have the same duration, resulting in simplified collision detection and synchronous, timed execution. In the real world agents have a shape, and usually execute actions with variable duration. This thesis re-formulates the MAPF problem definition for continuous actions, designates specific techniques for continuous-time collision detection, re-formulates two popular algorithms for continuous actions and formulates a new algorithm called Conflict-Based Increasing Cost Search (CBICS) for continuous actions."]},{"key":"dc:description.provenance","label":"Dc Description Provenance","values":["Received from ProQuest"]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:format.extent","label":"Dc Format Extent","values":["261 pgs"]},{"key":"dc:title","label":"Title","values":["Multi-Agent Pathfinding in Mixed Discrete-Continuous Time and Space"]}]}],"canonical_facts":{"dc:contributor":["Nathan R. Sturtevant","Scott T. Leutenegger","Matthew J. Rutherford"],"dc:creator":["Walker, Thayne T."],"dc:date.available":["2022-08-30T07:00:00Z"],"dc:date.copyright":["2022-01-01T08:00:00Z"],"dc:date.created":["2022-01-01T08:00:00Z"],"dc:description.abstract":["In the multi-agent pathfinding (MAPF) problem, agents must move from their current locations to their individual destinations while avoiding collisions. Ideally, agents move to their destinations as quickly and efficiently as possible. MAPF has many real-world applications such as navigation, warehouse automation, package delivery and games. Coordination of agents is necessary in order to avoid conflicts, however, it can be very computationally expensive to find mutually conflict-free paths for multiple agents – especially as the number of agents is increased. Existing state-ofthe- art algorithms have been focused on simplified problems on grids where agents have no shape or volume, and each action executed by the agents have the same duration, resulting in simplified collision detection and synchronous, timed execution. In the real world agents have a shape, and usually execute actions with variable duration. This thesis re-formulates the MAPF problem definition for continuous actions, designates specific techniques for continuous-time collision detection, re-formulates two popular algorithms for continuous actions and formulates a new algorithm called Conflict-Based Increasing Cost Search (CBICS) for continuous actions."],"dc:description.provenance":["Received from ProQuest"],"dc:format":["application/pdf"],"dc:format.extent":["261 pgs"],"dc:identifier":["https://digitalcommons.du.edu/etd/2086"],"dc:language":["en"],"dc:rights":["<p>Copyright is held by the author. User is responsible for all copyright compliance.</p>"],"dc:rights.holder":["Thayne T. Walker"],"dc:subject":["Artificial intelligence","Automated planning","Heuristic search","Multi-agent systems","Optimization","Robotics","Artificial Intelligence and Robotics","Computer Sciences"],"dc:title":["Multi-Agent Pathfinding in Mixed Discrete-Continuous Time and Space"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."]},"updated_at":"2026-11-19T07:54:59Z"}