A Mission planning algorithm inspired by temporal difference learning for minimizing Makespan

doi:10.1007/s10951-025-00865-w

2026-01-01

PRE

Hwang, Nam Eung *

Kim, Joon Won

Kim, Hyung Jun

DOI：10.1007/s10951-025-00865-w

原文链接

原文求助

摘要

En 中文

任务规划算法通常通过将其转化为混合整数规划来求解多机器人-多任务问题。然后，基于计算出的成本通过分配算法制定任务计划，例如顺序贪心算法。通常，用于分配的成本设置为从当前分配状态分配更多任务时的实际增加成本。为了得到精确解，往往不能选择当前分配状态中成本最低的情况。然而，仅通过从当前分配状态分配更多任务时的增加成本，无法判断是否应选择成本最低的情况。换句话说，使用现有算法难以最小化完成所有任务所需的时间。为解决此问题，本文提出了一种受基于时间差分强化学习启发的任务规划算法。该算法由三部分组成：分配策略决策、基于策略的成本计算以及使用策略的任务规划。选择顺序贪心算法作为策略，并将所提出算法的性能与其他任务规划方法（包括暴力搜索法）进行比较。

Keyword:

Mission planning

Makespan minimization

Temporal difference

Multi-robot-multi-mission problem