The author and his students were engaged in a multi-year project, SENTINEL, aimed at computerizing the strategic and tactical planning processes of the U.S. Coast Guard (USCG). In the course of this activity, we were also creating a decision support system for the human participants acting at the different levels of the USCG hierarchy. The chapter will describe the objectives, the problems and constraints of the task environment, as well as the solution to some problems that are fundamental and ubiquitous in many real-time, spatially and temporally distributed multi-agent systems. The fundamental and overall task of a Decision Support System (DDS) implemented was to allocate moving resources to moving tasks in an optimum manner over space and time while considering numerous constraints. We have introduced three significant innovations necessary to accomplish our goals. 1. Dynamic Scoping refers to a need-driven change in the size of the domain from which moving resources are called upon to accomplish moving tasks. The size of the domain has a limitation prescribed by the dynamic task environment, the technical capabilities of the resources, and the relationship between the expected gains and expenses. 2. The second innovation concerns “resource scheduling under time constraints.” We have introduced a method for the proper ordering of operating attributes and constraints in terms of a utility function. PRIORITY = IMPORTANCE*URGENCY Here, Importance is a measure of the relative static importance of an attribute in the decision making process. Urgency characterizes its gradually changing (usually increasing) relative importance over time. The constraints are arranged according to the priorities. More and more details are taken into account with each time-slice and more and more knowledge is used in the inference mechanism. A time-slice is the minimum time required for performing a unit of meaningful decision making. The ordering of constraints according to priorities guarantees that the result of planning is as good as time has permitted “so far.” 3. We have studied interagent communication and optimum message routing. Agents communicate at different levels—requesting and providing information, ordering/suggesting/accepting solutions to sub-problems, asking for and offering help, etc. The total knowledge about the environment and agent capabilities is too large to be stored by every agent, and the continual updating about the changes only aggravates the situation. The usual hierarchical organization structure for communication is inflexible, inefficient and error-prone. We have introduced the constrained lattice-like communication structure that permits direct interaction between functionally related agents at any level. The hierarchical and the lattice-like organizational structures may coexist: A transfer of temporary control over resources can be negotiated between the relevant agents directly while higher-level authorities will learn about the decisions, and can also modify or completely reject their implementation.