Applying heuristic search strategies to plan with re-configurable multi-robot systems

This thesis investigates heuristic search strategies that can be applied to planning with reconfigurable multi-robot systems. In the Vehicle Routing Problem (VRP), an optimal route for a set of vehicles to deliver a set of items to a set of customers is searched upon.  Temporal Planning for Reconfigurable Multi-Robot Systems (TemPl) is a constrained-based mission planner which introduces a mission description as a generalisation of the Vehicle Routing Problem (VRP). Due to this generalisation, heuristic search strategies used to find solutions in VRP could also possibly be used on TemPl. TemPl contains multiple constraints (spatial, temporal, load,inter-route) that aren’t considered by the classical VRP or its variants. Hence, heuristics used to solve VRP require to be adapted before applying to TemPl.For this reason, this thesis intends to evaluate existing literature and find heuristic search strategies  that can be applied to robot planning with TemPl. An implementation of a’solution-level heuristic’ and a ’constraint-level heuristic’ is used to determine the possible applicability of heuristic search strategies for robot planning.