MTU-LLM: LLM-based Multi-Robot Task Allocation and Path Planning for Heterogeneous Robots in Search and Rescue Operations

MRTA and path planning in USAR applications

The MRTA and path planning are critical yet challenging areas in robotics, requiring sophisticated coordination among robot teams and intelligent task distribution within MRSs. In recent years, there has been increased interest in developing novel strategies for these problems in SAR applications. Figure 1 provides an illustration of various MRS efforts in SAR applications and some state-of-the-art LLM-based approaches.

Many existing approaches for SAR applications that use robot teams employ centralized methods for task allocation. For instance, Surmann et al. [7] proposed a centralized path planning approach for a heterogeneous MRS involving unmanned aerial vehicles (UAVs). This work introduced a framework for path planning and 3D mapping by integrating UAVs in SAR missions. The platform in this work uses a complete sensor suite that enables 3D mapping, object detection, and scene inference of the affected areas using aerial robots, thereby providing a thorough initial assessment of the environment. Myeong et al. [8] introduced a strategy that uses fireproof UAVs for USAR applications involving fires. This work elaborates on effectively using these robots for mapping missions and providing valuable insight into trapped victims and the severity of the injuries in the impacted environment. In other significant contributions, Konyo et al. [9] demonstrated a thin serpentine robot platform capable of maneuvering itself in convoluted and crammed environments such as collapsed structures. The robot was designed to be up to 10 m long and extremely agile, with the ability to localize itself through visual SLAM. Zhao et al. [10] proposed a centralized task allocation approach that used heterogeneous robot teams to find survivors for SAR applications.

Although these centralized approaches offer valuable insights, they often lack flexibility and scalability in complex, dynamic SAR environments. To address these limitations, some researchers have explored distributed strategies. For example, Hussein et al. [11] presented a distributed strategy involving a market-based approach, which was formulated as a traveling salesman problem. This algorithm was applied to real robots and simulated victim locations. The robots had to divide themselves and reach the victims, providing optimal solutions. However, some downsides of the approach were scalability with an increased number of robots/victims and the run time complexity of the algorithm.

Decentralized approaches have also been proposed such as those by Mouradian et al. [12], who used multi-objective optimization, which is based on robot-to-robot communication, for effective task allocation and path planning. Osooli et al. [13] introduced a Multi-Stage Multi-Robot Task Assignment (MSMRTA) framework combining scouting, task allocation, and path planning stages using a communication-independent ant colony approach for scouting.

Despite these advancements, existing approaches often suffer from limited environmental coverage and are typically tailored to specific applications. Their constraints in scalability and adaptability to complex, nuanced environments underscore the need for more versatile MRTA approaches that can handle diverse problem constraints and environments with minimal modifications.

LLM-based approaches for MRSs

Recent developments in LLMs like GPT-4, Llama, and Gemini have demonstrated exceptional capabilities in scalability and common-sense reasoning. This has led to growing interest in leveraging LLMs for MRTA and path planning in MRSs.

Kannan et al. [14] introduced a framework called SMART-LLM, which uses a few-shot LLM prompting to execute a set of tasks sequentially, namely task decomposition, coalition formation, and task allocation. The SMART-LLM framework demonstrates promising results on a benchmark dataset comprising simple as well as complex tasks across different language models. Song et al. [15] leveraged LLMs as a planner for embodied agents attempting to handle complex tasks. Their work shows great promise for developing versatile and sample-efficient agents that can quickly adapt and perform new tasks. Similarly, Wang et al. [16] leveraged the powerful reasoning and planning capabilities of pre-trained language models for Conventional Task and Motion Planning, using prompting to incorporate motion planning feedback and reason about failures. The applicability of their work and results in real-world settings unlocks the huge potential of LLMs for practical applications.

Although these LLM-based approaches show great potential, they do not fully address key challenges around reliability and scalability in real-world scenarios. Most existing research relies heavily on pre-trained data and works only in limited real-world settings. Crucially, there is a significant gap in research applying LLMs specifically to SAR applications. To address these limitations, our work introduces Multi-robot Task allocation Utilizing LLMs (MTU-LLM) as a zero-shot prompt engineering technique for SAR operations. We focus on task allocation and path planning for heterogeneous robot teams, considering diverse robot capabilities. Our proposed method aims to provide a scalable and generalized solution for effective robot coordination in dynamic SAR environments, leveraging the adaptive reasoning capabilities of LLMs to overcome the limitations of traditional approaches.

By utilizing LLMs, we aim to create a more flexible and context-aware system that can rapidly adapt to the unpredictable nature of SAR scenarios, potentially revolutionizing how we approach MRTA and path planning in these critical applications. This approach not only addresses the scalability and adaptability issues of existing methods but also opens new avenues for integrating advanced AI capabilities into robotic SAR operations.

Overview

In this section, we describe MTU-LLM, which utilizes LLMs such as GPT-4o [17] to perform a two-stage zero-shot task allocation and path planning for the team of robots in an SAR scenario. The proposed framework is illustrated in Figure 2. The proposed approach performs clustering, task allocation, and routing for the set of robots in the SAR environment. We employ Natural Language Prompts (NLPs) that guide the LLM in generating executable code for the task allocation and path planning steps. The choice of NLP is intentional because it is easily readable and executable by a human. However, we still incorporate a meaningful structure to the prompts so that they can be easily inferred and interpreted by the LLM. In addition, we also provide examples to the LLM along with meaningful comments to help the LLM understand and generate the code efficiently.

Prompt engineering approach

We employ the LLM prompts in two stages: (1) MRTA and (2) path planning. While the overall approach works on the notion of zero-shot prompting, we compartmentalize the prompts into task allocation and path planning sections for a couple of reasons. First, task allocation can be a complex task in itself, especially with an increase in the dimensionality of the problem statement. Second, after continuous and iterative refinement of the prompts over time, it was observed that having task allocation as a standalone task reduces the complexity of the prompts and positively impacts the consistency of the output generated by the LLM. Once the LLM has generated the tasks for the robots and ensured that the task allocation involving the victims is feasible, the path planning prompts complement the task allocation prompts. Thereafter, the output of the task allocation prompts can be seamlessly used by the LLM to generate feasible paths for the robots.

Experimental setup

We use GPT-4o as the backbone for MTU-LLM. The Python script generated by this model is evaluated offline, and the approach is further validated using simulations performed across a range of problem sizes. The simulations are performed on a workstation with the Apple M2 Chip and 8 GB RAM. The experiments involve varying the number of robots from 2 to 10 and the number of victims ranging from 10 to 100. For each combination of state space, 100 iterations are executed. The environment map is defined as a 2D grid map as illustrated in Figure 3 and remains the same across all simulation runs. The robots are considered to be heterogeneous, each possessing a set of capabilities and unique characteristics. For the purpose of simplicity, the average running speed of all the robots is assumed to be the same, and the victims are all assumed to have the same severity rating. Table 1 presents the robot and victim characteristics that are used for the simulation along with the simulation parameters that are applied.

Additionally, we compare our results with Hamid et al.’s [13] MSMRTA algorithm, which is used as the baseline. The baseline is also evaluated on the same set of parameters, environment, constraints, and metrics.

Evaluation metrics

We use five distinct metrics to evaluate the performance and feasibility of the solutions generated by our approach and compare them against the baseline.

The performance metrics focus on evaluating how well the solution generated by the algorithm fares in terms of task completion rate, computation time, and travel cost. For this purpose, we employ the following three metrics:

1. (1)

   Travel cost: This measures the distance traveled or time taken by each robot to complete its task. The aim is to minimize this metric to improve performance.

2. (2)

   Average workload balance score: It is a measure of how well the tasks are balanced among the robots. Even though task allocation for the problem approached in this paper is largely dependent on matching robot capabilities to victim requirements, this is a useful metric that can indicate how well the LLM maximizes the opportunity to balance the workload when several options exist. It is represented as a normalized score between 0 and 1, where 1 indicates perfect balance.

3. (3)

   Computation time: This measures the algorithm’s computation time to find a solution and is a useful metric when drawing comparisons with other works in this domain.

Additionally, feasibility metrics are focused on evaluating whether the solution generated by the algorithm respects the problem constraints and produces appropriate task allocations. For this purpose, we employ the following two metrics:

1. (1)

   Full Requirement Fulfillment Percentage: Evaluate whether the capabilities of each robot match the requirements of the corresponding victims.

2. (2)

   Partial Requirement Fulfillment Percentage: Given that partial fulfillment is allowed, we also employ another metric that indicates partially fulfilled requirements by robots.

Comparison with baseline using GPT-4o as the backbone

The performance and feasibility of the MRTA approaches are presented in this section, illustrating the MSMRTA baseline through Figure 4 (for even number of robots) and Figure 5 (for odd number of robots). The MTU-LLM results are represented in Figures 6 and 7 for even and odd numbers of robots, respectively. The MTU-LLM demonstrates a significant improvement in computational efficiency, with a tenfold reduction in average computation time compared to the baseline. Furthermore, MTU-LLM consistently achieves higher requirement fulfillment percentages across all robot–victim count combinations.

The problem was deliberately structured to prevent maximum requirement fulfillment for robot counts below 8, with only the eighth robot possessing capabilities to meet certain victim requirements. This design served to identify any false positives in victim allocation during simulations. The lower requirement fulfillment percentage observed for robot counts less than 8 indicates feasible robot–victim matching without violating the specified task allocation constraints. The MTU-LLM successfully generated viable solutions, maximizing victim allocation while adhering to the given constraints. In the context of SAR operations, the efficient utilization of robot capabilities without false allocations is crucial, as timely and appropriate resource allocation to victims is of paramount importance. Notably, even without an explicit workload balance constraint, MTU-LLM outperformed the baseline in terms of workload distribution.

To further investigate this aspect, workload balance was introduced as an additional constraint in the LLM prompt, and updated Python scripts were generated. While the original LLM prompt yielded workload balance scores ranging from 0.2 to 0.6 across all robot–victim count combinations, the updated script with the workload balance constraint significantly improved scores for victim counts exceeding 40 as depicted in Figures 8 and 9. A workload balance score of 1 indicates perfect balance, but it is often hard to achieve for applications utilizing heterogeneous MRSs. The workload balance score is dependent on the characteristics of the robots, the needs of the victims, and the constraints that are defined for the tasks. For example, a robot with a unique capability of possessing a “fire extinguisher” will inevitably be assigned to all victims who are in need of this capability. The task distribution among the robots is designed to prioritize requirement fulfillment while maximizing workload balance.

Table 2 provides a comparison of the feasibility and performance metrics for a subset of robot–victim combinations. It can be observed that MTU-LLM consistently has significantly lower mean and maximum computation times than the MSMRTA baseline across all scenarios. The difference is very prevalent, especially for larger problem sizes such as 10 robots and 100 victims. The mean computation time for MTU-LLM is 0.033 s compared to 0.596 s for the baseline, indicating that MTU-LLM is far more computationally efficient than the baseline, even for large problem sizes. The MTU-LLM also achieves a higher or equivalent requirement fulfillment for all cases. For scenarios with eight or more robots, MTU-LLM achieves a 100% requirement coverage, whereas the baseline lags behind (e.g., 10 robots and 50 victims: 100% vs 72%). Moreover, MTU-LLM produces higher workload balance scores, with a strong indication of better distribution of tasks among robots with similar capabilities. The workload scores for MSMRTA are significantly low for some cases, which suggests that the baseline results in uneven task distribution among robots.

The results demonstrate MTU-LLM’s capability to handle task allocation and path planning tasks, even with large problem sizes and increased complexity. The performance and feasibility metrics suggest the effectiveness of our approach while strictly adhering to the specified problem constraints.

Case studies

In Figure 10, we show an example output of MTU-LLM (with GPT-4o as the backbone) illustrating the path chosen for each robot to reach the victims. For the purpose of demonstration, we consider 4 robots and 10 victims for this case study. The subplots and the subtext in this figure also represent the order in which the robots visit the victims in this environment. It can be observed that the robots meet all path planning constraints that are specified by the LLM prompt, and the approach generates feasible paths to reach victims without colliding with obstacles or walls along the way. It is worth noting that the problem was intentionally designed to have victim requirements that no robot can meet given a lack of robot capabilities. In this case study, “fire extinguisher” is the capability none of the robots possess. The LLM output is quite precise regarding recognizing the deficit in capabilities, and the allocations are provided in the output table in Figure 11. Furthermore, the problem does not have workload balance as an additional constraint. It can be seen from Figure 8 that the victims are correctly assigned to the given robots using clustering and distance-based bidding approaches. Overall, the output of MTU-LLM demonstrates consistency as well as accuracy in generating feasible solutions to the problem.

Discussion