Efficiently coordinating multiple robots to collaboratively complete a set of tasks requires solving two tightly coupled problems: task assignment and collision-free path planning. A widely used formalism for this setting is the Multi-Agent Path Finding (MAPF) framework, which computes conflict-free paths for agents navigating from start to goal locations on a discrete graph. Variants such as Task Assignment and Path Finding (TAPF) extend this framework by jointly determining both agent–task pairings and collision-free paths. This dissertation advances the state of the art in MAPF and its extensions by proposing new algorithms that improve computational efficiency, scalability, and real-world applicability in dynamic, physically constrained environments.

The first contribution focuses on improving the computational efficiency of MAPF. We develop an accelerated Conflict-Based Search (CBS) framework operating over structural–semantic topometric maps, where abstracted regions such as intersections and corridors replace dense grid cells. By reasoning about conflicts at the level of region occupancy in continuous time, rather than at individual grid cells, this representation drastically reduces the number of potential conflicts and search nodes while still supporting fine-grained temporal resolution. Additionally, we propose a Hybrid Priority-Based Search (HPBS) algorithm that integrates Priority-Based Search (PBS) and local CBS within a single search framework, combining the efficiency of PBS with the completeness guarantees of CBS. Together, these methods achieve significant speedups while preserving optimal or bounded-suboptimal solution quality.

The second contribution addresses the Task Assignment and Path Finding (TAPF) problem, which extends MAPF by jointly deciding how tasks are distributed among agents and how agents move to execute them. We first propose two decoupled approaches, in which task allocation and path planning are solved sequentially. The Simulated Annealing with recurrent CBS (SA-reCBS) framework combines a metaheuristic assignment process with a recurrent CBS planner to efficiently handle large-scale TAPF instances. The second decoupled method, a cluster-based task assignment and control framework, employs hierarchical clustering, the Hungarian algorithm, and a traveling salesman formulation to compute balanced task allocations and near-optimal routes. In contrast, the Conflict-Based Search with Task Sequencing (CBS-TS) framework represents a coupled formulation that integrates task assignment and path planning within a single optimization loop. By combining Mixed-Integer Linear Programming (MILP) for task sequencing with CBS for conflict resolution, CBS-TS achieves globally optimal flowtime across all agents and tasks.

The final contribution bridges the gap between discrete MAPF theory and physically realizable robot motion. Three complementary methods are proposed to achieve multi-robot motion planning under dynamic and kinematic constraints. The first, Hybrid Conflict-Based Search (HCBS), extends CBS to continuous space by embedding motion primitives directly into the search, using A* for holonomic robots and Hybrid A* for non-holonomic robots with Ackermann steering, together with geometric body-level conflict detection. The second, a Nonlinear Model Predictive Control (NMPC) framework augmented with a reactive Artificial Potential Field (APF) layer, enables real-time position tracking and adaptive collision avoidance in dynamic environments, providing robustness against disturbances and moving obstacles. The third, a trajectory optimization pipeline, refines discrete paths generated by CBS-TS into smooth, dynamically feasible trajectories within safe corridors, enforcing kinematic constraints, maintaining safety margins, and guaranteeing precise task visitation.

Collectively, these contributions establish a unified progression from discrete, combinatorial coordination to continuous, dynamically feasible multi-robot motion planning. Through extensive simulations and experiments with heterogeneous robotic platforms, the proposed methods demonstrate improved scalability, optimality, and robustness, providing a comprehensive bridge between theoretical MAPF frameworks and practical, deployable multi-robot systems.