HI-DE-HO: HIerarchical DistributEd Heterogenous Optimization

Smart Information Flow Technologies, LLC and University of Maryland, College Park (SIFT and UMd ) propose to develop and demonstrate HI-DE-HO (HIerarchical DistributEd Heterogeneous Optimization), a novel theoretical framework for distributed hierarchical and heterogeneous mission planning and scheduling for multi-domain operations. Large-scale military and civilian planning problems are (a) distributed, i.e., decision-making is spread across multiple organizations, including organizations that must employ information that they are unable or unwilling to share; (b) heterogeneous, i.e., the domains of optimization and local criteria for optimality differ; and (c) hierarchical, i.e., 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), etc., but there is no wholly satisfactory framework for tying these point solutions into overall solutions that are (approximately) optimal. HI-DE-HO is a novel framework for the design and mathematical analysis of suites of optimization and intelligent decision-support tools for DHHMPS problems. Our primary research directions will be combining technical results from OR and Computer Science (CS) into a unified approach to problem decomposition. CS researchers have developed techniques for decomposing problem models in ways that enable distributed solving and integration (often implicit integration) of partial solutions into coherent total solutions. However, CS researchers have paid less attention to questions of optimality than have their OR counterparts. Conversely, for specific mathematical programming problems, OR researchers have provided solution techniques for optimization. We will combine these two strengths to provide recipes for effectively decomposing problems, and translating them into mathematical forms that yield to known optimization techniques. We will also address the inverse problem: in many cases there already exist specialized optimizers for sub-problems, and those specialized optimizers form fixed points in system composition, and an integration framework must be built around them in order to achieve good coordinated performance.