HIDEHO: HIerarchical DistributEd Heterogenous Optimization

Large-scale military and civilian planning problems are (1) distributed – decision-making is spread across multiple organizations, including organizations that must employ information that they are unable or unwilling to share; (2) heterogeneous – the domains of optimization and local criteria for optimality differ – and (3) hierarchical – higher levels of authority solve abstract versions of the problem that must be delegated to subordinate echelons to solve in detail. There are a large variety of individual optimization tools available, based on techniques from Operations Research (OR), Constraint Programming (CP), Artificial Intelligence (AI), Multi-agent Systems (MAS) etc., but there is no wholly satisfactory framework for tying these point solutions into overall solutions that are (approximately) optimal. In Phase I we developed our HI-DE-HO (HIerarchical DistributEd Heterogenous Optimization) framework for solving distributed optimization problems.  HI-DE-HO combined developments from OR, CP, AI, and MAS. We showed how to decompose task-allocation optimization problems across a network of agents, and provide solutions guaranteed to achieve a fixed proportion of theoretical optimality. We demonstrated our technique using an abstract version of the Master Air Attack Plan (MAAP) problem, and evaluated it both analytically and empirically, showing that a distributed, hierarchical solution provides a guaranteed proportion of the theoretically optimal achievable quality, while providing feasible solutions much more efficiently.  In Phase II, we propose to expand our developments into a prototype system for distributed Air Force mission planning, building on a new domain-independent library for Distributed Hierarchical and Heterogeneous Mission Planning and Scheduling, and with enhanced algorithms for full-scale, real-world problems.