Hierarchical Auto-Organizing System for Open-Ended Multi-Agent Navigation

Introduction

Drawing on large language models (LLMs) with human knowledge, communicative competence Mao et al. (2020a; a), and decision-making capabilities, embodied agents exhibit human-like intelligence in playing games (Park et al., 2023; Wang et al., 2023a; Zhao et al., 2023), programming (Qian et al., 2023; Hong et al., 2023), and robotic tasks (Zhang et al., 2023b; Mandi et al., 2023). The development of individual intelligence has led to creating a new, collaborative framework where multiple agents Chen et al. (2023a; b) work together.

This shift towards a multi-agent system Hong et al. (2023); Chen et al. (2023a) uses advanced language understanding and decision-making abilities to enhance intelligence through interactions and data sharing. Agents in this system specialize in various tasks, sharing insights to enhance overall efficiency. This collaborative approach not only optimizes execution but also fosters a learning environment where agents continually improve through shared intelligence. Their interaction leads to refined skills, equipping them to handle complex, large-scale tasks through parallel processing and coordinated collaboration, a notable advancement in autonomous systems.

Multi-modal navigation (Wijmans et al., 2019; Yu et al., 2021; Du et al., 2020; Kwon et al., 2023; Chen et al., 2021; Moudgil et al., 2021) stands at the forefront of contemporary AI research, representing a rapidly evolving field that aims to integrate various sensory inputs into a cohesive navigational strategy. This emerging domain extends the capabilities of multi-agent systems by requiring them to interpret and act upon a confluence of sensory data. Unlike traditional methods focusing on rendered images or static virtual environments, works on dynamic environments Deng et al. (2023), such as multi-modal navigation in open-ended environments like Minecraft, pose a more complex challenge. Agents in Minecraft Wang et al. (2023a); Zhao et al. (2023) navigate a world full of freedom and variability, making it an ideal testbed for embodied agent systems. Minecraft’s unpredictable and open-ended environment is an ideal testing ground for advanced AI systems. These systems emulate human adaptability and intelligence, processing and sharing multi-modal data to strategically navigate and complete tasks. This approach goes beyond simple improvements, marking a significant leap in developing autonomous systems that handle complex tasks with remarkable autonomy and skill. Integrating Multi-modal Language Models (MLMs) into embodied agents enhances navigational efficiency. Equipped with LLMs, these agents engage intelligently with their environment. The zero-shot performance capabilities of LLMs enable them to interpret and act upon data without explicit programming. This makes them ideal for open-ended environments.

Our vision is centered on employing MLM-based embodied agents to revolutionize navigation within the intricate landscapes of Minecraft. Environments in this game present unique challenges, such as the need to respond to image, audio, and object cues in real-time, as highlighted in Figure 1. By harnessing the zero-shot learning capabilities and the nuanced decision-making abilities of LLMs, our agents can navigate these spaces with efficiency and adaptability akin to human intuition. Such versatility is achieved without requiring exhaustive retraining or complex reconfigurations, marking a substantial leap towards autonomous systems that engage with their surroundings in more sophisticated and human-like ways.

We summarize our contributions as follows:

$\bullet$ We introduce HAS, a hierarchical structure for multi-agent navigation based on LLMs in the Minecraft environment. It utilizes centralized planning with decentralized execution, enabling efficient multi-modal navigation in open-ended environments.

$\bullet$ We design an auto-organizing and intra-communication mechanism to dynamically adjust the key role and action group based on the task allocation and maintain inter-group communication to ensure efficient collaboration.

$\bullet$ We achieve state-of-the-art performance on the asynchronous multi-modal navigation task on image, audio, and object goals in Minecraft’s open-ended environment.

Related Works

As an open-ended sandbox game, Minecraft has always been an ideal setting for testing the performance of intelligent agents (Johnson et al., 2016; Hofmann, 2019). The agents must autonomously perform various tasks in Minecraft, such as chopping trees, crafting tools, and mining diamonds. At the beginning, much of the works focus on exploring reinforcement learning (Lin et al., 2021; Mao et al., 2022; Skrynnik et al., 2021; Lifshitz et al., 2023) or imitation learning (Amiranashvili et al., 2020; Baker et al., 2022), without satisfactory performance. VPT (Baker et al., 2022) and MineDojo (Fan et al., 2022) collect internet-scale datasets for their model pre-training. VPT enables direct learning to act during video pre-training and using these behaviors as exploration priors for reinforcement learning. Yet, recent works found that the pre-trained LLMs could serve as a strong “mind” that provides planning ability to the agents. Voyager (Wang et al., 2023a) is a single-robot multiple agent system that leverages multiple groups of GPT-4 (OpenAI, 2023) as a high-level planner, low-level action code generator, critic generator, and curriculum manager. Plan4MC (Yuan et al., 2023) proposes a skill graph pre-generated by the LLMs. DEPS (Wang et al., 2023e), an interactive planning method based on LLMs, addresses multi-step reasoning issues in open-world planning. GITM (Zhu et al., 2023b) develops a set of structured actions and leverages LLMs to generate action plans for the agents to execute, achieving impressive results in various tasks.

2 Embodied Multimodal Model

Embodied agents integrate sensory perceptions, physical actions, and computational intelligence to accomplish tasks and goals within their environment. Key areas are wide-ranging, including Navigation (Wijmans et al., 2019; Yu et al., 2021; Du et al., 2020; Kwon et al., 2023; Chen et al., 2021; Moudgil et al., 2021), Embodied Question Answering (Das et al., 2018; Yu et al., 2019; Datta et al., 2022), Active Visual Tracking (Luo et al., 2018; Zhong et al., 2021; Luo et al., 2019; Zhong et al., 2019), and Visual Exploration (Liu & Okatani, 2022; Dean et al., 2020; Chen et al., 2018). The field is evolving rapidly with the development of Large Language Models (LLMs) (Song et al., 2022) and Multimodal LLMs (MLLMs) (Alayrac et al., 2022; Zhu et al., 2023a; Li et al., 2023a; 2022; b; Gong et al., 2023; Lyu et al., 2023; Ye et al., 2023; Dai et al., 2023; Wang et al., 2023c; Liu et al., 2023a; Maaz et al., 2023; Su et al., 2023; Gao et al., 2023), integrating multiple modalities for more effective processing. A prime example of this innovation is PaLM-E (Driess et al., 2023), a sophisticated multimodal model with 562B parameters, adept at a broad spectrum of embodied tasks and demonstrating exceptional capabilities in visual reasoning.

3 LLM-based Multi-Agent Frameworks

Large Language Models (LLMs) are skilled at completing new tasks when given prompt-based instructions. Autonomous agents based on Large Language Model-based (LLM-based) models have gained significant interest in industry and academia (Wang et al., 2023b). Several works (Wang et al., 2023d; Du et al., 2023; Zhuge et al., 2023; Hao et al., 2023; Akata et al., 2023; Zhang et al., 2023a) have augmented the problem-solving abilities of LLMs by incorporating discussions among multiple agents. Stable-Alignment (Liu et al., 2023b) generates instruction datasets by reaching a consensus on value judgments through interactions among LLM agents in a sandbox. Some works in the field of artificial intelligence focus on studying sociological phenomena. For instance, Generative Agents (Park et al., 2023) creates a virtual “town” comprising 25 agents to investigate language interaction, social understanding, and collective memory. The Natural Language-Based Society of Mind (Zhuge et al., 2023) involves agents with different functions interacting to solve complex tasks through multiple rounds of Mindstorms. In addition, others (Cai et al., 2023) propose a model for cost reduction by combining large models as tool makers and small models as tool users.

Some works emphasize cooperation and competition related to planning and strategy (Bakhtin et al., 2022), some propose LLM-based economies (Zhuge et al., 2023), and others propose LLM-based programming (Hong et al., 2023). Developing an LLM-based multiple embodied agent system with control capability is challenging. We face difficulties in multi-agent cooperation, such as low efficiency of global perception and generalizing dynamic groups. To overcome these challenges, we aim to apply a hierarchical auto-organizing system in multi-agent navigation.

HAS: A Multi-agent Navigation Framework

As shown in Figure 2, the HAS is a hierarchical LLM-based multi-modal multi-agent navigation framework denoted as $\mathcal{F}$, which can manage and execute complex multi-agent navigation tasks on image ($Im$), object ($Oj$), and audio ($Au$) goals with perception on the state list of vision ($v$), audio ($a$), and other properties $p$ within open-ended environments by leveraging cognitive and collaborative capabilities of the multi-modal language model ($\mathbf{MLM}$):

where $(v^{c}_{i},a^{c}_{i},p^{c}_{i})$ represents the state list of vision, audio, and other properties of one conductor agent, $g$ is the original goal, and $\mathcal{M}$ is the dynamic map. Then, we get $\mathbf{a}^{c}_{i}$ as the action for the conductor agent $i$.

The Hierarchical architecture consists of two primary operational domains: higher-order centralized planning, which is managed by the manager multi-modal language model ($\mathbf{MLM}^{M}$), and ground-level decentralized execution, which is conducted by the conductor model ($\mathbf{MLM}^{C}$), then the action $a^{c}_{i}$ of the conductor can be obtained as follows,

where $\mathbf{MLM}^{C}$ and $\mathbf{MLM}^{M}$ represent the multi-modal language models of the conductor and manager agents.

Evoked from the Centralized Training with Decentralized Execution (CTDE) framework (Hu et al., 2023; Sunehag et al., 2017; Lowe et al., 2017; Mao et al., 2018) for cooperative Multi-Agent Reinforcement Learning (MARL), we propose Centralized Planning with Decentralized Execution (CPDE) for the cooperative LLM-based Multi-Agent system. This architecture leverages global state information to inform the planning process, while the execution of tasks is carried out by local agents independently. CPDE is tailored to maximize the synergy of global oversight and local autonomy, ensuring efficient navigation and task completion in complex environments.

The centralized planning process for a manager agent $M$ simulates a high-level understanding like that of a human planner. The process includes understanding the environment’s dynamic global states, recognizing the conductor agents’ capabilities and limitations, and devising a strategy. It contains $\mathbf{MLM}^{M}$ consisting of 4 MLM modules with different functions for the manager as mentioned in Section 3.2 and a Global Multi-modal Memory for storing multi-modal information as mentioned in Section 3.3.

Decentralized execution for action agent.

The decentralized execution process is designed to capitalize on the autonomy and flexibility of conductor agents $C$. These agents navigate the environment, perform tasks, and learn from their interactions guided by the strategic direction from the centralized planning of the manager agent. Note that these conductors can deploy several action agents for similar goals of one sub-goal. It contains $\mathbf{MLM}^{C}$ comprising 4 MLM modules for conductors with different functions as mentioned in Section 3.2 and a Local Multi-modal Memory for storing multi-modal information as mentioned in Section 3.3.

Auto-organizing mechanism.

The auto-organizing mechanism is a spontaneous grouping mechanism to promote multi-agents’ efficiency. In the centralized planning phase, the manager agent auto-organizes several conductor agents based on the global environment and tasks, which takes advantage of the planning capabilities of MLM and is inspired by AutoAgents (Chen et al., 2023a) to deploy agents with different roles automatically. During the decentralized execution stage, we are inspired by the Self-Organized Group (SOG) (Shao et al., 2022) to solve the issue of zero-shot generalization ability with dynamic team composition and varying partial observability. We improve and use a novel auto-organizing mechanism. Each group has conductor-action agent consensus, where the action agents can only communicate with their conductor. Additionally, we utilized the summarization ability (Ma et al., 2023) from LLM to summarize and distribute the messages received to all affiliate group members to hold a unified schedule.

2 Multi-modal Language Model

The Multi-modal Language Model $\mathbf{MLM}=\{\mathbf{MLM}^{M},\mathbf{MLM}^{C}\}$, consisting of two different types of MLM of the manager and conductor agents. $\mathbf{MLM}^{M}=\{\mathcal{P}_{l},\mathcal{D}_{s},\mathcal{C}_{r}^{m},\mathcal{D}_{p}\}$, which consists of Planner, Describer, Critic, and Deployer for the manager. They formulate aligned task plans, condense and translate multi-modal data, refine strategies through feedback, and assign and direct agent subtasks respectively. $\mathbf{MLM}^{C}=\{\mathcal{A}_{c},\mathcal{C}_{u},\mathcal{C}_{r}^{c},\mathcal{S}_{k}\}$, which consists of Actor, Curriculum, Critic, and Skill module for conductors. They translate strategic plans into executable actions, orchestrate dynamic group formations, and distribute tasks across agents, ensuring alignment with centralized directives and facilitating continuous learning and adaptation through a curriculum of complex tasks.

Our approach integrates the environment’s observations and task directives to plan actions based on the current scenario. We begin by translating multi-modal observations into textual descriptions, utilizing a method that avoids direct scene captioning by the MLM. Instead, we extract keywords for items from the STEVE-21K dataset (Zhao et al., 2023) and employ GPT-4 to craft sentences that articulate these observations. The MLM identifies relevant condition sentences from textual observations during the planning phase. It also incorporates additional context, such as biome types and inventory levels, into text formats via predefined templates. We generate action plans by re-engaging the MLM’s linguistic component with the task instructions and these descriptive texts. This methodology leverages the MLM’s capabilities in a layered manner, yielding more accurate situational descriptions and plans that significantly reduce the likelihood of generating unrealistic elements compared to fully integrated models.

Autonomous error correction and proactive planning.

HAS enhances its planning through a closed-loop feedback mechanism, automatically correcting failures by analyzing feedback and identifying errors using its self-explanation capabilities. Unlike other agents, it generates improved plans without human input or extra information. Additionally, HAS simulates and evaluates each plan step to identify potential flaws early, reducing the likelihood of encountering difficult situations due to plan failures. This proactive approach enables it to foresee issues like insufficient resources, which could hinder task completion.

3 Multi-modal Memory

Research (Hong et al., 2023) has shown that memory mechanisms play a crucial role in the functioning of generalist agents. Equipping HAS with multi-modal memory enables it to plan using pre-existing knowledge and real-world experiences, improving planning accuracy and consistency. The MLM in HAS allows leveraging these experiences in context without requiring additional model updates.

We have illustrated the design of our multi-modal memory system. At a high level, this system is a key-value memory model with multi-modal keys comprising both the task and the observation of the state when this memory entry is created. The values stored in this memory system are the plans that were successfully executed. Since the plans are in an open-ended environment, Minecraft, there could be multiple entries with the same task but different observations and plans. As a result, HAS needs to generate multi-modal queries based on the current task and situations to retrieve the relevant memory entries.

Retrival-augmented storage (RAS) enables long-term planning capability by Retrieval-Augmented Generation (RAG) (Lewis et al., 2020; Mao et al., 2020b). RAG improves the quality of responses generated by language models with external sources of knowledge to complement the model’s internal representation. Instead of external knowledge libraries, we use the collected multi-modal memory as the knowledge library and retrieve interactive experiences as demonstration prompts to improve the planning results. The formulation is as follows:

where $x$, $y$, and $z$ represent instructions, plans, and retrieved memory entries. $p_{\eta}$ and $p_{\theta}$ denote retrieval and planning models. This retrieval-augmented planning method helps HAS to ground its internal knowledge into open-ended environments efficiently. It also leverages historical interaction feedback to solve hallucinations within LLMs and produce more accurate plans.

Multi-modal retrieval.

Multi-modal retrieval (MMR) enables efficient access to a rich repository of multi-modal memories. This process is initiated with a query containing textual and visual elements. To align this query with the trajectories stored within the multi-modal memory, we utilize the manager’s Describer $\mathcal{D}_{s}$. The Describer converts visual information into a textual format. This textual description serves as an image tag, amalgamating with other textual data or as a textual representation for audio information.

When a retrieval request is made from the multi-modal memory, especially when the information is an amalgamation of image and text, the Describer module $\mathcal{D}_{s}$ is employed to transcribe the image into text. Subsequently, this description is used to compute the similarity across the multi-modal memory entries. The top-k most similar entries are retrieved for further processing. The formalization of this retrieval process is as follows:

where $q_{t}$ denotes the textual query, $q_{v}$ represents the visual query, and $\mathcal{R}$ signifies the retrieval function. The function $\mathcal{S}$ computes the similarity between the multi-modal memory entries and the query, using the textual description provided by $\mathcal{D}_{s}$.

Dynamic map.

The dynamic map visually represents the exploration domain, showcasing only the areas the agents have explored. It is the main way for the manager agent to see the global environment. When using the map, it will be used in the form of an image. It is updated in real-time with information from all action agents, providing a strategic overview of the environment. This map is instrumental in planning and executing navigation tasks as it reflects the current knowledge and discoveries made by the agent collective.

The following equations can formalize the dynamic map’s function:

Where $M_{t}$ represents the dynamic map at time $t$, $S_{i,t}$ is the state information from agent $i$ at time $t$, including text data $\mathbf{txt}_{i,t}$ like the place name, special materials. $F$ is the function that integrates the text data into the map, and $n$ is the number of active agents. This real-time updating mechanism ensures that the dynamic map remains an accurate and current representation of the exploration field.

Experiment

Our experiments aim to achieve three goals using HAS in challenging Minecraft navigation tasks. Firstly, we want to evaluate the performance of HAS against baselines that do not fully address the issues faced by open-world agents. Secondly, we aim to understand the factors that contribute to these results. Lastly, we want to explore the potential of HAS for life-long learning and its benefits in long-horizon tasks. We will first introduce the evaluation settings, present the main comparative results and ablation studies, and conclude with an exploratory trial on long-horizon tasks.

We select gpt-4-1106-vision-preview (Yang et al., 2023) as the base model. Our simulation environment is based on MineDojo (Fan et al., 2022) and uses Mineflayer (PrismarineJS, 2013) APIs for motor controls. The maximum number of robots that can be allocated based on this environment is 8, which is also our experimental robots’ upper limit.

2 Baselines

Currently, no MLM-driven multi-agents (robots) work out of the box for Minecraft, so we carefully selected several representative algorithms as baselines for our experiment. They rely on extracting information from a system’s backend, presenting a significant divergence from real-world scenarios.

(Wang et al., 2023a) is a blind, single-robot system, relying only on textual grounding for perception. It has a long-term procedural memory that stores a hierarchical library of code-based grounding procedures. Complex skills can use simpler skills as sub-procedures. Voyager is known for its ability to explore areas and master the tech tree. However, its main focus is to prompt GPT-4 (OpenAI, 2023) on background text messages in embodied agents. We use multiple hosts to deploy multiple models to work directly on the server. We convert the input of the image goal into a text task through GPT-4V, using the same Describer module as ours.

STEVE

(Zhao et al., 2023) is a multi-modal single-robot system that combines the vision unit with the STEVE-13B with the code database. It focuses on introducing a visual module to endow the model with visual perception capabilities in processing visual perception information and handling task reasoning for skill-related execution. Similarly, using multiple hosts, we deploy multiple models to work directly on the server. This single-agent method optimizes performance. We also convert the input of the image goal into a text task by using the same Describer module as ours.

3 Task setting

We set the world on peaceful mode and agents always start in survival mode with an empty inventory so that navigation tasks can be performed without interruption. Meanwhile, we choose over 15 environment seeds of 6 different terrains from the STEVE-21K dataset (Zhao et al., 2023) for evaluation. The tasks we chose mainly test the efficiency of long-distance directivity navigation, short-range non-directional navigation, and free-world exploration.

A task is considered successful when the target object is close to the target or when a certain number of targets are reached. Due to the open-world nature of Minecraft, the world and initial position that the agent is spawned at could vary a lot. Therefore, we conduct at least 30 tests for each task and report the average efficiency and success rate to ensure a thorough assessment.

4 Evaluation Results

Multi-modal goal search includes goals of Image, Object, and Audio. Object labels identify in-game items such as villages, pyramids, and animals. Image labels help locate objects using images. Audio labels are used to detect sounds outside of the player’s range. Due to an insufficient audio library, we set the perceptible range around the target and passed it to the agent as text. It is similar to finding objects at close range, expressing distance through feedback intensity values.

As shown in Table 1, HAS achieves the best performance as a multi-agent system. Due to the auto-organizing mechanism, multiple agents can be better planned than directly adding multiple free agents. Even with a single-agent system, our performance is still the best. This is because our system decomposes tasks layer by layer, allowing both managers and action agents to maintain focus on their specific tasks. With the help of dynamic maps, the agent can be dynamically updated to understand the environment better globally. Our method has sufficient potential for performance growth. With the improvement of robots, it does not require too many robots to find a reasonable number of robots in the audio goal at close range.

Continuous block search.

Continuous block search is a close exploration mission to assess the agent’s exploratory capabilities and proficiency in locating multiple blocks in a row. Diamond blocks are placed at every 16-block interval across the mainland map.

As shown in Table 2, we experiment with the block-searching task (Zhao et al., 2023) to assess the agent’s exploratory capabilities and proficiency in locating specified blocks. Dynamic map is to identify as many blocks as possible within the fewest iterations, which indicates the method’s efficiency. The dynamic map and the self-organization of the hierarchical structure allow more blocks to be found and deployed.

Map exploration.

Map exploration aims to let the agent update the map as much as possible. We set up the same status awareness: when in an unreached area, status information prompts the agent in text. We set each step’s maximum movement distance not to exceed 50 blocks.

As shown in Table 3, HAS has achieved the best performance, especially on multi-agent, which can better reflect the hierarchical structure. It is of considerable value for macro-control of multi-agent exploration and avoids agents repeatedly wandering in the explored area.

5 Ablation Study

To understand the impact of different components on the performance of our system, we conducted ablation studies. The results, as shown in Table 4, provide insights into the effectiveness of the dynamic map and auto-organizing mechanism. Note that in w/o AO, we directly block the planner and deployer modules of the Manager to remove the auto-organizing mechanism and only retain the describer’s perception of the environment, including dynamic maps into status information, thereby directly acting on the same target task on a fixed number of agents.

Dynamic map is a multi-modal information body including images and status information. It can integrate data in the simplest way to provide global understanding, reduce additional overhead and provide the possibility of macro layout for multi-person cooperation.

Comparison with GPT-4.

Auto-organizing mechanism can dynamically adjust dynamic groups and automatically assign tasks based on the existing environment, allowing efficient multi-person cooperation.

Conclusion

In conclusion, HAS brings a significant advancement to multi-agent systems for complex environment navigation. Our contributions include a hierarchical auto-organizing system that ensures effective centralized planning and decentralized execution, an innovative auto-organizing and intra-communication mechanism for dynamic task adaptation, and a multi-modal information platform that integrates diverse sensory inputs. These advancements collectively enhance the autonomy, efficiency, and adaptability of AI agents, marking a pivotal step forward in the field of Embodied AI.

References