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

doi:10.1007/s10951-025-00865-w

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

2026-01-01

0

PRE

AI

DOI：10.1007/s10951-025-00865-w

Original

Original request for help

Save

Abstract

En 中文

Mission planning algorithms typically solve multi-robot-multi-mission problems by converting them into mixed-integer programming. Then, the mission plan is made through an assignment algorithm based on the calculated cost, such as a sequential greedy algorithm. Generally, the cost used for assignment is set to the actual increasing cost when assigning one more mission from the current assignment state. To derive an exact solution, it is often necessary not to select the case with the lowest cost in the current assignment state. However, it cannot be judged whether the case with the lowest cost should be chosen just by the increasing cost when assigning one more mission from the current assignment state. In other words, it is difficult to minimize the time taken to complete all missions using existing algorithms. To solve this problem, a mission planning algorithm inspired by temporal difference-based reinforcement learning is proposed in this paper. The proposed algorithm consists of three parts: assignment policy decision, cost calculation based on the policy, and mission planning using the policy. The sequential greedy algorithm is selected as the policy, and the performance of the proposed algorithm is compared with other mission planning methods, including brute-force.

Keywords:

Mission planning

Makespan minimization

Temporal difference

Multi-robot-multi-mission problem

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

Abstract

Journal

Organization

Cited Papers