Task scheduling for mobile robots using interval algebra

We present a novel task scheduling algorithm for use on mobile robots in real environments. The scheduling problem is formalised as mixed integer program, which is a standard approach in the scheduling community. Our contribution is the use of Allen's interval algebra to prune the search to be performed by the mixed integer program. This significantly speeds up the algorithm. The proposed algorithm has been used on several mobile robots in long-term autonomy scenarios, where it schedules large sets containing a variety of tasks. The proposed algorithm outperforms the state of the art by at least one order of magnitude on both these real tasks and synthetic datasets.

Authors

• Lenka Mudrová
• Nick Hawes

Keywords

• Schedules
• Optimization
• Scheduling
• Algebra
• Mobile robots
• Mobile Robot
• Task Scheduling
• Interval Algebra
• Mixed-integer Programming
• Time Window
• Processing Time
• Time Constraints
• Autonomic System
• Travel Time
• Task Execution
• Time Instants
• Task Order
• Optimization Criteria
• Release Date
• Constraint Satisfaction Problem
• Constraints In Order
• Mixed-integer Programming Problem
• Task Properties
• Amount Of Tasks
• Pair Of Tasks
• Care Scenarios