Open access peer-reviewed article

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

Kaushik Kannan

Jungyun Bae

This Article is part of Robotics Section

Article metrics overview

6 Article Downloads

Article Type: Research Paper

Date of acceptance: June 2025

Date of publication: July 2025

DoI: 10.5772/acrt.20250014

copyright: ©2025 The Author(s), Licensee IntechOpen, License: CC BY 4.0

Download for free

Table of contents


Introduction
Related works
Problem description
Methodology
Validation and discussion
Computational results
Future work
Conclusion
Figure A.1.
MRTA LLM prompt
Path planning LLM prompt
LLM results
Author’s contribution
Funding
Ethical statement
Data availability statement
Conflict of interest

Abstract

Urban Search and Rescue operations after natural disasters involve locating and assisting victims in hazardous environments, which is challenging. Classical Multi-Robot Task Allocation (MRTA) and path planning approaches have been used to deploy heterogeneous robot teams in unsafe areas. However, existing methods often lack focus on workload balance and requirement fulfillment and struggle to generalize across different scenarios. To address these challenges, we propose Multi-robot Task allocation Utilizing LLMs (MTU-LLM), a framework designed to reduce the development time for task allocation and path planning approaches, enabling faster robot deployment. The framework uses an LLM-based “prompt engineering” approach that generates task allocation and path planning scripts for heterogeneous robot teams. This method is scalable, repeatable, and consistent across various environmental conditions, reducing lead time for MRTA algorithm development. The MTU-LLM approach is evaluated against classical MRTA and path planning methods using standard metrics. When tested on a standard environment map with varying robot teams and victim counts, the LLM-based approach demonstrates significantly higher computation time efficiency, better workload balance, and comparable requirement fulfillment percentage across numerous use cases compared to baseline methods.

Keywords

  • AI-based methods

  • multi-robot systems

  • search and rescue robotics

Author information

Introduction

Areas affected by natural disasters always require a rapid and swift response from search and rescue (SAR) teams to identify and rescue victims. Urban Search and Rescue (USAR) involves the location and provision of medical stabilization to victims trapped in structural collapse due to disasters, accidents, and so on. The USAR teams have about 48 h after a disaster to reach survivors, beyond which the probability of finding victims drastically decreases [1]. Moreover, structurally collapsed environments pose significant challenges to rescue teams in terms of traversability due to confined spaces.

Autonomous robots have started to play an increasingly significant role in USAR in recent years [2]. Robots have been used in USAR applications to assist humans and accelerate the response time [3, 4]. Additionally, robots have also been used in USAR scouting operations to survey, monitor, and fully understand the extent of damage while also gathering information related to victims trapped in the environment [5, 6]. Rescue robots are extremely valuable as they can complement humans and also perform independent tasks in USAR operations, alleviating a number of challenges that humans face in these situations.

Deploying a team of rescue robots for USAR applications and ensuring their cohesive functioning as a collective requires efficient task allocation and path planning strategies. Given the dynamic nature of USAR situations, there exist several practical challenges with Multi-Robot Task Allocation (MRTA) and path planning strategies. These include: (1) adaptability of MRTA and path planning with changing environmental conditions at the scene; (2) MRTA and path planning refinement based on changing victim needs, requirements, and severity of injury; and (3) efficient allocation of robots to victims, ensuring the underlying constraints (workload balance, requirement matching, etc.) are met.

This paper aims to bridge the gap between traditional MRTA and path planning approaches and the dynamic, complex nature of USAR operations by introducing a Large Language Model (LLM)-based prompt engineering approach. While existing methods often struggle with real-time adaptability and efficient resource allocation in rapidly changing environments, our LLM-driven framework offers a novel solution to generate adaptive MRTA and path planning algorithms. This approach not only addresses the challenges of environmental adaptability, victim-centric refinement, and efficient robot allocation but also significantly reduces algorithm development time. By leveraging the advanced natural language understanding and generation capabilities of LLMs, we aim to create more flexible, context-aware, and rapidly deployable solutions for complex USAR situations. Our research evaluates the scalability and consistency of this approach across various environmental conditions, potentially revolutionizing how we approach algorithm development for heterogeneous multi-robot systems (MRSs) in critical SAR operations.

Related works

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.

Figure 1.

Overview of related work and scope of this paper.

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.

Problem description

The primary objective of this work is to develop an LLM-based approach for efficient task allocation and path planning in USAR operations. Given high-level textual instructions in the form of LLM prompts, our goal is to formulate, optimize, and execute the prompt to effectively perform task allocation and planning. The key components are as follows: (1) a heterogeneous robot team, a set of robots with diverse characteristics and capabilities; (2) victims, individuals in need of rescue, each with specific requirements; and (3) environment, the SAR operation area. The robots are expected to perform the following high-level tasks: (1) task assignment: clustering victims and matching robot capabilities to victim requirements; and (2) path planning: generating feasible paths for robots to their assigned victims.

Given a set of m robots, n victims, and k environments, the corresponding inputs and outputs are defined as follows:

Inputs

a set of robots

a set of victims

a set of depots

a set of instructions that get translated into tasks on output for each robot

a set of environment maps

Outputs

tasks/victims allocated to each robot

path (order of victims to be visited) for each robot

Robot characterization

Each robot ri, i = 1, … , m, can be characterized by the function Robot (Rid, Rpos, Rspeed, algorithm, numclusters, Rcompetency, Rcapabilities, caplist), where each parameter is defined as follows:

Rid

robot ID

Rpos

starting position of the robot on the map

Rspeed

speed of the robot (m/s)

algorithm

algorithm used for path planning

numclusters

number of clusters

Rcompetency

competency of the robot

Rcapabilities

capabilities of the robot

caplist

complete list of capabilities of all robots

Victim characterization

Similarly, each victim vj, j = 1, … , n, can be characterized by the function Victim (Vid, Vpos, makespan, Vrequirements, caplist), where each parameter is defined as follows:

Vid

victim ID

Vpos

position of the victim on the map

makespan

complete list of victim requirements along with the total number of each capability required

Vrequirements

requirements of the victim

caplist

complete list of capabilities of all robots

High-level constraints and assumptions

In addition to the parameters described above, the robots are expected to satisfy the following high-level constraints: (1) requirement matching with victims; (2) feasible motion constraints; and (3) balanced workload of robots to minimize the maximum travel cost across all robots. Furthermore, the robots are assumed to depart from their respective depots and return to the depots after visiting all the assigned victims. We also assume that all robots have the same average running speed, and therefore, the travel cost is defined as the travel time of the robot to traverse the path in the order of visiting the assigned victims.

Methodology

Overview

Figure 2.

MTU-LLM: the proposed framework.

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.

Stage I: MRTA prompts

The MRTA prompts are structured as follows:

  • Context: The first section of the prompt is meant to provide the high-level goals and expectations for the LLM. While this section does not delve into the intricate details of constraints and objectives, it is intended to ground the LLM on how the problem shall be approached. Specifically, it is imperative to inform the LLM that the problem must be solved by learning from the example provided.

  • Example: To acquaint the LLM with the nature of the problem, we provide a simple yet holistic example of a task allocation problem along with a feasible solution. The example shall encompass all parameters used for solving the problem, such as environment map, map coordinate system, robot characteristics, victim characteristics, and the overall list of capabilities possessed by the robots. A solution in the desired format shall also be provided, indicating how the victims are allocated to the robots.

  • High-level objective: After providing the context and examples to the LLM, the high-level objective of the robot shall be clearly communicated. A sample high-level objective can be as follows: You should generate a solution to a new MRTA problem and consider the following task allocation objectives to solve the problem.

  • Task allocation approach and constraints: The purpose of this section is twofold: Specify the desired algorithm to be used by the LLM to solve the problem and provide an exhaustive list of constraints to which the LLM shall adhere.

    It is recommended that the desired algorithm used by the LLM be specified since it alleviates some of the non-determinism in the solutions provided by the LLM. Various experiments conducted by the team suggest that specifying the algorithm in the prompt tends to provide consistent and feasible results. For the purpose of this paper, we specified that the LLM should use a combination of K-means clustering [18] for task grouping based on proximity and distance-based bidding approaches while matching the victim requirements to robot capabilities, which is considered the primary criterion.

    The crux of the LLM prompting technique relies on providing the LLM with constraints that are feasible, mutually exclusive, and non-conflicting with each other. With the iterative refinement of the prompts, the following set of objectives was meticulously selected and incorporated as part of the prompt structure.

    • A victim’s requirements shall be fully met by one or more robots.

    • Each victim shall be visited by at least one robot that meets their requirements.

      • If all requirements can be met by one robot, prioritize this assignment.

      • If multiple requirements exist, they can be met by different robots with matching capabilities.

    • For a given requirement, the objectives are as follows:

      • It only needs to be met by one robot, even if multiple robots have the capability.

      • Use an appropriate heuristic to match unassigned victims to suitable robots.

    • Ensure the following:

      • Each robot is assigned at least one victim.

      • All victim requirements are met by robots with matching capabilities.

      • If a requirement cannot be met, indicate this in the output table.

    • In addition to distance-based clustering and bidding, consider matching victim requirements to robot capabilities for task allocation.

    • Workload balance may also be included as a constraint for task allocation. For multiple robots with similar capabilities, distribute the workload so that the overall workload is evenly distributed among the robots.

  • Problem to be solved: The problem to be solved shall be specified in this section and shall follow the same format as the example. This section shall also provide instructions on the desired format of the output to be generated.

Stage II: path planning prompts

The robot-specific task allocation output generated from the task allocation prompts is then used by the LLM to determine an appropriate path planning approach. The path planning prompts are structured as follows:

  • Path planning objectives: The path planning objectives and constraints shall consider motion constraints, meet expectations on feasible solutions, and solve for the objective function defined. Similar to the task allocation objectives, these constraints shall be defined in such a way that they are clear, concise, exhaustive, and non-conflicting. A list of path planning constraints used for path planning is as follows:

    • Find a feasible path for the robots to reach the victims.

    • The order of reaching the victims shall depend on the feasible path for the robot.

    • The robot should not travel through walls or obstacles on the map. Remember that 0’s in the map are traversable areas while 1’s are not traversable.

    • The robots should only travel along the map coordinates in the north, south, east, or west direction. The robot’s path cannot be diagonal.

    • The travel cost for the robot shall be calculated from its starting position on the map to the last victim that the robot visits.

  • Desired output and plot generation: The desired output of the path planning execution includes information related to the path planning algorithm used by the LLM, task allocation for each robot in the order in which victims are visited, travel cost for each robot in executing the tasks, and an indication of victims whose requirements were not fully met. These outputs are meant to provide visual cues and an initial assessment of the feasibility of task allocation and path planning outputs generated by the LLM.

A thorough evaluation of the scripts generated by the LLM for task allocation and path planning is performed offline, and the quality and completeness of the solution are assessed.

Validation and discussion

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.

Figure 3.

Illustration of 2D grid used as the search and rescue environment with randomized victim assignment.

ParametersValues
Robot characteristics
Number of robotsRanges from 2 to 10
Average running speed0.4 m/s (uniform for all robots)
Robot initial positionRandomized at four entrances on the 2D grid map
CapabilitiesFirst aid
Debris remover
Oxygen cylinder
Defuser
Manipulator
Fire extinguisher
Victim characteristics
Number of victimsRanges from 10 to 100
Severity rating1 (uniform for all victims)
Victim locationsRandomized within the 2D grid map
Simulation parameters
PlatformApple M2 Chip w/ 8 GB RAM
Number of simulation runs100 (for each combinatorial state space)

Table 1

Simulation parameters and robot/victim characteristics.

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. 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. 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. 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. Full Requirement Fulfillment Percentage: Evaluate whether the capabilities of each robot match the requirements of the corresponding victims.

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

Computational results

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.

Figure 4.

Baseline model (MSMRTA) evaluated in simulation with workload balance as a constraint (even number of robots).

Figure 5.

Baseline model (MSMRTA) evaluated in simulation with workload balance as a constraint (odd number of robots).

Figure 6.

MTU-LLM evaluated in simulation without workload balance as a constraint (even number of robots).

Figure 7.

MTU-LLM evaluated in simulation without workload balance as a constraint (odd number of robots).

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.

Figure 8.

MTU-LLM evaluated in simulation with workload balance as a constraint (even number of robots).

Figure 9.

MTU-LLM evaluated in simulation with workload balance as a constraint (odd number of robots).

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.

Average computation time (s)Requirement fulfillment (%)Workload balance score
RobotsVictimsMTU-LLM MSMRTAMTU-LLM MSMRTAMTU-LLM MSMRTA
2 20 0.003 0.145 55 35 0.815 0.737
4 10 0.004 0.113 60 10 0.532 0.351
5 20 0.005 0.147 55 15 0.623 0.129
6 80 0.021 0.411 67.5 52.5 0.849 0.511
8 50 0.016 0.341 100 68 0.527 0.1664
9 80 0.025 0.502 100 70 0.742 0.519
10 50 0.017 0.369 100 72 0.617 0.203
10 100 0.033 0.596 100 69 0.780 0.337

Table 2

Comparison of MTU-LLM and MSMRTA baseline for a subset of data points.

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

Figure 10.

Path planning output of MTU-LLM for a simple scenario with 10 victims and 4 robots.

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.

Figure 11.

Task allocation output: requirement fulfillment details for a simple scenario with 10 victims and 4 robots.

Discussion

Prompt engineering factors

Prompt engineering in LLMs is an evolving field, and several research groups have made significant contributions to novel prompting techniques, the taxonomy of prompt engineering approaches, and recommended best practices for prompt engineering [19, 20]. The prompt engineering approach for multi robot task allocation (MRTA) and path planning described in this work required a large number of iterations to yield the desired performance and output from the LLM. There are several aspects of the prompt input that affect the quality and feasibility of the LLM output. Some of these factors have been discussed in what follows:

  • Complex prompts: Our work suggests that breaking down complex tasks into multiple prompt stages yields better results. With task allocation and path planning being the two tasks incorporated into the LLM prompt, it was initially observed that the LLM was often directionless and performed poorly. However, breaking down these tasks into two separate stages in a staggered approach helps the LLM handle the prompts in a more efficient way.

  • Prompt sensitivity: Several authors, including Leidinger et al. [21], suggest that LLMs are highly sensitive to input prompts. A minor change in the prompt order, format, or semantics could potentially impact the quality of the LLM output. In our work, it was observed that swapping the order of different sections, such as “examples” and “objective,” led to an incomplete or incohesive suboptimal output from the LLM of 10 robots. However, several iterations on the prompt order eventually resulted in a consistent generation of results.

  • Prompt consistency: It was of the utmost importance that the prompts were structured such that they remained self-consistent and non-conflicting. This was especially true when the task allocation constraints were specified in the LLM prompt. Having two conflicting constraints results in the LLM either choosing one over the other or providing solutions that are infeasible. This inconsistent nature of the LLM can be addressed by meticulously formatting the prompts and ensuring that they are logical and cohesive.

  • Hallucinations: LLMs are prone to hallucinations that can be hard for humans to recognize since the solutions generated may be feasible but non-factual in nature [20]. This warrants the need for a precise and appropriate generation of prompts, which can largely alleviate some of the hallucinations that the LLMs inherently produce. Providing complete prompts will help reduce the ambiguity in the LLM output. Providing the LLM with a holistic view of the problem statement by including the algorithms, approaches, and examples helps the LLM to calibrate accordingly and generate the desired output with better consistency.

Overall, these factors were considered through the iterative development of the prompting technique in this work. With each factor considered in the design of the prompt structure, the performance of the LLM gradually improved and eventually, consistent results were generated.

Tokens and context window in LLMs

For LLMs, tokens represent groupings of text that are used by the model to derive semantic information. The token is generated using the input prompt provided by the user. Context window defines the amount of text that a model can process at any given time. Most LLMs operate within a fixed context window, ranging from 2000 to 100,000 tokens per inference window. A larger context window enables the model to handle larger prompts and generate precise outputs, but this may also suffer from computational limitations. Therefore, the context window is an important factor to be considered for MRSs, especially with an increase in the problem size. A larger number of victim–robot combinations or spatial reasoning over a larger environment map may pose significant challenges in using LLM-based approaches for SAR applications.

  • Larger Environment Maps: An expansive SAR area may require the use of highly detailed maps with nuanced semantic information encoded within them. This is a useful factor since the level of detail directly impacts the effectiveness of robot coordination and path planning. However, such maps may easily exceed available context limits, restricting the model’s ability to reason about the environment holistically and reducing the spatial context needed to perform the tasks.

  • Robot team size: As the number of robots or the amount of information encoded for each of the robots/victims also increases, this in turn results in a large volume of information such as states, capabilities, observations, and task assignment. Moreover, effective coordination strategies for a large robot–victim count are more complex to achieve if the necessary computational budget is unavailable. Having all of the above information in a zero-shot prompt may easily surpass the maximum allowable token budget, limiting the model from reasoning over the entire state space.

Some of these factors were addressed by decomposing the problem and partitioning the prompts into a two-stage approach. Separating the task allocation and path planning prompt structure into two stages helps solve each of the subproblems sequentially while still adhering to the context window limitations of the LLM. Future research will explore more hierarchical strategies for the LLM-based approach with an increase in the problem size, further diving deep into the factors discussed in this section.

Future work

Future research will focus on incremental updates based on the foundational work introduced in this paper. Some of the improvements and future considerations have been discussed in the following:

  • Real-time applicability: While this paper demonstrates the computational efficiency of the proposed approach, future research will focus on validating its real-time applicability and scalability in more complex and realistic environments. The current evaluation is limited to a simplified two-dimensional grid, which does not adequately reflect the challenges encountered in real-world USAR scenarios. For practical purposes, robot teams operate in three-dimensional spaces, navigate around dynamic and unpredictable obstacles, and adapt to evolving victim locations. Furthermore, the integration of real-time sensory feedback and the coordination of heterogeneous robotic platforms are critical to enhancing the robustness and adaptability of the approach. Extensive testing in both high-fidelity simulations and real-world deployments will be essential to substantiate the framework’s practical effectiveness.

  • Latency considerations: Latency is a safety-critical consideration in multi-robot USAR operations, where timely coordination and decision-making can directly impact the safe rescue of victims. In the future, evaluating the LLM-based approach in realistic environments will provide more insight into the robustness of the approach. Moreover, this will also be used to assess the effectiveness of the coordination approach in the presence of communication or processing delays. 

  • Dynamic victim prioritization: The current work assumes all victims have uniform prioritization and the same level of severity. Future work will focus on introducing victim severity as an additional constraint, which may change dynamically over the timeline of the mission. Including this additional constraint will help refine the approach to better represent the dynamic nature of real-world SAR operations.

  • More enhanced constraints: In the future, we aim to introduce additional constraints to the problem and refine the prompts to handle more complexity in the USAR applications. Some of these constraints include varying speeds of robots, payload capability of robots, additional heterogeneity in robots, and so on.

  • Other LLMs: We also intend to apply the LLM-based approach in this paper to other LLMs and develop strategies for effective optimization of prompts based on varying model capabilities and characteristics.

Conclusion

In our work, we introduce MTU-LLM as a zero-shot two-stage prompt engineering technique for task allocation and path planning in SAR operations. The prompts were designed and structured as NLPs to aid human readability as well as enhance the consistency of the LLM output. Our experiments through simulation show that the proposed method handles the task allocation and path planning tasks efficiently, producing feasible solutions over the parameterized state space of robot–victim combinations in the environment. This method largely reduces the algorithm development time and provides a deployable solution for complex USAR applications.

In the future, we aim to introduce additional constraints for these tasks and develop prompts to handle more complexity in the USAR applications. Additionally, we aim to evaluate the techniques used in additional LLM models to draw objective comparisons and recommendations.

The subsections on MRTA and path planning LLM prompts provide an example prompt developed as part of this work. The prompt is designed for a problem size involving 4 robots and 20 victims but has shown the potential to scale for larger problem sizes.

MRTA LLM prompt

READ ALL THE STEPS IN THE PROMPT COMPLETELY AND ENSURE THAT THEY ARE FULLY CONSIDERED IN YOUR FINAL ANALYSIS. YOU WILL PROVIDE THE OUTPUT ONLY AFTER COMPLETING ALL THE STEPS IN THE PROMPT. Follow all the constraints and criteria for #Task Allocation Objectives #.

  1. Context: I want you to determine task allocation for each robot for a Multi-Robot Task Allocation (MRTA) Problem in a Search and Rescue (SAR) application. The output determined should be feasible. I will provide you with information related to the environment map, map entrances, robot capabilities, victim requirements, and constraints. I will also provide you with an example of how to determine a feasible solution to a Multi-Robot Task Allocation Problem. You will understand the example provided below and learn to solve a similar problem. Learn from the #EXAMPLE #and solve the problem under #OBJECTIVE #.

  2. Example:

    1. Constants:

      capabilities = [’FirstAids’, ’DebrisRemover’, ’OxygenCylinder’, ’Defuser’, ’Manipulator’, ’FireExtinguisher’] num_clusters = 4

    2. Map Coordinate System: The 2D map X–Y coordinate (19,0) corresponds to the origin.

    3. Map Information:env_map2 = np.array([[0, 0, 0, 0, 0, 0, 0, 0, 1, ...], [0, 0, 0, 0, 0, 0, 0, 0, 1, ...]...])

      Here is how to interpret the map: 0’s indicate traversable points while 1’s represent obstacles or walls that are not traversable by the robot.

    4. Environment Map Entrances:env_map2_entrances = [[0, 0], [0, 1], [0, 2], [1, 0], [2, 0]]

    5. Robot Capabilities: The robot is characterized by

      Robot(id, pos, speed, algorithms, num_clusters, competency, capabilities, cap_list)

      where

      • id = robot ID

      • pos = starting position of the robot on the map

      • speed = speed of the robot (m/s)

      • algorithm = algorithm used for path planning

      • num clusters = number of clusters

      • competency = competency of the robot

      • capabilities = capabilities of the robot

      • cap list = full list of capabilities from constants

      Defined robots:

      r0 = Robot(0, [0, 9], 0.2, [],num_clusters, [], [’Defuser’, ’DebrisRemover’], capabilities) r1 = Robot(1, [0, 10], 0.3, [],num_clusters, [], [’FirstAids’], capabilities) robots = [r0, r1]

    6. Victim Requirements: The victim is characterized by

      Victim(id, pos, make_span, requirements, cap_list)

      where

      • id = victim ID

      • pos = location of the victim on the map

      • make span = full list of victim requirements with capability needs

      • requirements = specific needs of the victim

      • cap list = full list of capabilities from constants

      Defined victims:

      v0 = Victim(0, [16., 7.], make_span, [’DebrisRemover’, ’OxygenCylinder’], capabilities) v1 = Victim(1, [15., 12.], make_span, [’Defuser’, ’Manipulator’], capabilities)

      victims = [v0, v1]

  3. Task Allocation:r0 --> [v0] & [v2] & [v1]

    r1 --> [v1] & [v0] & [v3]

  4. Objective: You should generate a solution to a new MRTA problem, considering the following objectives:

    • Perform task allocation using K-means clustering and distance-based bidding.

    • Ensure that one or more robots fully or partially meet victim requirements.

    • Prioritize single-robot fulfillment of victim needs.

    • If multiple robots match a victim’s requirement, distribute tasks appropriately.

    • Use heuristic matching for unassigned victims.

    • Every victim should be assigned to at least one robot if the capabilities match.

    • Indicate unmet victim requirements in the output.

  5. New Problem: The new problem follows the same structure as the example but with different robot and victim allocations.

    1. Constants:capabilities = [’FirstAids’, ’DebrisRemover’, ’OxygenCylinder’, ’Defuser’, ’Manipulator’, ’FireExtinguisher’] num_clusters = 4

    2. Map Information:

      env_map2 = np.array([[0, 0, 0, 0, 0, 0, 0, 0, 1, ..],[0, 0, 0, 0, 0, 0, 0, 0, 1, ..],...])

    3. Robot Capabilities: Defined robots:

      r0 = Robot(0, [0, 9], 0.2, [], num_clusters, [], [’Defuser’, ’DebrisRemover’], capabilities) r1 = Robot(1, [0, 10], 0.3, [], num_clusters, [], [’FirstAids’], capabilities)

      robots = [r0, r1]

      ...

      ...

      robots = [r0, r1, ...]

    4. Victim Requirements: Defined victims:v0 = Victim(0, [16., 7.], make_span, [’DebrisRemover’, ’OxygenCylinder’], capabilities)

      v1 = Victim(1, [15., 12.], make_span, [’Defuser’, ’Manipulator’], capabilities)

      victims = [v0, v1]

      ...

      ...

      victims = List of [v0,v1,v2,v3,...]

Path planning LLM prompt

READ ALL THE STEPS IN THE PROMPT COMPLETELY AND ENSURE THAT THEY ARE FULLY CONSIDERED IN YOUR FINAL ANALYSIS. INITIALIZE AND USE ALL VARIABLES AND CONSTANTS FROM THE PREVIOUS PROMPT FOR THIS ANALYSIS. YOU WILL PROVIDE THE OUTPUT ONLY AFTER COMPLETING ALL THE STEPS IN THE PROMPT INCLUDING THE VISUALIZATIONS. Follow all the constraints and criteria for #Path Planning Objectives #

(1) Path Planning Objectives: Use the task allocation output generated and choose an appropriate path planning approach. You will consider the following constraints for path planning:

  • Find a feasible path for the robots to reach the victims.

  • The order of reaching the victims shall depend on the feasible path for the robot.

  • The robot should not travel through walls or obstacles on the map. Remember that 0’s in the map are traversable areas while 1’s are not traversable.

  • The robots should only travel along the map coordinates in the north, south, east, or west direction. The robot’s path cannot be diagonal.

  • The travel cost for the robot shall be calculated from its starting position on the map to the last victim that the robot visits.

LLM results

Figures A.1A.3 illustrate the output from the LLM after the MRTA and path planning prompts are provided. This illustration is for a problem size involving 4 robots and 20 victims.

Figure A.1.

LLM output: requirement fulfillment table.

Figure A.2.

LLM output: task allocation per robot and order of victims visited by robots.

Figure A.3.

LLM output: path taken by robots to reach victims.

Author’s contribution

Kannan, Kaushik: Conceptualization, Data curation, Formal analysis, Investigation, Methodology, Software, Validation, Visualization, Writing – original draft; Bae, Jungyun: Conceptualization, Methodology, Project administration, Supervision, Writing – review & editing.

Funding

This research did not receive external funding from any agencies.

Ethical statement

Not applicable.

Data availability statement

Source data is not available for this article.

Conflict of interest

The authors declare no conflict of interest.

References

  1. 1.
    Shah B, Choset H. Survey on urban search and rescue robots. J Robot Soc Japan. 2004;22(5):582586. doi:10.7210/jrsj.22.582.
  2. 2.
    Queralta JP, Taipalmaa J, Can Pullinen B, Sarker VK, Nguyen Gia T, Tenhunen H, Collaborative multi-robot search and rescue: Planning, coordination, perception, and active vision. IEEE Access. 2020;8: 191617191643. doi:10.1109/ACCESS.2020.3030190.
  3. 3.
    Mehmood S, Ahmed S, Kristensen AS, Ahsan D. Multi criteria decision analysis (MCDA) of unmanned aerial vehicles (UAVs) as a part of standard response to emergencies. In: 4th International Conference on Green Computing and Engineering Technologies. Gyancity International Publishers; 2018. 31 p, Available from: https://www.ijitee.org/wp-content/uploads/papers/v8i2s2/BS2014128218.pdf.
  4. 4.
    Roberts W, Griendling K, Gray A, Mavris DN. Unmanned vehicle collaboration research environment for maritime search and rescue. In: Proceedings of the 30th Congress of the International Council of the Aeronautical Sciences, Daejeon, Republic of Korea. 2016. Available from: https://www.icas.org/icas_archive/ICAS2016/data/papers/2016_0728_paper.pdf.
  5. 5.
    Merino L, Caballero F, Martinez-de Dios J, Ollero A. Cooperative fire detection using unmanned aerial vehicles. In: Proceedings of the 2005 IEEE International Conference on Robotics and Automation. Piscataway, NJ: IEEE; 2005. p. 18841889. doi:10.1109/ROBOT.2005.1570388.
  6. 6.
    Brenner S, Gelfert S, Rust H. New approach in 3d mapping and localization for search and rescue missions. In: CERC2017. 2017. 105 p, Available from: https://www.researchgate.net/publication/361364306.
  7. 7.
    Surmann H, Worst R, Buschmann T, Leinweber A, Schmitz A, Senkowski G, Integration of UAVs in urban search and rescue missions. In: 2019 IEEE International Symposium on Safety, Security, and Rescue Robotics (SSRR). Piscataway, NJ: IEEE; 2019. p. 203209. doi:10.1109/SSRR.2019.8848940.
  8. 8.
    Myeong W, Jung KY, Myung H. Development of FAROS (fire-proof drone) using an aramid fiber armor and air buffer layer. In: 2017 14th International Conference on Ubiquitous Robots and Ambient Intelligence (URAI). Piscataway, NJ: IEEE; 2017. p. 204207. doi:10.1109/URAI.2017.7992713.
  9. 9.
    Konyo M, Ambe Y, Nagano H, Yamauchi Y, Tadokoro S, Bando Y, ImPACT-TRC thin serpentine robot platform for urban search and rescue. In: Disaster robotics: results from the ImPACT tough robotics challenge. 2019. p. 2576. doi:10.1007/978-3-030-05321-5_2.
  10. 10.
    Zhao W, Meng Q, Chung PW. A heuristic distributed task allocation method for multivehicle multitask problems and its application to search and rescue scenario. IEEE Trans Cybern. 2015;46(4):902915. doi:10.1109/TCYB.2015.2418052.
  11. 11.
    Hussein A, Adel M, Bakr M, Shehata OM, Khamis A. Multi-robot task allocation for search and rescue missions. J Phys Conf Ser. 2014;570(5):052006. doi:10.1088/1742-6596/570/5/052006.
  12. 12.
    Mouradian C, Sahoo J, Glitho RH, Morrow MJ, Polakos PA. A coalition formation algorithm for multi-robot task allocation in large-scale natural disasters. In: The 13th International Wireless Communications and Mobile Computing Conference (IWCMC). Piscataway, NJ: IEEE; 2017. p. 19091914. doi:10.1109/IWCMC.2017.7986575.
  13. 13.
    Osooli H, Robinette P, Jerath K, Azadeh R. A multi-robot task assignment framework for search and rescue with heterogeneous teams. In: 2023 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 2023 Advances in Multi-Agent Learning - Coordination, Perception, and Control Workshop). Oct. 2023. Available from: https://doi.org/10.48550/arXiv.2309.12589.
  14. 14.
    Kannan SS, Venkatesh VLN, Min B-C. SMART-LLM: Smart multi-agent robot task planning using large language models. In: 2024 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), Abu Dhabi, United Arab Emirates. Piscataway, NJ: IEEE; 2024. p. 1214012147. doi:10.1109/IROS58592.2024.10802322.
  15. 15.
    Song CH, Wu J, Washington C, Sadler BM, Chao W-L, Su Y. LLM-planner: few-shot grounded planning for embodied agents with large language models. In: Proceedings of the IEEE/CVF International Conference on Computer Vision (ICCV). Piscataway, NJ: IEEE; 2023. p. 29983009. doi:10.1109/ICCV51070.2023.00280.
  16. 16.
    Wang S, Han M, Jiao Z, Zhang Z, Wu YN, Zhu S-C, LLM3: large language model-based task and motion planning with motion failure reasoning. In: 2024 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), Abu Dhabi, United Arab Emirates. Piscataway, NJ: IEEE; 2024. p. 1208612092. doi:10.1109/IROS58592.2024.10801328.
  17. 17.
    OpenAI. Achiam J, Adler S, Agarwal S, Ahmad L, Akkaya I, GPT-4 technical report [Internet]. arXiv; 2024. Available from: https://arxiv.org/abs/2303.08774.
  18. 18.
    Janati F, Abdollahi F, Ghidary SS, Jannatifar M, Baltes J, Sadeghnejad S. Multi-robot task allocation using clustering method. In: Robot intelligence technology and applications 4. Advances in intelligent systems and computing. vol. 447, Berlin: Springer; 2017. p. 233247. doi:10.1007/978-3-319-31293-4_19.
  19. 19.
    Schulhoff S, Ilie M, Balepur N, Kahadze K, Liu A, Si C, The prompt report: A systematic survey of prompting techniques [Internet]. arXiv; 2024. Available from: https://arxiv.org/abs/2406.06608.
  20. 20.
    Huang L, Yu W, Ma W, Zhong W, Feng Z, Wang H, A survey on hallucination in large language models: principles, taxonomy, challenges, and open questions [Internet]. ACM Trans Inform Sys. Jan. 2025;43(2):155. Available from: doi:10.1145/3703155.
  21. 21.
    Leidinger A, van Rooij R, Shutova E. The language of prompting: What linguistic properties make a prompt successful? In: Findings of the association for computational linguistics: EMNLP 2023. Singapore: Association for Computational Linguistics. p. 92109232. doi:10.18653/v1/2023.findings-emnlp.618.

Written by

Kaushik Kannan and Jungyun Bae

Article Type: Research Paper

Date of acceptance: June 2025

Date of publication: July 2025

DOI: 10.5772/acrt.20250014

Copyright: The Author(s), Licensee IntechOpen, License: CC BY 4.0

Download for free

© The Author(s) 2025. Licensee IntechOpen. This is an Open Access article distributed under the terms of the Creative Commons Attribution License (https://creativecommons.org/licenses/by/4.0/), which permits unrestricted reuse, distribution, and reproduction in any medium, provided the original work is properly cited.


Impact of this article

6

Downloads

13

Views


Share this article

Join us today!

Submit your Article