Core Challenges for Multi-Robot-Path-Planning Algorithms: History
View Latest Version
Please note this is an old version of this entry, which may differ significantly from the current revision.
Contributor:
James R. Heselden
,
Gautham P. Das

The benefits of multi-robot systems are substantial, bringing gains in efficiency, quality, and cost, and they are useful in a wide range of environments from warehouse automation, to agriculture and even extend in part to entertainment. In multi-robot system research, the main focus is on ensuring efficient coordination in the operation of the robots, both in task allocation and navigation. However, much of this research seldom strays from the theoretical bounds; there are many reasons for this, with the most-prominent and -impactful being resource limitations. This is especially true for research in areas such as multi-robot path planning (MRPP) and navigation coordination. This is a large issue in practice as many approaches are not designed with meaningful real-world implications in mind and are not scalable to large multi-robot systems. 

  • coordination
  • multi-robot path planning (MRPP)
  • multi-agent path finding

1. Introduction

Robotics, automation, and artificial intelligence (AI) have a great influence on many domains that traditionally relied on the human workforce. By replacing human-based roles with robotics and AI-based tools designed solely for the task, able to work with less error and fatigue and with enhanced communication speed and cooperation, the throughput of businesses can be increased along with the quality of the goods produced. With higher-quality automation and decreasing costs for robots, the potential for autonomous systems has soared. As these trends continue, more systems will see much more mass automation [1]. With these developments and the need to address wider spatial contexts, multi-robot systems (MRSs) have seen a significant increase in their use over the last decade. An example of the benefits of MRS was shown in [2], where strawberry harvesting logistics were improved by 20–30% with the use of autonomous robots to deliver fruit from pickers to storage. MRSs have already seen promising development in fully autonomous coordination such as in warehouses [3], agriculture [4], search and rescue [5], and drone shows [6].
A large factor impacting the effective deployment of MRSs is multi-robot path planning (MRPP), being the ability to define paths each robot should take through the environment from its location to its respective goal, which both minimises the total distance each robot takes through the network and, more importantly, avoids all potential collisions with other robots. MRPP research overlaps with multi-agent path finding (MAPF) in multi-agent system (MAS) research, which is defined as the problem of finding paths for multiple agents such that every agent reaches its goal and the agents do not collide. The discussions in this survey are relevant to both MRPP and MAPF.
Different environmental representations have been used in MRPP research. Continuous space metric map representations have been used for local trajectory planning of multi-robot systems [7][8]. However, the computational complexity of considering a continuous space for MRPP is prohibitively high for large environments, even for a small MRS. To enable efficient planning in large environments, most of the existing MRPP algorithms have used discretised environmental representations. A grid representation of the environment, with each cell connected to four neighbouring cells, has been used for different MRPP algorithms [9]. More recently, a discrete topological perspective of the environment is the most-commonly used discrete environment representation in MRPP. In this topological perspective, the environment is modelled as a graph or network with nodes identifying key points and edges describing how these points connect to one another, and this utility effectively describes the navigable connections between spaces in which the robot can move. With the utilisation of these representations, the complexity of the space is minimised to only the aspects of key importance and allows MRPP algorithms to work more efficiently such as in [10], though the planning can be performed without such a map, instead opting for the use or metric representations, such as in [11], despite a trade-off in scalability.
Even with the topological representation of the environment, MRPP has been proven to be NP-hard [12], wherein the joint state space grows exponentially as the complexity increases, with the complexity increasing alongside either the total number of robots or the size of the map. This means that finding optimal routes through a topology requires more processing resources or time, as there are more options and possibilities that must be explored. This restricts the scalability and, thus, deployment of large MRSs in potentially congested spaces or domains.
The purpose and contributions of this survey are focused on three aims. First, and primarily, is to consolidate the variety of prioritised multi-robot-path-planning approaches and the rationale behind them to form a single, referable source from which researchers can begin their study in this area. Second is to identify areas within the space of prioritised planning that warrant further exploration. Many approaches use simulations for their development; thus, there is potential for further development when considered in practice for physical robots. Third is to identify and provide solutions for common weaknesses in the evaluation methodologies, which otherwise limit the transferability of efficacy into actual deployments.
There has been extensive research on multi-robot systems and the efficient coordination among robots within a system, with some overlap in the focus areas of research between multi-robot systems and multi-agent systems, where multi-agent systems can consider agents as physical (such as robots or humans), software (as in simulated or projected robots), or general constructs (of mobile or stationary entities); these may not contain any robots at all. Multi-robot systems exclusively consider robots as the agents. In the context of this survey, consider the terms robot and agent to be synonymous. Similarly, as many of the MRPP approaches discussed in this survey rely on explicit communications between the robots, multi-robot networks and networks are used as synonymous with MRSs.
Similarly, domains that have vastly different contexts share the same or similar research challenges, and the algorithms developed for a specific context in one domain may also be applicable in another domain. For instance, agricultural transportation logistics [10] and pipe routing [13] are both capable of utilising versions of prioritised planning implementations to optimise path assignments to individual robots. 

2. Core Challenges for Multi-Robot-Path-Planning Algorithms

While developing an MRPP algorithm, many design challenges need to be addressed. Often, these challenges are mutually exclusive, with one or more other constraints failing when the MRPP algorithm is designed to conform to one constraint. A short description of the five main challenges to MRPP is given below.

2.1. Completeness

In MRPP solutions, the main aim is to find a set of routes that the robots within an MRS may use to reach their respective targets, subject to some constraints. Whilst it is often a guarantee that such a set of assignments may exist, it is not always possible to find it [12]. Completeness, the most-important challenge faced by MRPP approaches, is used to define whether an approach can guarantee that, if a solution exists that allows all agents to reach their targets, it will be identified.

2.2. Optimality

For any collection of robots, their start locations, and the targets, there is always an optimal collective route, that is the collection of routes that each robot can take in order to minimise a collective objective measured by a metric such as the total distance travelled by all robots through the network [11]. The metric chosen is most commonly either the make-span (time the last robot arrives) or flow-time (sum of all route lengths). The key idea is that there is some optimal assignment of routes that can be matched, but cannot be beaten.
Optimality refers to the ability of the MRPP algorithm to guarantee the identification of an optimal solution given enough computing time, i.e., the ability to find the optimal route from the start to the target given such a route exists. This is an issue on which much of the research on MRPP is focused, as the computational complexity of finding the optimal route is much higher.

2.3. Deadlocks

Deadlock situations are a significant concern for MRPP solutions and deployments. Deadlocks refer to a situation in which a robot is unable to find a route through the environment because it is trapped by another robot. Often, this is caused by planning inefficiencies such as the incorrect assessment of priorities or sub-optimal waiting points. In [14], the authors designed an abstract concept detailing the causes of deadlocks, which they used to evaluate the efficacy of a range of prioritised planning approaches. While their aim was to detail specifically prioritised planning issues, the theory can be extended beyond this. They summarised the causes of deadlocks into two key situations. In the first, the cause of the deadlock is the result of the high-priority robot lying in the path required by a low-priority robot, and in the second situation, the cause is a high-priority robot following behind a low-priority robot.
Papers such as [15] have attempted to resolve these common types of deadlocked situations using methods that discourage navigation around the initial movement areas of other agents. These methods, while simple, are effective at managing many causes of deadlocks.
While not as prevalent of an issue, approaches must also ensure they do not fall into the risks of livelock (i.e., robots circle around one another and are unable to move forward) and starvation (where resources, such as nodes of special interest, are locked up under different processes) as these can also be critical problems for a deployed system.

2.4. Scalability

The largest challenge to the successful deployment of an MRS is its scalability, where the performance is not degraded with an increase in the size of the MRS or the working environment. The grand aim of a MRS is to have many robots coordinating and working fully autonomously for long periods of time. There are three primary components that impact the scalability: the size of the map, the number/length of tasks, and the quantity of robots. As these grow, the complexity of the joint state space increases with them at an exponential rate due to more data requiring processing and more situations that need evaluation. This type of growth leads to a slower processing of the system overall [12].
Effective approaches to combat this are the utilisation of distributed and decentralised deployments. These can help unburden a centralised coordination system that would otherwise be handling all the processing by itself [16]. This, however, comes with other scalability problems such as communication or synchronisation overheads.
Decentralisation is effective at spreading the workload; however, it is not enough alone; the processing requirement is only divided by the total number of decentralised processors. So, if the number of robots exceeds the capacity for a decentralised unit, the coordination must be decentralised further so that the number of robots per processor is stable.
Distributed processing is used widely with autonomous robots, where even if the primary coordination system is centralised, the elements of the motion planning can be run locally for each agent. For instance, an agent can be given a simple goal or path from the coordination system, allowing it to compute its own motion trajectories. This type of offloading allows for scalability issues to be lessened as a minimal amount of information needs to be computed centrally. With the full utilisation of distributed coordination, robots can make all decisions themselves utilising technologies such as swarm behaviour or potential fields [17].

2.5. Communication

Communication is another challenge within MRSs that must be overcome. In any MRPP approach, there must be a method for robots to share information, either via a wireless data connection or via physical observations of their environment. Without such channels, agents in centralised or decentralised systems are unable to plan/share their routes, and agents in distributed systems are unable to share their intentions about their movements.
This challenge can have critical impacts on not just the efficiency of a system, but also on safety. If communications slow down too much and processing takes too long, hazards can appear and become critical before the coordinator has time to react and recalculate the routes. This is especially troublesome in MRSs involving both robots and humans sharing the same workspace, where even though local navigation can work to avoid direct collisions, robots suddenly moving in unexpected manners can cause accidents indirectly.
When utilising wireless data communication, which is the most-common approach, it is important to understand the coupling between the robots and the environment. Many aspects of the environment can impact the reliability of such a system. Many materials can have significant impacts on the quality of wireless signals: stone walls for caving/mining robots or metal infrastructure in warehouses/factories can significantly impact the reliability of wireless technologies, and the radiation in nuclear decommissioning can prevent any signals from passing through. In outdoor environments such as for agricultural robots, the reliability of 4G is not always guaranteed, and even in a well-suited environment such as an office or school, issues such as blackouts and bandwidth limitations can also occur [18]. In real-world settings, there are many elements that can cause communication issues and are easily overlooked when solely working in simulation.
Communication overhead scales linearly with the number of agents in a system where the agents are only required to communicate with the coordinator; however, when the robots are all communicating their locations in a distributed manner without the use of a central coordinator, this can result in much communication processing for each robot and each coordinator, and if they must process much information with each communication, there is also potential for error accumulation [17]. Many coordination issues can arise if a piece of information, such as a robot’s location, is sent, but becomes delayed or corrupted or is inaccurate, even if it is eventually received.

This entry is adapted from the peer-reviewed paper 10.3390/machines11111033

References

  1. Rizk, Y.; Awad, M.; Tunstel, E.W. Cooperative Heterogeneous Multi-Robot Systems: A Survey. ACM Comput. Surv. 2019, 52, 2.
  2. Das, G.P.; Cielniak, G.; From, J.; Hanheide, M. Discrete Event Simulations for Scalability Analysis of Robotic In-Field Logistics in Agriculture—A Case Study. In Proceedings of the ICRA 2018 Workshop on Robotic Vision and Action in Agriculture, Brisbane, Australia, 21–25 May 2018.
  3. Fernandez Carmona, M.; Parekh, T.; Hanheide, M. Making the Case for Human-Aware Navigation in Warehouses. In Towards Autonomous Robotic Systems; Althoefer, K., Konstantinova, J., Zhang, K., Eds.; Springer: Cham, Switzerland, 2019; pp. 449–453.
  4. Bechar, A.; Vigneault, C. Agricultural robots for field operations: Concepts and components. Biosyst. Eng. 2016, 149, 94–111.
  5. Drew, D.S. Multi-agent systems for search and rescue applications. Curr. Robot. Rep. 2021, 2, 189–200.
  6. O’Malley, J. There’s no business like drone business . Eng. Technol. 2021, 16, 72–79.
  7. Wen, T.; Wang, X.; Sun, Z.; Zheng, Z.; Kong, X. An Adaptive Local Path Planning Algorithm for Multi-robot Systems. In Proceedings of the 2022 IEEE International Conference on Unmanned Systems (ICUS), Guangzhou, China, 28–30 October 2022; pp. 817–822.
  8. Andreychuk, A.; Yakovlev, K.; Atzmon, D.; Stern, R. Multi-Agent Pathfinding with Continuous Time. In Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence, IJCAI-19, International Joint Conferences on Artificial Intelligence Organization, Macao, China, 10–16 August 2019; pp. 39–45.
  9. Walker, T.T.; Sturtevant, N.R.; Felner, A. Extended Increasing Cost Tree Search for Non-Unit Cost Domains. In Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, IJCAI-18, International Joint Conferences on Artificial Intelligence Organization, Stockholm, Sweden, 13–19 July 2018; pp. 534–540.
  10. Heselden, J.R.; Das, G.P. CRH*: A Deadlock Free Framework for Scalable Prioritised Path Planning in Multi-robot Systems. In Proceedings of the Annual Conference Towards Autonomous Robotic Systems, Lincoln, UK, 8–10 September 2021; Springer: Cham, Switzerland, 2021; pp. 66–75.
  11. Wu, W.; Bhattacharya, S.; Prorok, A. Multi-Robot Path Deconfliction through Prioritization by Path Prospects. arXiv 2019, arXiv:1908.02361.
  12. Yu, J.; LaValle, S. Structure and intractability of optimal multi-robot path planning on graphs. In Proceedings of the AAAI Conference on Artificial Intelligence, Bellevue, WA, USA, 14–18 July 2013; Volume 27.
  13. Belov, G.; Du, W.; De La Banda, M.G.; Harabor, D.; Koenig, S.; Wei, X. From multi-agent pathfinding to 3D pipe routing. In Proceedings of the Thirteenth Annual Symposium on Combinatorial Search, Online, 26–28 May 2020.
  14. Dewangan, R.K.; Shukla, A.; Godfrey, W.W. Survey on prioritized multi robot path planning. In Proceedings of the 2017 IEEE International Conference on Smart Technologies and Management for Computing, Communication, Controls, Energy and Materials (ICSTM), IEEE, Chennai, India, 2–4 August 2017; pp. 423–428.
  15. Cap, M.; Novak, P.; Kleiner, A.; Selecky, M. Prioritized Planning Algorithms for Trajectory Coordination of Multiple Mobile Robots. IEEE Trans. Autom. Sci. Eng. 2015, 12, 835–849.
  16. Mao, W.; Liu, Z.; Liu, H.; Yang, F.; Wang, M. Research progress on synergistic technologies of agricultural multi-robots. Appl. Sci. 2021, 11, 1448.
  17. Soni, A.; Hu, H. Formation control for a fleet of autonomous ground vehicles: A survey. Robotics 2018, 7, 67.
  18. Prorok, A.; Malencia, M.; Carlone, L.; Sukhatme, G.S.; Sadler, B.M.; Kumar, V. Beyond robustness: A taxonomy of approaches towards resilient multi-robot systems. arXiv 2021, arXiv:2109.12343.
More
© Text is available under the terms and conditions of the Creative Commons Attribution (CC BY) license; additional terms may apply. By using this site, you agree to the Terms and Conditions and Privacy Policy.
This entry is offline, you can click here to edit this entry!
Video Production Service
Feedback