A crucial factor that can severely limit the success and performance of Multi-Robot Systems (MRS) is the possibility of collisions among the robots in a deployment. The MRS deployment in real-world applications has increased almost exponentially in recent years. Thus, finding efficient and fast methods to identify collision-free paths for MRS environments becomes very important.A common objective in such applications is to generate a collision-free path for all the vehicles between two points and minimize the total distance covered while reaching the destination. Since these problems are known to be NP-hard (i.e., no classical algorithm can solve the problem in polynomial time), a heuristics-based approach is usually applied to obtain an acceptable solution.We derive a novel Quantum Alternating Operator Ansatz (QAOA) construction for collision-free path planning in MRS deployment. A heuristic approach such as the QAOA is well suited for combinatorial optimization problems that need to satisfy multiple hard constraints. We also derive the approximate resource estimates in terms of universal quantum gates for our QAOA constructions.
A crucial factor that can severely limit the success and performance of Multi-Robot Systems (MRS) is the possibility of collisions among the robots in a deployment. The MRS deployment in real-world applications has increased almost exponentially in recent years. Thus, finding efficient and fast methods to identify collision-free paths for MRS environments becomes very important.A common objective in such applications is to generate a collision-free path for all the vehicles between two points and minimize the total distance covered while reaching the destination. Since these problems are known to be NP-hard (i.e., no classical algorithm can solve the problem in polynomial time), a heuristics-based approach is usually applied to obtain an acceptable solution.We derive a novel Quantum Alternating Operator Ansatz (QAOA) construction for collision-free path planning in MRS deployment. A heuristic approach such as the QAOA is well suited for combinatorial optimization problems that need to satisfy multiple hard constraints. We also derive the approximate resource estimates in terms of universal quantum gates for our QAOA constructions.
This paper tackles the multi-vehicle Coverage Path Planning (CPP) problem, crucial for applications like search and rescue or environmental monitoring. Due to its NP-hard nature, finding optimal solutions becomes infeasible with larger problem sizes. This motivates the development of heuristic approaches that enhance efficiency even marginally. We propose a novel approach for exploring paths in a 2D grid, specifically designed for easy integration with the Quantum Alternating Operator Ansatz (QAOA), a powerful quantum heuristic. Our contribution includes: 1) An objective function tailored to solve the multi-vehicle CPP using QAOA. 2) Theoretical proofs guaranteeing the validity of the proposed approach. 3) Efficient construction of QAOA operators for practical implementation. 4) Resource estimation to assess the feasibility of QAOA execution. 5) Performance comparison against established algorithms like the Depth First Search. This work paves the way for leveraging quantum computing in optimizing multi-vehicle path planning, potentially leading to real-world advancements in various applications.
More and more, multi-robot systems (MRS) are being used for hard tasks like industrial automation, surveillance, and autonomous navigation. Nevertheless, these systems have significant computation difficulties especially in path planning, task distribution and coordination. Quantum computing is capable of computing information based on such concepts as superposition and entanglement. This provides an alternative solution to optimization problems that are more efficient than the conventional methods. A systematic review approach based on PRISMA was used. We used pre-set search terms to look for useful papers in databases including Google Scholar, Scopus, IEEE Xplore, and Web of Science. We found peer-reviewed articles that had come out in the last 10 to 15 years based on some rules for which ones to include and which ones to leave out. A total of thirty papers, mainly focusing on algorithms, applications and constraints were included in qualitative synthesis. The review demonstrated that quantum algorithms, such as the search and QAOA algorithms created by Grover, can be helpful in optimizing the problems of MRS. These methods have the benefits of parallelism and speed. Nevertheless, they are used in simulations only due to the limitations of technology, scaling issues, and integration challenges with real-time robotic system.
Path planning in complex and obstacle-constrained environments remains a challenging combinatorial optimization problem due to the exponential growth of the solution space and the limitations of classical algorithms in dynamic decision-making scenarios. Traditional approaches such as Dijkstra or A* may experience high computational costs and susceptibility to local optima when dealing with large-scale directed graphs containing obstacles. This study proposes a hybrid quantum computing approach that integrates the Grover Search Algorithm and the Quantum Approximate Optimization Algorithm (QAOA) to address optimal path planning on obstacle-oriented directed graphs. The Grover algorithm is first employed as an oracle-based filtering mechanism to detect and eliminate obstacle-containing edges, thereby generating a valid subgraph of feasible paths. Following this preprocessing step, QAOA is applied to the filtered graph within a nonlinear optimization framework to determine the minimum-cost path between source and destination nodes. The optimization model represents the graph as G=(V,E), where binary decision variables indicate whether an edge is included in the selected route while satisfying flow conservation constraints. By narrowing the solution space through Grover-based obstacle detection and performing optimization only on valid edges, the proposed method significantly reduces computational complexity compared to conventional approaches. Experimental analysis demonstrates that the hybrid quantum model effectively identifies optimal routes and adapts to different obstacle configurations while maintaining efficient convergence behavior. The results highlight the potential of integrating quantum search and quantum optimization techniques for solving combinatorial graph problems. This work contributes to the growing body of research on quantum-assisted optimization and demonstrates the feasibility of applying hybrid quantum algorithms to directed path planning problems relevant to autonomous navigation systems.
The increasing availability of quantum hardware has stimulated interest in applying quantum algorithms to combinatorial optimization problems. Collision avoidance for unmanned aerial vehicles (UAVs) is one such challenge due to the computational complexity of coordinating multiple agents in shared airspace. In this paper, we formulate the problem as a Quadratic Unconstrained Binary Optimization (QUBO) model that captures route selection and collision constraints, enabling the use of the Quantum Approximate Optimization Algorithm (QAOA). To improve efficiency, we introduce a constrained QAOA Ansatz employing an XY-mixer that preserves one-hot route assignment constraints and restricts the search space to valid solutions. We evaluate the approach through noiseless simulations and device-based noise models, analyzing its behavior under realistic conditions and highlighting the opportunities and limitations of near-term quantum hardware for multi-agent routing problems.
With the expansion of complex transport infrastructure, new paths for linking different destinations have emerged, allowing the definition of multiple routes. The introduction of new roads may also lead to disruptions in traffic flow. This problem can be generalized into a special case of VRP, which aims to find the optimal route for a fleet of vehicles within a network of destinations. Finding solutions to this problem requires an exponential number of operations, hindering the ability of exact solvers to deal with large instances, which must therefore be tackled using heuristics, often leading to suboptimal results. Quantum-based algorithms may allow us to find exact solutions in polynomial time with high probability, offering a potential future alternative to classical solvers and in this work, we focus on the QAOA. Our novel contributions are a parameter-initialization strategy that improves the convergence probability and the integration of the subtour constraints directly into the optimization without using additional qubits by employing an approximation of exponential equality constraints. We believe that our results pave the way for effectively solving instances of VRP using quantum-based solutions, leveraging the space-efficient problem encoding and our initialization strategy, which limits the effect of barren-plateau under random parameter initialization.
Multi-Agent Path Finding (MAPF) remains a fundamental challenge in robotics, where classical centralized approaches exhibit exponential growth in joint-state complexity as the number of agents increases. This paper investigates Quadratic Unconstrained Binary Optimization (QUBO) as a structurally scalable alternative for simultaneous multi-robot path planning. This approach is a robotics-oriented QUBO formulation incorporating BFS-based logical pre-processing (achieving over 95% variable reduction), adaptive penalty design for collision and constraint enforcement, and a time-windowed decomposition strategy that enables execution within current hardware limitations. An experimental evaluation in grid environments with up to four robots demonstrated near-optimal solutions in dense scenarios and favorable scaling behavior compared to sequential classical planning. These results establish a practical and reproducible baseline for future quantum and quantum-inspired multi-robot coordinations.