RBE MS Thesis Presentation
Multi-Robot Task Allocation and Scheduling with Spatio-Temporal and Energy Constraints
Abstract: Autonomy in multi-robot systems is bounded by coordination among its agents. Coordination implies simultaneous task decomposition, task allocation, team formation, task scheduling and routing; collectively termed as task planning. In many real-world applications of multi-robot systems such as commercial cleaning, delivery systems, warehousing and inventory management: spatial \& temporal constraints, variable execution time, and energy limitations need to be integrated into the planning module. Spatial constraints comprise of the location of the tasks, their reachability, and the structure of the environments; temporal constraints express task completion deadlines.
There has been significant research in multi-robot task allocation involving spatio-temporal constraints. However, limited attention has been paid to combine them with team formation and non-instantaneous task execution time. We achieve team formation by including quota constraints which ensure to schedule the number of robots required to perform the task. We introduce and integrate task activation (time) windows with the team effort of multiple robots in performing tasks for a given duration. Additionally, while visiting tasks in space, energy budget affects the robots operation time. We map energy depletion as a function of time to ensure long-term operation by periodically visiting recharging stations. Research on task planning approaches which combines all these conditions is still lacking.
In this thesis, we propose two variants of Team Orienteering Problem with task activation windows and limited energy budget to solve the simultaneous task allocation and scheduling problem. A complete mixed integer linear programming (MILP) formulation for both variants is presented in this work, and analyzed for scalability. This work compares the different objectives of the formulation like maximizing the number of tasks visited, minimizing the total distance travelled, and/or maximizing the reward, to suit various applications.
Thesis Advisor: Prof. Carlo Pinciroli
Thesis Committee: Prof. Jane Li, Prof. Andrew Trapp