Simultaneous Multi-Robot Task Scheduling and Path Planning

Abstract

Manufacturing processes often run on a schedule, because each production step takes a certain amount of time, after which a component is transported to the next machine. Mobile robots can be used to automate transportation of components between production steps. To do so, a task scheduler assigns transportation tasks to robots and a path planner calculates trajectories for robots to follow to complete their tasks.

In scientific literature, path planning and task scheduling are treated as separate problems. Typically, path planners use initial and goal positions as a given and task schedulers consider tasks of fixed duration. In this thesis, the integration of task scheduling and path planning is treated, resulting in three contributions. First, a novel cost function to minimise the duration of paths is proposed for an existing Mixed-Integer Linear Programming (MILP) formulation of the multi-robot path planning problem. Second, a new MILP formulation is developed for the scheduling problem of tasks with deadlines to be completed by mobile robots. Third, two methods for integrating the path planner and task scheduler are proposed. Through simulations these methods are compared with an integration method that uses rule-based scheduling, which assigns tasks to robots in a predefined order.

Simulation results show that the novel path planning objective function improves upon that from the literature by striking a balance between duration, distance, energy use and computation time. Furthermore, integration methods using the MILP scheduler have trouble outperforming a rule-based approach, caused by a practical limit on the computation time. Moreover, compared with single-robot path planning the use of multi-robot path planning is shown to improve performance at the cost of higher computation time. However, this improvement is negligible for environments with a lot of free space, where robots can easily avoid each other without making detours.

These results lead to the conclusion that the MILP path planner with the new path planning objective function performs well when integrated with a task scheduler. For restrictive physical environments, multi-robot path planning can further improve results. On the other hand, for practical applications a scheduling method other than the MILP scheduler should be employed to integrate task scheduling and path planning. The scheduling method should at least outperform rule-based scheduling with a practical limit on computation time, even if an optimal solution is not guaranteed.