Author Login Chief Editor Login Reviewer Login Editor Login Remote Office

Computer Engineering ›› 2026, Vol. 52 ›› Issue (10): 340-349. doi: 10.19678/j.issn.1000-3428.0252412

• Large Language Models and Generative Artificial Intelligence • Previous Articles     Next Articles

DAG-LLM: Multi-Robot Task Scheduling Method Based on Large Language Models

LIN Mingsheng*(), SHEN Liwei, DONG Zhen   

  1. School of Computer Science, Fudan University, Shanghai 200438, China
  • Received:2025-05-09 Revised:2025-07-21 Online:2026-10-15 Published:2026-10-23
  • Contact: LIN Mingsheng

DAG-LLM:基于大语言模型的多机器人任务调度方法

林明生*(), 沈立炜, 董震   

  1. 复旦大学计算机科学技术学院, 上海 200438
  • 通讯作者: 林明生
  • 作者简介:

    林明生, 男, 硕士研究生, 主研方向为机器人系统

    沈立炜, 副教授、博士

    董震, 副研究员、博士

  • 基金资助:
    国家重点研发计划(2022YFB4501803)

Abstract:

In the home service scenario, multi-robot systems need to process natural language instructions issued by non-professional users, which poses higher requirements for automated task scheduling. Existing multi-robot scheduling methods present limitations in terms of task understanding, dependency management, and resource optimization. To address these issues, this paper proposes a Directed Acyclic Graph (DAG)-Large Language Model (LLM) scheduling method to achieve full process automation from natural language input to multi-machine collaboration. First, this method first utilizes the LLM combined with environmental information for semantic parsing and task decomposition and generates a set of subtasks with execution constraints through the Chain-of-Abstraction (CoA) mechanism. Second, based on the LLM, a DAG is automatically constructed between subtasks to replace traditional manual modeling processes and accurately represent task dependencies. Finally, a backtracking algorithm is used to match robot skills with subtask requirements, combined with an asynchronous execution strategy to improve execution, and dynamic scheduling is used to reduce waiting time while ensuring dependency order. To verify the effectiveness of this method, three types of household tasks with different complexities (including four sets of scenarios) are designed in an AI2-THOR simulation environment for comparative experiments. Experimental data show that, compared with SMART-LLM and AutoTAMP, the DAG-LLM improves the task success rate by 41.4 and 57.7 percentage points, respectively, and reduces the running time by 24.3% and 6.3%, respectively. The results of an ablation experiment further demonstrate that task dependency modeling and asynchronous execution mechanisms play a crucial role in improving the system performance. The proposed method does not require manual involvement in task decomposition and dependency modeling, and it is suitable for the efficient collaborative scheduling of multi-robot intelligent agents in natural-language-driven application scenarios such as homes.

Key words: multi-robot task scheduling, Large Language Model (LLM), Chain-of-Abstraction (CoA), Directed Acyclic Graph (DAG), asynchronous execution

摘要:

在家庭服务场景中, 多机器人系统需处理非专业用户发出的自然语言指令, 这对自动化任务调度提出更高要求。针对现有多机器人调度方法在任务理解、依赖管理和资源优化方面的不足, 提出有向无环图(DAG)-大语言模型(LLM)调度方法, 实现从自然语言输入到多机器人协作的全流程自动化。该方法首先利用LLM结合环境信息进行语义解析与任务分解, 通过抽象链(CoA)机制生成具备执行约束的子任务集合; 其次, 基于LLM自动构建子任务间的DAG, 取代传统人工建模流程, 准确表征任务依赖关系; 最后采用回溯算法匹配机器人技能与子任务需求, 结合异步执行策略提升执行效率, 在保证依赖顺序的前提下通过动态调度减少等待时间。为验证所提方法有效性, 在AI2-THOR仿真环境中设计3类不同复杂度的家庭任务(含4组场景)开展对比实验。实验结果表明, DAG-LLM在任务成功率上相较于SMART-LLM提升41.4百分点, 相较于AutoTAMP提升57.7百分点; 运行时间分别缩短24.3%和6.3%。消融实验进一步表明任务依赖建模和异步执行机制对提升系统性能具有关键作用。该方法无需人工参与任务分解与依赖建模, 适用于多机器人智能体在家庭等自然语言驱动应用场景下的高效协作调度。

关键词: 多机器人任务调度, 大语言模型, 抽象链, 有向无环图, 异步执行