Multi-Robot Task Allocation and Route Planning for Indoor Building Environment Applications

Abstract

The operation and management of today’s complex built environments pose several challenges for building managers, who increasingly rely on location-based physical and information services for inspection and maintenance tasks. Recent advances in computing and cognitive capabilities enable the possibility of deploying robots for several operation and management tasks in the built environment. Potential examples of such coexisting built environment robot functions include indoor equipment delivery, environmental monitoring, inventory management, scheduled inspection, surveillance, wayfinding and search, and rescue. Coordination among robots deployed in indoor environments relies on the efficiency of task allocation and route planning. Previous studies have attempted to adapt existing algorithms used in outdoor logistics applications (such as genetic algorithm, Tabu search, and integer linear programming) and modify them with context-specific assumptions (e.g., existence of a unique Hamiltonian tour in the optimal solution). This often leads to suboptimal or infeasible solutions. For example, to visit a set of nodes in a graph network based on indoor environment, a Hamiltonian tour might not be possible. This paper addresses these issues and proposes a domain-independent framework to solve the multi-robot task allocation and route planning problems for centrally-located service robots charged with spatiotemporal tasks in indoor built environments. Scenario analysis is conducted to compare the performance of existing algorithms with the developed approach for route planning in building service robots. The results demonstrate the feasibility of the proposed approach in a range of applications involving constraints on both the environment (e.g., path obstructions) as well as robot capabilities (e.g., maximum travel distance on a single charge).