Constraint Optimization Coordination Architecturefor Search and Rescue RoboticsMary Koes, Illah Nourbakhsh, and Katia SycaraCarnegie Mellon Robotics InstitutePittsburgh, PA{mberna, illah, katia}@cs.cmu.eduAbstract— The dangerous and time sensitive nature of adisaster area makes it an ideal application for robotic exploration.Our long term goal is to enable humans, software agents, andautonomous robots to work together to save lives. Existing workin coordination for search and rescue does not address the varietyof constraints that apply to the problem. This paper provides anexpressive language for specifying system constraints. We alsodescribe a coordination architecture capable of quickly findingan optimal or near optimal solution to the combined problems oftask allocation, scheduling, and path planning subject to systemconstraints. We address a perceived lack of benchmarks for thisresearch area by establishing a repository open to the researchcommunity which includes a set of benchmarks we designed toillustrate some of the complexities of the problem space. Finally,we evaluate various algorithms on these benchmarks.Following a natural or man m ade disaster, rescue workersrisk their lives searching f or survivors in a race against time.The search and rescue domain has the potential to benefitgreatly from robotic technology. Our vision is that robots coulduse a rough map of the environment, perhaps obtained froma blueprint or city map, and search areas specified by humanrescue workers.This problem not only has significant humanitarian benefitsbut poses a difficult research challenge. Robot teams in chal-lenging environments such as disaster sites will necessarilybe heterogeneous as cost limitations, power consumption,and size constraints require tradeoffs between mobility andcapabilities. Large scale disasters need to include robots withdiverse modalities (e.g. ground, air, water). Multiple robots areoften required to work together on a joint goal. Coordinationon a joint goal involves simultaneously solving two NP-hardproblems, task allocation and scheduling, as well as the pathplanning problem [1].Since each passing minute reduces the chance of success-fully rescuing victims, the quality of the solution is veryimportant. Furthermore, the system must accommodate a widevariety of system constraints on goals, robots, and resources. Aproblem formulation that does not allow for these constraintsis, for example, unable to handle the simple constraint, turnoff the circuit breakers before completing any other goals.These four aspects of the problem–heterogeneity, joint tasks,emphasis on optimality, and additional system co nstraints–distinguish the problem from other multirobot planning prob-lems. Research in market-based algorithms for coordination[2] and token based coordination algorithms [3] cannot effi-ciently reason about joint goals.The contributions of this paper are fourfold. In sectionI, we establish the objective for the team planning problemand present a first order logic constraint language for thesearch and rescue domain. In section II, we present COCOA,a Constraint Optimization Coordination Architecture, whichimplements the team objective and constraint language whileenabling us to employ state-of-the-art optimization engineslike CPLEX [4] to solve the team planning problem. Sincethe problem is NP-hard, findin g an optimal solution m ay taketoo long, particularly as robots must interleave planning andexecution due to the uncertainty in a disaster environment.In section III, we present a progressive algorithm that findsclose to optimal solutions very quickly and elegantly degradessolution quality with available time. Our fourth contributionis a set of benchmarks designed to illustrate some of thecomplexities of the problem space which we make ava ilableto the research community. We discuss our conclusions andfuture work in section V.I. TEAM PLANNING PROBLEM FOR SEARCH AND RESCUEThe coordination problem for search and rescue is part ofthe broader class of multi-agent planning problems. Withinmulti-agent planning, th e search and rescue problem falls intothe class of team planning problems since robots do not haveindependent goals but share the team’s goals. The coordinationitself is tightly coupled in that robots must frequently worktogether on a joint goal as no single robot working on thegoal is capable of achieving the goal by itself.A search and rescue problem consists of an environment, aset of robots, R, a set of goals, G, and a set of additionalsystem constraints, C. We assume that robots have someinitial representation of the environment, such as a blueprintof a collapsed building, but that there may be considerableuncertainty in the model.The set of robots on the team is defined as R :={R1,R2, ..., RN} where N is the number of robots on theteam. The set of goals is G := {G1,G2, ..., GM},whereMis the number of goals in the system. Each goal, Gm, has anassociated location in the environment, amount of time it takesto accomplish the goal or duration, dm, and reward, Qm(t).Internal to this problem representation is the assumptionthat there are a numbe r of relevant capabilities; capabilitiesmight include the ability to map the environment, check forheat signatures, manipulate objects, or extinguish fires. Eachrobot has a binary capability vector indicating whether or notrobot n has a relevant capab ility and each goal has a bin aryrequirement vector indicating which capabilities are needed.The last problem component is the set of system constraints,C. The expressiveness of the constraint language for the systemconstraints determines the scope of problems that can besolved. Goal, robot, and resource constraints form the buildingblocks for this constraint language.A. Goal constraintsAllen’s 13 temporal relationships [5] (before, equal, meets,overlaps, during, starts, finishes and their inverses) form thebasis for temporal goal constraints. Goal constraints are de-fined to hold if and only if both goals are scheduled, allowingfor a trivial solution of not scheduling either goal. In additionto the temporal relationships, the do constraint is necessaryfor cases where one or more goals must be accomplished. DoGmforces the goal to be scheduled at some time but does notrestrict when it is scheduled.B. Robot constraintsIt is frequently convenient to specify additional constraintson the actions of individual robots. Rescue workers may wishto specify which robots