Long-Horizon Planning for Multi-Agent Robots in Partially Observable Environments

Dear Reviewer,

Thank you for your comprehensive review and insightful feedback on our paper. We appreciate your thoughtful comments and suggestions, and we have provided our responses and clarifications below.

Computational complexity

Yes, we agree that having multiple LM-based modules would increase the computational complexity of the planning. Our initial goal was to create a benchmark and a method for getting the multi-agent robot teams to complete the tasks with a higher success rate as compared to previous approaches and hence it necessitated the need for more modules. While our initial experiments (refer to Table 2) compared the performance of different open-source along with GPT-4v, we found that GPT-4v was the best-performing one. Our future work would include using specialized fine-tuned LM modules. This would allow us to use smaller LMs and decrease the computational resources required to utilize all 4 modules.

Number of actions

While our action space contains the following executable actions: Move(<direction>), Rotate(<direction>), LookUp(<angle>), LookDown(<angle>), NavigateTo(<object_id>), Pickup(<object_id>), Put(<receptacle_id>), etc. There are a lot of different combinations available where the <object_ids>, <directions>, and <angles> can change. Hence the action space inherently becomes combinatorially large. For this reason, we do not constrain the LM modules to choose actions in a fixed format from this set; rather, we obtain a free-form language output. This allows for more expressivity in the outputs. The sentenceBERT module maps these free-form natural language outputs to the executable actions in the environment.

Scaling to real-world settings

We agree that scaling LLM-based TAMP methods is a challenge. We perform experiments with LLaMAR in a multi-agent drone search-and-rescue environment (SAR). Refer to the global rebuttal. The idea of having these experiments was to test out the capabilities of LLaMAR in other multi-agent environments. While the metrics reported with LLaMAR are in a simulator, we are hoping to run more real-world experiments with these drones to test how they fare when executed in a more realistic setting.

League++ Reference

Thanks a lot for bringing this very recent paper (April 2024) to our attention. While League++ does tackle the TAMP problem in conjunction with reinforcement learning a few key differences to our work are:

1. They focus on single-agent scenarios whereas we focus on multi-agent planning
2. They use LLMs for reward generation and skill acquisition.
3. The agent is given a list of all objects as a part of the observation which allows for creating plans and performing an A* search to verify the plan. In our case, we have a partially observable view of the environment which does not allow for performing search over the possible tasks/actions.

Challenge posed by over-restricted environments

Having over-constrained systems in various robotics settings is a well-known challenge (eg., freezing-robot problem) that could lead to issues in scaling. We agree with the comment on how our proposed method is also limited in similar settings. We will add this in our limitations section in the paper.

Dear Reviewer,

Thank you for your comprehensive review and insightful feedback on our paper. We appreciate your thoughtful comments and suggestions, and we have provided our responses and clarifications below.

LLaMAR explanation

The specific order of the modules is due to natural causal relationships in which environment feedback is received, which restricts our freedom in permuting the order significantly.

We use the planner as the first module because it allows LLaMAR to come up with an initial list of open subtasks that could be completed based on the current observation to satisfy the task. This list serves as a rough high-level plan. The actor then uses this information to suggest the necessary actions.

The Corrector is used after the Actor module so as to check for any failures in the execution of the actions suggested by the Actor. Note that the failure module is inert and only suggests corrective actions. Only the Actor module has the final say in the actions that are supposed to be executed. This distinction allows for clear reasoning on failures when they occur and lets the actor module focus on choosing actions.

The verifier is used after the action is executed to update the list of closed subtasks so that LLaMAR can be current with the progress toward the completion of the task. This allows the planner to update the list of open subtasks in the next step. In essence, the planner and the verifier ensure that the progress of the agents is tracked and the actor and the corrector ensure that the actions are executed successfully to advance towards completion of the task.

Our revised manuscript will include this justification with illustrative examples so as to explain why we converged on this solution.

Multi-agent features in LLaMAR

• Coordination Through Communication: Agents share their state information with the centralized LLaMAR modules to predict actions, enabling them to coordinate and avoid conflicts. This information sharing allows for the agents to cooperate and achieve the collective goal. A limitation of having a centralized module is that as the number of agents increases the observation input size (both textual and visual features) increases leading to a large input query (prompt).
• Hierarchical Task Decomposition: LLaMAR decomposes complex tasks into subgoals that are distributed among agents. This hierarchical approach simplifies the planning process and reduces computational complexity by focusing on manageable sub-tasks.
• Dynamic Role Assignment: Agents are dynamically assigned roles based on the current task requirements and their capabilities. This flexibility allows LLaMAR to adapt to changing environments and task demands.
• Decomposition of Action-Space: To handle the complexity of multi-agent planning, LLaMAR decomposes the action space by creating specific subgoals/subtasks available for any agent to assign itself (done by the actor module) based on the observation & current context. This decomposition reduces the overall search space and improves planning efficiency.

The corrector and actor module separation

Correct, the actor and corrector have similar information as inputs, but they are queried with a different task prompt. That is, we task the Actor module to suggest the actions and the Corrector module to explicitly reason why certain actions failed. This explicit designation of tasks in LM agents is more effective [1] as compared to letting a single LM module predict both the actions and reason for failure. Finally, only the ‘actor’ LM has the final say in the action to be performed, and the ‘corrector’ module is inert, only serving as a reasoning tool for the ‘actor’ LM.

[1] Guo, T., Chen, X., Wang, Y., Chang, R., Pei, S., Chawla, N. V., ... & Zhang, X. (2024). Large language model based multi-agents: A survey of progress and challenges. arXiv preprint arXiv:2402.01680.

Table 5 Analysis

In Table 5, there is a decrease in the metrics when the number of agents increases from 3 to 5. The reason for this is that as the number of agents increases, the rooms in MAP-THOR get crowded. Hence the agents block each other while navigating in the environment leading to a decrease in success rates due to successive failures in navigating to desired locations. We will update the analysis for Table 5 in our revised manuscript to explain the decrease in the metrics as we increase the number of agents. We apologize for the confusion! We perform experiments with LLaMAR in a multi-agent drone search-and-rescue environment (SAR) to showcase the effectiveness of LLaMAR in a different environment. Please refer to the global rebuttal for results and analysis.

Exploration Strategy

We agree that the exploration strategy used is domain-specific as we wanted the agents to search in more semantically related regions for objects of interest. We hope to use more sophisticated & generic approaches for exploration in our future work such that can be generalized well to other scenarios.

SmartLLM Benchmark

MAP-THOR is designed to include tasks that could be done by multiple agents. SmartLLM includes many tasks that could be completed with just a single agent. Example: “Slice the tomato”, “throw the spatula in the trash”, etc. Link. Although many of the tasks in these benchmarks require single agents, there are a few tasks that could be solved with multiple agents. We include most of such tasks in our benchmark. We will ensure that we include any other tasks from the SmartLLM benchmark that are not present in MAP-THOR.

Dear Reviewer,

Thank you for your comprehensive review and insightful feedback on our paper. We appreciate your thoughtful comments and suggestions, and we have provided our responses and clarifications below.

Single-agent comparison in MAP-THOR:

We perform experiments with just a single agent in the environment for the task in MAP-THOR. We report all the metrics for the single agent setting below. We report the means and the 95% confidence interval in parentheses.

With just a single agent in the environment, it is not able to complete the task in a majority of the episodes. This is because the number of steps required to complete the episode is higher than the horizon length of $L=30$. Hence the success rate and the transport rate are lower than n>1 agents. Also, the singular agent in the environment is not able to explore the environment enough within the planning horizon and hence the coverage is lower than $n>1$ agents.

Multi-agentness in experiments

We perform experiments in a multi-agent search-and-rescue environment where multiple drones are required to collaborate together. More information can be obtained in the global rebuttal. The key relevant points in this new environment are:

• Scalability: With the addition of multiple parallel emergency disaster scenarios at once, the environment scales comfortably to more agents. Additionally, the complexity slowly increases as the model has to coordinate between more actors and competing emergencies.
• Explicit cooperation:
  • In order to move a group of humans, at least 2 agents are required. Thus, explicit multi-agent collaboration is required.
  • Due to the time pressure, in order to successfully stop the fire, drones must all effectively collaborate in collecting and strategically using resources in high-intensity regions.
• Exploration task assignment: There is an explicit tradeoff between allocating drones towards exploring to find lost personnel and fighting the current fires.

Table 5 Analysis

In Table 5, there is a decrease in the metrics when the number of agents increases from 3 to 5. The reason for this is that as the number of agents increases, the rooms in MAP-THOR get crowded. Hence the agents block each other while navigating in the environment leading to a decrease in success rates due to successive failures in navigating to desired locations. We will update the analysis for Table 5 in our revised manuscript to explain the decrease in the metrics as we increase the number of agents. We apologize for the confusion!

We have performed experiments in a search-and-rescue environment that requires explicit cooperation. Please refer to the global rebuttal for the results in the search-and-rescue environment and more analysis.

Task Allocation

In our proposed architecture, the planner module plays the role of creating subtasks necessary for completing the tasks. The actor module then takes these subtasks and allocates them to different agents based on each agent's state. Centralized planning ensures that the actions suggested are not in conflict.

Analysis of failures cases

Multi-agent planning in embodied robotics environments has been a challenging problem. Our initial goal was to achieve better success rates in planning for a variety of tasks compared to previous approaches. While our method outperforms other baselines, we agree that the success rate is still not as good as expected for real-world deployment. We believe that our approach LLaMAR and the MAP-THOR benchmark would serve as a starting point for future research to improve the success rates in multi-agent embodied robotics tasks.

A few major types of failures in our experiments were:

• Mis-generalization: For example, in the wash tasks the LM assumes that it must put the objects in the sink, and add soap; rather than using the “CleanObject” action.

• Mutual interference (limited spatial reasoning): For example, in the put objects on the sofa task, the LM allows the agents to block each other, and therefore fail to put the objects on the sofa. Similarly, for the put objects in a box task.

• Improper receptacle visibility: For example, in the put objects on table task, the table is not initially visible yet the LM does not prioritize exploring to find it. Thus, it fails to navigate to it to put the necessary objects.

• SentenceBERT mismatch: The free-form natural language output from the Actor is incorrectly mapped to the executable action. Based on our experimental results, 96.7% of the time the free-form natural language was correctly mapped to the feasible actions. The 2 main reasons for failures in the few cases it failed were:

  1. Incorrect mapping of objects: when the agents had not yet explored the environment enough and the Actor module suggested the agents interact with objects that were not yet available in the agents’ combined memory. Example: The free-form output “navigate to the table” was mapped to the action “NavigateTo(ArmChair)”.
  2. Wrong object numeration: When there are multiple objects of the same type in the memory, the sentenceBERT maps “Cabinet_3” to “Cabinet_1” which sometimes leads to incorrect actions being executed for the completion of the plan.

  We will add a comprehensive list of different reasons for failures in each of the task categories in our revised appendix to help the readers better understand the gaps in performance between the baselines and our proposed approach. Along with this, we agree that having more illustrative examples of cooperation among agents in completing tasks would be helpful to showcase the effectiveness of our method. We will add these illustrations in our revised manuscript.

Thanks a lot for your reply and your follow-up questions!

1. We chose $L=30$ as our episode length for computational and budget reasons (to limit the GPT-4 API costs) to fit all the experiments we wanted to do and hence we did not extend the horizon. However, we ensured that all of the tasks were solvable by a single-agent human-controlled agent. The major difference between a human-controlled agent and an autonomous agent is that the visibility distance is set to 1.5m for the autonomous agents whereas it is not restricted for a human-controlled agent. A human can identify objects from quite far away (from the rendered images) and hence are able to efficiently navigate in the environment to interact with the objects whereas autonomous agents have to explore the environment. Thanks a lot for bringing up this point. We apologize for not including these details in the appendix.
2. We agree that a table clarifying the different scenario types in MAP-THOR would help the readers understand the rationale behind having them. Below is a description of the type of tasks in MAP-THOR along with the differences.

   1. Explicit item type, quantity, and target location (Type 1): Since the name and the quantity of the items to be interacted with and their exact target locations are explicitly defined, these tasks allow the agents to come up with an initial plan even without needing the agents to explore the environment.

      Example: the task “put bread, lettuce, and fridge in the fridge” can be solved by creating an initial plan:

      • transport bread to fridge
      • transport lettuce to fridge
      • transport bread to fridge

      These types of tasks are used in the experiments in the CoELA and SmartLLM paper.

   2. Explicit item type and target location but implicit item quantity (Type 2): Similar to Type 1, since the name of the items to be interacted with and their target locations are known, the agents can come up with an initial plan. But here, the number of such objects is not known apriori. Hence the agents will have to explore the environment to identify all such instances of these objects.

      Example: the task “put all vases on the table” can be partially solved by creating an initial plan:

      • transport vase to the table
      • explore the environment to search for more vases

   3. Explicit target location but implicit item types and quantity (Type 3): In these type of tasks, the agents cannot create an initial plan to solve the task as easily as Type 1 and Type 2. Here the names of the objects that it is supposed to interact with are not known apriori. The agents need to explore the environment such that the planner module can add subtasks that need to be satisfied.

      Example: for the task “put all groceries in the fridge”, the agents have to first identify the relevant objects that fit the category of “groceries” and then add subtasks to interact with those objects appropriately. This showcases the effectiveness of the planner module, verifier module, and exploration module to update the open and closed subtasks list by efficiently exploring the environment.

   4. Implicit target location, item type, and quantity (Type 4): This is similar to Type 3 tasks where the objects it needs to interact with are not known apriori. The key difference is that the target locations are also not known in this case whereas it is explicitly defined in Type 4 tasks. This checks whether the underlying LM is able to identify the appropriate target locations for the objects that it needs to interact with.

      Example: “Clear the table by placing the items in their appropriate positions”. In this task, the LM is supposed to first identify the objects on the table and their appropriate target locations.

      • transport bread to the fridge,
      • transport apple to the fridge
      • transport tomato to the fridge
      • transport knife to the cabinet/countertop/drawer
      • transport bowl to the cabinet
      • transport book to the bookshelf

      Note that the ambiguity of the tasks increases in each type of task.

Dear Reviewer,

Thank you for your comprehensive review and insightful feedback on our paper. We appreciate your thoughtful comments and suggestions, and we have provided our responses and clarifications below.

SentenceBERT

Yes, we agree with the concern about potential performance issues and incorrect mappings with SentenceBERT. Based on our experimental results, 96.7% of time the free-form natural language was correctly mapped to the feasible actions. The 2 main reasons for failures in the few cases it failed were:

1. Incorrect mapping of objects: when the agents had not yet explored the environment enough and the Actor module suggested the agents interact with objects that were not yet available in the agents’ combined memory. Example: The free-form output “navigate to the table” was mapped to the action “NavigateTo(ArmChair)”.
2. Wrong object numeration: When there are multiple objects of the same type in the memory, the sentenceBERT maps “Cabinet_3” to “Cabinet_1” which sometimes leads to incorrect actions being executed for the completion of the plan.

We will add more specific examples of the failure cases of the sentenceBERT module in the appendix of our revised manuscript.

As for using more general function calling with LLMs, we saw in our initial experiments that the LLMs performed well with function calling only when we gave a few examples of the exact format (eg., JSON, pythonic plans, dictionary, etc.) we wanted the LLM to answer in. This meant that we would have to use a significant amount of prompt tokens to include the examples in the input prompt. A way to get around this is to fine-tune the underlying LLMs on the type of outputs we want which we would like to do in our future work along with having specialized smaller LLMs for each module.

Checking the safety of actions before execution

This is a great point! One possible way to tackle this is to let the LMs build a world model of the environment as done in a very recent work [1,2]. This would allow the agents to reason about what would happen if certain actions were executed in the current context of the environment. This could act as a pre-execution action checker and allow for filtering unsafe or infeasible actions. However, a drawback of using another LM for the world model would be the added computational complexity.

[1]: Xiang, J., Liu, G., Gu, Y., Gao, Q., Ning, Y., Zha, Y., ... & Hu, Z. (2024). Pandora: Towards General World Model with Natural Language Actions and Video States. arXiv preprint arXiv:2406.09455. [2]: Zhang, H., Wang, Z., Lyu, Q., Zhang, Z., Chen, S., Shu, T., ... & Gan, C. (2024). COMBO: Compositional World Models for Embodied Multi-Agent Cooperation. arXiv preprint arXiv:2404.10775.

Dear Reviewer,

Thank you for your comprehensive review and insightful feedback on our paper. We appreciate your thoughtful comments and suggestions, and we have provided our responses and clarifications below.

Justification for the Proposed Framework

The specific order of the modules is due to natural causal relationships in which environment feedback is received, which restricts our freedom in permuting the order significantly.

We use the planner as the first module because it allows LLaMAR to come up with an initial list of open subtasks that could be completed based on the current observation and past memory to satisfy the task. This list serves as a rough high-level plan. The actor then uses this information to suggest the necessary actions.

The Corrector is used after the Actor module to identify reasons for failures in the execution of the actions suggested by the Actor. Note that the failure module is inert and only suggests corrective actions. Only the Actor module decides the final actions to be executed. This role distinction allows for clear reasoning on failures when they occur and lets the actor module focus on choosing actions.

The verifier is used after the action is executed to update the list of closed subtasks so that LLaMAR can be current with the progress toward the completion of the environment task. This allows the planner to update the list of open subtasks in the next step. In essence, the planner and the verifier ensure that the progress of the agents is tracked and the actor and the corrector ensure that the actions are executed successfully to advance towards completion of the task.

Our revised manuscript will include this justification with illustrative examples so as to explain why we converged on this solution.

Oracle feedback clarification

The terminology is confusing and should be cleared up. Thanks a lot for pointing it out. In L49, when we say our approach does not rely on oracle feedback, we mean to say that the environment does not provide any feedback. Instead, it uses controller feedback—a boolean variable indicating action success or failure, such as obstacles in planned paths or failed object grabs.

It is indeed true that, in general, loss of that low-level controller information could make the problem harder, and it is a fruitful direction to explore in future work.

MAP-THOR details

MAP-THOR includes 45 evaluation scenarios each initialized in 5 different rooms in AI2THOR. All of these 45 tasks are described in Appendix C. We refer to L726-L787 for a detailed list of all the tasks in MAP-THOR. A more detailed description of how to use the dataset to run experiments will be provided in the code’s repository when it is open-sourced. Additionally, a description of how to append new tasks to MAP-THOR will also be provided there. MAP-THOR as a dataset consists of AI2Thor scene pre-initializations, task information (task description, timeout, etc.) pairs, and an oracle performance evaluator (to get the metrics). Thus, there isn’t an explicit collection procedure since we create and simulate the tasks based on each floor plan.

The MAP-THOR dataset was not used to fine-tune/ train any of the modules in the cognitive architecture. Indeed we should provide a fixed training and evaluation division of the dataset in order to aid future work.

MAP-THOR is designed to include tasks that could be done by multiple agents. Previous benchmarks like AlfWorld, and SmartLLM include many tasks that could be done with just a single agent. Example: “Slice the tomato”, “throw the spatula in the trash”, etc. Link:https://github.com/SMARTlab-Purdue/SMART-LLM/blob/master/data/final_test/FloorPlan6.json. Although many of the tasks in these benchmarks require single agents, there are a few tasks that could be solved with multiple agents. We include those tasks in our benchmark. Other benchmarks like the ones used in CoELA in the ThreeDWorld and CWAH environments include tasks that require multiple agents. But there are only limited tasks, 5-10, in those experiments. Another major difference in MAP-THOR is that we instantiate each task in 5 different rooms with random initialization to test for the robustness of the underlying LM based cognitive architecture to variations in the room layouts. This allows us to perform a systematic study of its performance when compared to previous approaches. Along with this, we have created a script to add custom scenarios in AI2THOR. We will add more details about its usage in our documentation of the code and in our appendix along with pointing out specific details about how it is qualitatively different than previous approaches.

Clarification on the metrics in tables

The metrics shown in all tables are means. The values in the parentheses are the 95% confidence intervals. Since success rates are binomial, we use the Clopper-Pearson Interval as the confidence interval. For the metrics: “Success Rates (SR)”, “Transport Rates (TR)”, “Coverage (C)” and “Balance(B)”, higher is better and for “Steps (L)” lower is better

In Table 3, the means for SR, TR, C, and B are higher for LLaMAR (w/ exploration) compared to LLaMAR (wo/ exploration). Similarly, the lower bound of the confidence intervals for SR, TR, and C are higher for LLaMAR (w/ exploration). Similarly, the upper bounds for SR, TR, C, and B for LLaMAR (w/ exploration) are higher than or equal to the upper bounds for LLaMAR (wo/ exploration). For Balance (B), the means are equal for w/ and w/o exploration and the lower bound for w/ exploration (0.75) is slightly smaller than the lower bound for w/o exploration (0.77)