Multi-Robot Coordination in Domains with Intra-path Constraints

Abstract

Many applications require teams of robots to cooperatively execute tasks. Among these domains are those in which successful coordination must respect intra-path constraints, which are constraints that occur on the paths of agents and affect route planning. One such domain is disaster response with intra-path constraints, a compelling application that is not well addressed by current coordination methods. In this domain a group of fire truck robots attempt to address a number of fires spread throughout a city in the wake of a large-scale disaster. The disaster has also caused many city roads to be blocked by impassable debris, which can be cleared by bulldozer robots. To produce coordinated agent behavior that satisfies the requirements of this domain entails not only allocating fires to fire trucks, but also determining what routes fire trucks should take given the presence of debris piles and which bulldozers should be assigned to clear debris along those routes. To determine high quality coordinated plans in domains with intra-path constraints requires that agent interactions be considered when making path planning, allocation, and scheduling decisions. This thesis addresses the problem of coordinating agents in such domains, with the goal of determining high quality coordinated behavior while minimizing the time required for computation. Different scenarios involving domains with intra-path constraints will vary in terms of the nature of the constraints, the level of uncertainty in the environment, and the time available for computation. The central contribution of this thesis is a suite of different approaches for effectively coordinating behavior in domains with intra-path constraints, each of which has strengths and weakness and each of which may be most appropriate given scenario requirements and specifications. One technique we employ is greedy, market-based coordination. In our market-based approaches, we seek to exploit the structure and independence inherent in domains with intra-path constraints to develop heuristics and bounding routines that serve to improve the quality of agent behavior while limiting the required computation. Our other primary technique is a randomized evolutionary search method that employs genetic algorithms. The genetic algorithm approach can potentially avoid local performance maxima that can result from using the market-based methods but requires orders of magnitude more computation. In addition to our suite of approaches, this thesis formulates domains with intra-path constraints as a distinct problem space within multi-robot literature and comprehensively treats the scenario factors that must be considered in approach design. Further contributions include a tiered auction methodology that extends market-based methods to domains where forming accurate bids requires soliciting the help of other agents; the first tractable time-extended allocation approach to domains with intra-path constraints; and the first approach that employs genetic algorithms within a domain where allocation and path-planning are inter-constrained.