A distributed planning system for dynamic resource allocation

Timeliness is often an indispensable attribute in planning and problem solving for a command, control and communication (C{dollar}sp3{dollar}) environment. The success of a C{dollar}sp3{dollar} system is judged on its ability to respond to both routine and unscheduled tasks within a permissible time period ("window of opportunity"). A C{dollar}sp3{dollar} response is usually a plan that covers the following activities: resource allocation, plan execution and monitoring, and dynamic plan mending, if necessary. Resource selection for both strategic and reactive planning has to take care of various constraints. Decision making can become very time consuming when there are many resources and the number of constraints is large. Restrictive organizational structures and strict communication protocols cause further delays in decision making and execution in a command and control setup.; The nature of the C{dollar}sp3{dollar} problem lends it to the implementation and testing in a Distributed Artificial Intelligence (DAI) framework. Traditional approaches to planning in deterministic environments require a predictable amount of time to produce and execute plans. However, given more time, the system usually cannot improve on the plans. A distributed network of problem solving agents, using a hierarchical planning mechanism with skeleton plans, is proposed. The skeleton plans are refined into instances of action sequences and resource-mixes by employing a rule-based system with a time-critical inference mechanism. Rules are arranged in a hierarchy of priorities so that more and more details are taken into account with each iteration of the inference mechanism. This ordering also guarantees that the result of the planning process is always as good as possible within the time available.; As part of this research, dynamic scoping is presented as a mechanism to promote inter-agent cooperation and constrained lattice-like communications as an innovative message routing strategy. These mechanisms lead to improved resource utilization and reduced decision making times.