Overview

Solving real military problems often requires solving hard optimization problems, such as scheduling, under stringent bounds on computation time. This usually requires us to abandon the hope of optimal solutions. Instead ‘anytime solvers ” are used: solvers that can rapidly produce some solution, possibly of low quality, then go on to produce better quality solutions if given more time. The common experience with anytime solvers is that the solution improves rapidly at first, but eventually progress slows down drastically. As the solution quality approaches optimality the computational effort required to make further improvements increases dramatically. This behavior is actually inherent in the problems themselves. When progress begins to require vastly increased resources we refer to this as a computational “cliff”. In a monolithic solver (one agent working on one CPU) avoiding such cliffs requires changing the solution algorithms themselves. In distributed, or multi-agent, systems the greater freedom of choice in building the system gives us new opportunities to avoid the cliffs. The study of “phase transitions ” is relevant because they concern cases in which small changes in a parameter, such as temperature, cause large changes in the resulting system, for example changing water into ice. These sharp changes correspond to the sharp changes in properties o