Simulation parameters and robot/victim characteristics.
Open access peer-reviewed article
This Article is part of Robotics Section
Article metrics overview
6 Article Downloads
View Full Metrics
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
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.
AI-based methods
multi-robot systems
search and rescue robotics
Author information
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.
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.
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.
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.
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:
robot ID
starting position of the robot on the map
speed of the robot (m/s)
algorithm used for path planning
number of clusters
competency of the robot
capabilities of the robot
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:
victim ID
position of the victim on the map
complete list of victim requirements along with the total number of each capability required
requirements of the victim
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.
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.
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.
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.
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.
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.
Illustration of 2D grid used as the search and rescue environment with randomized victim assignment.
Parameters | Values |
---|---|
Robot characteristics | |
Number of robots | Ranges from 2 to 10 |
Average running speed | 0.4 m/s (uniform for all robots) |
Robot initial position | Randomized at four entrances on the 2D grid map |
Capabilities | First aid Debris remover Oxygen cylinder Defuser Manipulator Fire extinguisher |
Victim characteristics | |
Number of victims | Ranges from 10 to 100 |
Severity rating | 1 (uniform for all victims) |
Victim locations | Randomized within the 2D grid map |
Simulation parameters | |
Platform | Apple M2 Chip w/ 8 GB RAM |
Number of simulation runs | 100 (for each combinatorial state space) |
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.
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:
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.
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.
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:
Full Requirement Fulfillment Percentage: Evaluate whether the capabilities of each robot match the requirements of the corresponding victims.
Partial Requirement Fulfillment Percentage: Given that partial fulfillment is allowed, we also employ another metric that indicates partially fulfilled requirements by robots.
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.
Baseline model (MSMRTA) evaluated in simulation with workload balance as a constraint (even number of robots).
Baseline model (MSMRTA) evaluated in simulation with workload balance as a constraint (odd number of robots).
MTU-LLM evaluated in simulation without workload balance as a constraint (even number of robots).
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.
MTU-LLM evaluated in simulation with workload balance as a constraint (even number of robots).
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 | |||||
---|---|---|---|---|---|---|---|
Robots | Victims | MTU-LLM | MSMRTA | MTU-LLM | MSMRTA | MTU-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 |
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.
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.
Task allocation output: requirement fulfillment details for a simple scenario with 10 victims and 4 robots.
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.
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 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.
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.
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 #.
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 #.
Example:
Constants:
capabilities = [’FirstAids’, ’DebrisRemover’, ’OxygenCylinder’, ’Defuser’, ’Manipulator’, ’FireExtinguisher’] num_clusters = 4
Map Coordinate System: The 2D map X–Y coordinate (19,0) corresponds to the origin.
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.
Environment Map Entrances:env_map2_entrances = [[0, 0], [0, 1], [0, 2], [1, 0], [2, 0]]
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]
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]
Task Allocation:r0 --> [v0] & [v2] & [v1]
r1 --> [v1] & [v0] & [v3]
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.
New Problem: The new problem follows the same structure as the example but with different robot and victim allocations.
Constants:capabilities = [’FirstAids’, ’DebrisRemover’, ’OxygenCylinder’, ’Defuser’, ’Manipulator’, ’FireExtinguisher’] num_clusters = 4
Map Information:
env_map2 = np.array([[0, 0, 0, 0, 0, 0, 0, 0, 1, ..],[0, 0, 0, 0, 0, 0, 0, 0, 1, ..],...])
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, ...]
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,...]
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.
Figures A.1–A.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.
LLM output: requirement fulfillment table.
LLM output: task allocation per robot and order of victims visited by robots.
LLM output: path taken by robots to reach victims.
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.
This research did not receive external funding from any agencies.
Not applicable.
Source data is not available for this article.
The authors declare no conflict of interest.
Written by
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
© 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
Join us today!
Submit your Article