Task Fusion Heuristics for Coalition Formation and Planning

Automating planning for large teams of heterogeneous robots is a growing challenge. The planning literature incorporates expressive features, but examples that scale to multiple robots in complex domains are limited and fail to generate feasible plans. The Coalition Formation then Planning framework accelerates planning by decomposing the robots into coalitions, allocating tasks to each coalition, and planning each task separately. However, the task decomposition limits cooperation between coalitions and results in many nonexecutable plans. The presented Task Fusion heuristics fuse coalition-task pairs, resulting in higher success rates by leveraging relaxed plans to estimate couplings between tasks and determine the coalition-task pairs to be fused. The heuristics are compared to baseline methods across randomly generated problems that incorporate temporal and continuous constraints.