Task scheduling and merging in space and time

[摘要] Every day, robots are being deployed in more challenging environments, where they are required to perform complex tasks. In order to achieve these tasks, robots rely on intelligent deliberation algorithms. In this thesis, we study two deliberation approaches – task scheduling and task planning. We extend these approaches in order to not only deal with temporal and spatial constraints imposed by the environment, but also exploit them to be more efficient than the state-of-the-art approaches. Our first main contribution is a scheduler that exploits a heuristic based on Allen’s interval algebra to prune the search space to be traversed by a mixed integer program. We empirically show that the proposed scheduler outperforms the state of the art by at least one order of magnitude. Furthermore, the scheduler has been deployed on several mobile robots in long-term autonomy scenarios. Our second main contribution is the POPMERX algorithm, which is based on merging of partially ordered temporal plans. POPMERX first reasons with the spatial and temporal structure of separately generated plans. Then, it merges these plans into a single final plan, while optimising the makespan of the merged plan. We empirically show that POPMERX produces better plans that the-state-ofthe- art planners on temporal domains with time windows.

[发布机构] University:University of Birmingham;Department:School of Computer Science

[关键词] Q Science;QA Mathematics;QA75 Electronic computers. Computer science