\documentclass{article} \usepackage{bookmark} \usepackage{amsmath, amssymb, geometry, fancyhdr} \usepackage{hyperref} \geometry{margin=1in} \pagestyle{fancy} \fancyhf{} \lhead{\textbf{Welcome to our Flask Application!}} \rhead{\textbf{Enter your inputs:}} \chead{\textbf{Submit Prediction Result}} \cfoot{\thepage}  \begin{document}  \section*{Collision Definition in Grid-Based Multi-Agent Path Finding}  In the context of \textbf{Multi-Agent Path Finding (MAPF)} on grid graphs, a \emph{collision} occurs when two or more agents interfere with each other's movements, violating the constraints of the environment or the rules of agent interaction. Specifically, collisions are typically defined in two primary ways:  \begin{enumerate}     \item \textbf{Vertex Collision (Node Collision)}:     \begin{itemize}         \item Occurs when two or more agents occupy the same grid cell (\textbf{vertex}) at the same time step.         \item This violates the rule that only one agent can occupy a grid cell at any given time.     \end{itemize}     \item \textbf{Edge Collision (Swap Collision)}:     \begin{itemize}         \item Happens when two agents concurrently move into each other's positions, effectively swapping places over an edge.         \item This is considered a collision because the agents pass through the same edge in opposite directions simultaneously.     \end{itemize} \end{enumerate}  These collision definitions are crucial for ensuring that agents navigate the grid without interfering with each other, maintaining safety and efficiency in their paths.  \section*{Collision Avoidance Strategies in the Literature}  The literature on MAPF offers a variety of collision avoidance strategies aimed at efficiently computing collision-free paths for multiple agents on grid graphs. These strategies can be broadly categorized into centralized, decentralized, and hybrid approaches. Below is an overview of the key strategies:  \subsection*{1. Centralized Planning Methods}  These methods consider the paths of all agents simultaneously within a single planning process.  \subsubsection*{a. Conflict-Based Search (CBS)} \begin{itemize}     \item \textbf{Overview}: CBS is a two-level algorithm with a high-level search that resolves conflicts and a low-level search that finds optimal paths for individual agents.     \item \textbf{Collision Avoidance}: When a collision is detected, CBS creates constraints to prevent the collision and branches the search into subproblems where these constraints are enforced.     \item \textbf{Pros}: Optimal and complete for cooperative settings.     \item \textbf{Cons}: Computationally intensive for large numbers of agents. \end{itemize}  \subsubsection*{b. Increasing Cost Tree Search (ICTS)} \begin{itemize}     \item \textbf{Overview}: ICTS searches over the combinations of individual agents' paths that collectively satisfy the cost constraints.     \item \textbf{Collision Avoidance}: Generates candidate paths for each agent and combines them while avoiding collisions.     \item \textbf{Pros}: Can be more efficient than exhaustive search.     \item \textbf{Cons}: May not scale well with the number of agents. \end{itemize}  \subsubsection*{c. Enhanced Partial Expansion A* (EPEA*)} \begin{itemize}     \item \textbf{Overview}: An extension of the A* algorithm that efficiently handles multiple agents.     \item \textbf{Collision Avoidance}: Generates nodes only when they can lead to a solution, reducing the number of expansions.     \item \textbf{Pros}: Reduces computational overhead.     \item \textbf{Cons}: Still suffers from scalability issues in dense environments. \end{itemize}  \subsubsection*{d. M$^*$ (Modified A$^*$)} \begin{itemize}     \item \textbf{Overview}: M$^*$ modifies the A$^*$ algorithm to handle multiple agents by combining their searches when their paths intersect.     \item \textbf{Collision Avoidance}: Plans paths for agents independently until a potential conflict arises, then coordinates paths to resolve collisions.     \item \textbf{Pros}: Focuses computational effort where it's needed.     \item \textbf{Cons}: Complexity increases with the number of interactions between agents. \end{itemize}  \subsection*{2. Decentralized Planning Methods}  Agents plan their paths independently or with limited coordination.  \subsubsection*{a. Priority-Based Planning} \begin{itemize}     \item \textbf{Overview}: Assigns priorities to agents; higher-priority agents have right-of-way over lower-priority ones.     \item \textbf{Collision Avoidance}: Lower-priority agents adjust their paths to avoid conflicts with higher-priority agents.     \item \textbf{Pros}: Simple and efficient for certain scenarios.     \item \textbf{Cons}: Suboptimal paths for lower-priority agents; potential for deadlocks or livelocks. \end{itemize}  \subsubsection*{b. Local Repair Strategies} \begin{itemize}     \item \textbf{Overview}: Agents plan paths independently and locally repair them when collisions are detected.     \item \textbf{Collision Avoidance}: Uses online collision detection and replanning to adjust paths dynamically.     \item \textbf{Pros}: Scalable; good for dynamic environments.     \item \textbf{Cons}: May not find optimal paths; potential for oscillations. \end{itemize}  \subsubsection*{c. Reciprocal Collision Avoidance (e.g., ORCA)} \begin{itemize}     \item \textbf{Overview}: Each agent predicts the future positions of other agents and adjusts its velocity to avoid collisions.     \item \textbf{Collision Avoidance}: Uses velocity obstacles and linear programming to compute collision-free velocities.     \item \textbf{Pros}: Efficient computation; no central coordination.     \item \textbf{Cons}: Assumes perfect sensing and prediction; may not handle complex interactions well. \end{itemize}  \subsection*{3. Hierarchical and Hybrid Methods}  Combining different planning levels or methods to improve performance.  \subsubsection*{a. Hierarchical Cooperative Multi-Agent Pathfinding (HiCMPF)} \begin{itemize}     \item \textbf{Overview}: Breaks down the planning process into hierarchical levels, typically global and local planning.     \item \textbf{Collision Avoidance}: High-level plans provide guidelines, while low-level planners handle collision avoidance.     \item \textbf{Pros}: Balances between optimality and computational efficiency.     \item \textbf{Cons}: Complexity in designing appropriate hierarchy levels. \end{itemize}  \subsubsection*{b. Combining Global and Local Planning} \begin{itemize}     \item \textbf{Overview}: Uses global planners to find approximate paths and local planners to refine them and avoid collisions.     \item \textbf{Collision Avoidance}: Global paths are adjusted locally to resolve conflicts.     \item \textbf{Pros}: Scalable and adaptable.     \item \textbf{Cons}: May not guarantee optimality. \end{itemize}  \subsection*{4. Reservation-Based Methods}  Agents reserve nodes and edges in a time-space graph.  \subsubsection*{a. Time-Expanded Networks} \begin{itemize}     \item \textbf{Overview}: Constructs a time-space graph where each node represents a location at a specific time.     \item \textbf{Collision Avoidance}: Ensures that no two agents occupy the same node or edge at the same time.     \item \textbf{Pros}: Can find optimal paths considering time.     \item \textbf{Cons}: Large memory requirements due to graph expansion. \end{itemize}  \subsubsection*{b. Reservation Tables} \begin{itemize}     \item \textbf{Overview}: Agents reserve time slots for moving through nodes and edges.     \item \textbf{Collision Avoidance}: Other agents avoid reserved slots when planning their paths.     \item \textbf{Pros}: Simple implementation; reduces collisions.     \item \textbf{Cons}: Can lead to inefficiencies if agents hold reservations they no longer need. \end{itemize}  \subsection*{5. Safe Interval Path Planning (SIPP)}  \begin{itemize}     \item \textbf{Overview}: Extends the idea of time-expanded planning by considering ``safe intervals'' during which a node is free.     \item \textbf{Collision Avoidance}: Agents plan paths through these intervals, ensuring they don't enter nodes during unsafe times.     \item \textbf{Pros}: Reduces the size of the time-expanded graph; efficient for certain scenarios.     \item \textbf{Cons}: Complexity increases with dynamic obstacles. \end{itemize}  \subsection*{6. Multi-Agent Reinforcement Learning (MARL)}  \begin{itemize}     \item \textbf{Overview}: Agents learn policies through trial-and-error interactions with the environment and other agents.     \item \textbf{Collision Avoidance}: Agents receive negative rewards for collisions, encouraging them to find collision-free paths.     \item \textbf{Pros}: Can handle complex, dynamic environments.     \item \textbf{Cons}: Requires extensive training; may not guarantee optimality. \end{itemize}  \subsection*{7. Swarm Intelligence and Bio-Inspired Algorithms}  \begin{itemize}     \item \textbf{Overview}: Agents follow simple rules inspired by natural swarms (e.g., flocks of birds).     \item \textbf{Collision Avoidance}: Rules like separation, alignment, and cohesion guide agents to avoid collisions naturally.     \item \textbf{Pros}: Scalable; robust against individual failures.     \item \textbf{Cons}: Difficult to control precise agent behavior; may not suit all applications. \end{itemize}  \subsection*{8. Deadlock Avoidance Strategies}  \begin{itemize}     \item \textbf{Overview}: Specific strategies to prevent deadlocks that arise due to collision avoidance maneuvers.     \item \textbf{Collision Avoidance}: Incorporates rules or algorithms (e.g., token passing) to ensure progress.     \item \textbf{Pros}: Improves system reliability.     \item \textbf{Cons}: May add complexity to the planning process. \end{itemize}  \subsection*{9. Constraint-Based Programming}  \begin{itemize}     \item \textbf{Overview}: Models the MAPF problem as a Constraint Satisfaction Problem (CSP) or Integer Linear Program (ILP).     \item \textbf{Collision Avoidance}: Encodes collision constraints that must be satisfied.     \item \textbf{Pros}: Can find optimal solutions; flexible modeling.     \item \textbf{Cons}: Computationally intensive for large problems. \end{itemize}  \subsection*{10. Lifelong Planning and Replanning Algorithms}  \begin{itemize}     \item \textbf{Overview}: For environments where agents have continuous or recurring tasks.     \item \textbf{Collision Avoidance}: Continuously updates paths as new information or tasks arise.     \item \textbf{Pros}: Adaptable to changes.     \item \textbf{Cons}: Complexity in maintaining up-to-date plans for all agents. \end{itemize}  \section*{Conclusion}  Collision avoidance in grid-based MAPF is a well-researched area with numerous strategies tailored to different requirements such as optimality, computational efficiency, scalability, and adaptability to dynamic environments. The choice of collision avoidance strategy often depends on the specific application, number of agents, environmental complexity, and performance criteria.  \section*{References for Further Reading}  \begin{itemize}     \item Silver, D. (2005). \emph{Cooperative Pathfinding}. Proceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment.     \item Sharon, G., Stern, R., Felner, A., \& Sturtevant, N. R. (2015). \emph{Conflict-Based Search for Optimal Multi-Agent Pathfinding}. \emph{Artificial Intelligence}, 219, 40--66.     \item Van den Berg, J., Guy, S. J., Lin, M., \& Manocha, D. (2011). \emph{Reciprocal n-body collision avoidance}. \emph{Robotics Research}, 3--19.     \item Wagner, G., \& Choset, H. (2015). \emph{Subdimensional Expansion for Multirobot Path Planning}. \emph{Artificial Intelligence}, 219, 1--24. \end{itemize}  \end{document}