AUTOPILOT: A Distributed Planner for Air Fleet Control

1 . INTRODUCTION

Distributed planning refers to the process by which multiple processors cooperate to achieve a set of common objectives . Development of distributed planning systems requires two major activities: the specification of architectures for structuring the cooperating processors, and the discovery and implementation of planning techniques to be used by each processor . We have unde rtaken both activities in an effort to develop methods for distributed control of aircraft moving through an air traffic control sector . This task domain has permitted us to investigate three important questions concerning cooperation:

1. \.'hat are the computational costs and benef its of different architectures for distributing planning functions?
2. How should distributed planners cope with incomplete and errorful information? Dist ributed planners typically possess different

* This research was sponsored by the Defense

Advanced Research Projects Agency (DOD) under Cont ract No. MDA903-78-C-0029 . The views and conclusions contained in this document are those of the authors and should not be interpreted as representing the official policies, either expressed or implied, of the Defense Advanced Research Projects Agency or the U.S . Government.

The flight plan for each aircraft (shown on the right side of Figure 1) displays, reading left to right, its status (active or approaching), its identifier, its current location (or origin, for pending aircraft), its destination, its altitude ( in thousands of feet), and its bearing. For example, aircraft R, will enter the airspace in one time-step of the simulation at infix location 2, heading northwest at an altitude of 6000 feet. Its dest i nation is exit fix 0 . A potential route for R would take R northwest to "''" and then north to 0 .

Successful control of aircraft issuing commands to navigate planes desired destinations and maintaining three miles of horizontal separation or of vertical separation between any two A violation of any of these constraints an error, as does allowing an aircraft to its fuel supply . requires to their at least 1000 feet aircraft . produces exhaust In our simulation, planning responsibility i!:i distributed among the aircraft . Each aircraft is controlled by an automated planner called AUTOPILOT. We refer to this allocation of function as an £Eject -£_ent~>red architecture for distributed planning. Whenever a n~w aircraft appears in the airspace, a new AUTOPILOT clone is created and perf orms all planning aud cooperation for that aircraft as it navigates from its origin to destination .

All AUTOPILOT c lones are behaviorall y identical and can be viPwed as virtuill copies of 11 generic ATC planner . The structurt.> of Al'TOPlLOT resemblPs that of un independent actor [1], o r object. as in S~IALLTAI.K [ 2], DIRECTOR [ 3], or ROSS [4] . In the current implementation, we simulate multiple planners by a single planning system that assumes different perspectives for each aircraft . The planner spawns offspring for differen t aircraft that contain the data base and world model specific to each. The computational expertise resides in the generic planner and can be applied to any of the various data bases .

4. THE AUTOPILOT DESIGN

AUTOPILOT contains a design kernel common to all architectural variants we have im·estigated. Figure 2 illustrates this kernel .

Several processing modules fun c tion as experts that share data and results via a common data base, the World Model . As in a Hearsay-like model [5, 6],--performance of these experts is triggered by particular conditions in the World Mode l, and each expert posts its results in the World ~lodel as new knowledge or changes to exist ing knowledge . The World Hodel contains such information as aircraft locations, their flight plans or assumed flight plans, and its own dest ination and tentative plans .

The Sensor receives simulated radar returns in the fo rm of airspace displays eve ry fifteen seconds. By comparing new displays to knowledge in the World Model, the Sensor compiles a list of location updates to be posted .

When AUTOPILOT is assigned to a new aircraft, the Pl an Generator produces a set of tentative flight plans to navigate the ai rcraft from its o r igi n to its des tination . The Eva luator tests these tentative plans against the real or infe rred f ligh t p l ans of other ai r craf t and posts pr<>dicted conflicts in the World ~lodel. The Plan Genera t or uses th is informa l ion to ei the r attach a minor patch to an ex isting plan or to rep l an comp l e tely .

The Communicator exchanges information and reques t s with other aircraft. When planning is thwarted by environmental uncertainty, the Communicato r may request locations or intentions from others. If the Plan Generator has failed to produce a conflict-free route, the Communicator may r equest other aircraft to patch or replan

their routes .

Finally, the Controller implements the aircraft 's flight plan . lt monitors the location of the aircraft and issues commands to alter course or a ltitude at the appropriate locations in the airspace.

5 . INCREMENTAL PLANNING

AUTOPILOT represents a plan in the World Model as a schema with several slots to be filled during the planning process . For example, the comp l e ted plan for aircraft R in Figure 1 is

( PI.AN008

Ali{CHAFT R

comtANDS ( a4 : o as)

CONSTRAINTS (( 12 13) (1 2 13) (4 1))

ROUTE

((12 13 6 285 ) (11 12 6 300 ) . .. )

CONFLICTS :!

CONFLICTSUM ((X (6 7))) (X (4 16)))

LENGTH 13

VALUE 106

PARENT NIL

OFFSPRING NIL) .

The slots in the plan schema contain information about the commands required to execute the plan, the x-y coordinates at which the commands must be executed, estimates of the overal l utility of the plan, annotations of the plan 's current predicted conflicts, and a four­ dimensional map of the executed plan (i.e., a specifica t ion of the location of the aircraft at each poin t in time) . Some slots in the plan schema are fill ed during plan generati on, some during evaluati on, and other during plan patching.

The following paragraphs discuss these processes in more detai 1.

5.1 . Plan Generation

AUTOPILOT produces route plans incrementally by planning approximately. The Plan Generator first produces with minimal effort a few standard routes from infix to the desired destination by indexing a library of plan templates . Each template is list of commands, indexed by infixjoutfix, that is guaranteed to take an aircraft to its destination from its entry fix . These plans are then evaluated to determine the nature and location of expected conflicts . Finally, the best plans are refined using a variety of techniques to produce local patches that avoid the conflicts . This incremental approach to planning has four advantages . First , it emphasizes the general adherence to designated airways and conventional rout i ng strategies. Second, plan failures are simple to diagnose and desc ribe; therefore, it is possible to patch accurat ely. Third, the incremental planning s trategy reflects the approach used by real air traffic controllers and by expert humans performing in the ATC simulation. Fourth, this strategy is well suited to the distributed planning environment, since predicted conflicts identify sets of aircraft that must cooperate to solve their common problem .

5 . 2 . Plan Evaluation and Conflict Detection

The Evaluator detects conflicts in candidate plans using a fast-time lookahead . Once candidate initial plans are generated, the Evaluator computes a four-dimensional route map of the locations to be occupied by the aircraft under each plan . Converting plan commands into route maps is costly; however this cost is offset by caching the results in the ROUTE slot of the plan schema. Hence, each plan undergoes this expansion only once . The route map is then compared to similar maps of the projected or known plans of other aircraft in the airspace. Maps are compared using an intersection search that requires maintenance of a 36-square mile window around each aircraft . Detected conflicts trigger annotations of a plan's problems and utility that are stored in the CONFLICTS, CONFLICTS~!, and VALUE slots of the plan schema .

5 . 3 . Plan Refinement

The Plan Generator r e fines initial plans whenever the Evaluator detects conflicts in every initial plan. The patches fall into three classes. Timing patches alter the time at which a plan's commands are executed without changing the commands themselves (e . g . , by deferring or promoting an altitude change command). Delaying patches insert new commands in a plan to delay an aircraft's arrival at a particular point (e.g., looping). Course alteration patches insert a detour to avoid the conflict location. This requires deleting several commands from the flight plan and replacing them with new ones .

These patch types are representative of more general replanning capabilities. For example, interpolating a loop is a kind of prerequisite insertion [7], and course corrections amount to

substitution of subgoals [8] .

Each patch is represented as a schema with slots encoding the computations required to evaluate patch effectiveness and modify a plan . The following presents an abstraction of a patch that inserts a left-loop into a plan :

(PLAN-PATCH LOOP-LEFT

TYPE

DIRECTION

PREREQUISITE

INITIATEPOINT

DELETECOM~!AND

ADDCOMNAND

COST

EFFECTIVENESS

delaying

left

<conflict point must not be too close to an airspace boundary else the loop will take aircraft out of airspace>

<use the earliest point that satisfies prerequisites and is prior to conflict>

nil

<turn left 360 degrees>

lo10

high)

To instantiate a patch schema for use with a particular plan, the Plan Generator attempts to satisfy the PREREQUISITES of the patch in the context of the plan . If successful, the Generator applies the heuristics in the INITIATEPOI~~ slot to select a point at which to insert a remedial command . The specific commands are then copied from the ADDCmi~IAND slot into the plan itself. In some cases (e.g., when deferring an altitude change), commands initially in the route must also be excised. The specifications for such deletions res ide in the slot DELETECON:1AND . Finally, the ROUTE slot is updated to reflect the new flight path entailed by the patched plan.

The patching process is best viewed as a search involving the Plan Generator and Evaluator as co-routines. The Generator iteratively expands a plan tree for the aircraft in the World ~lode! using possibly flawed initial plans as the parent nodes . Offspring are generated through the application of one or more patches to the initial plans. Patches are applied to copies of the parent plan rather than the original plan itself . Hence, the modified offspring are distinct data structures . Whenever a new plan is posted in the ~orld Model, the E~aluator criticizes the plan and posts the results of its critique.

The Generator selects plans for expansion (i . e . , patch application ) according to which current plan has the highest value in its VALUE slot . This value reflects the number of confli cts remaining to be resolved and the length of the flight path . Once a plan has been selected for patching, the Plan Generator applies only patches that generate better offspring (i . e . , have higher VALUEs) than their parents. This heur is ti c results in depth-first/best-first searches since offspring plans are always better than their parents. Planning terminates whenever one offspring plan has no conflicts or when the plan space is exhausted--that is, when no plan for the aircraft has a set of patches that remove all conflicts. In this case, the Evaluator selects the plan with the highest VALUE for execution.

In the current implementations, searches typically converge quickly on a solution . Rate of convergence is governed by the density o f solutions in the problem space (an inverse function of the number of active aircraft), the branching factor of the plan tree, and the depth of the plan tree. Both the breadth and the depth of the tree are limited . The branching factor is limited by the number of patch types kno10n and by the fact that particular patches do not ~atisfy all prerequisites for application in a given situation. Tbe depth of the tree is limited by the number of conflicts found in initial routes .

6 . DISTRIBUTED PLANNING ARCHITECTURES

We are currently exploring techniques for distributed planning in four versions of the object-centered architecture . The first two variants exemplify cooperation without negotiation . In the first version, the use of common planning rules and tocal inference obviates the need for communication of plan intentions. In the second, aircraft communicate their plans but not replanning requests. The third and fourth variants employ cooperative planning using different control regimes . The following sections describe these four variants and the modifications in the kernel planner they entail .

~ - l Object-Centered Autonomous--No Communication

In this most restricted form of cooperation, aircraft plan autonomously without communication . Thus, in this version we excise the Communicator from the AUTOPILOT kernel. In lieu of obtaining flight plans from other aircraft, the _Sensor infers their plans from altitudes, bearings: and nearest exit fixes or airports along their current flight paths .

Due to the uncertainty associated with such extrapolation, the Sensor must continually monitor the radar returns and the World Model to detect changes in aircraft locations and violated assumptions about their flight plans . Updating the hypothesized flight plans triggers new conflict detection checks by the Evaluator. If new conflicts are predicted, the Planner attempts to patch the current plan to avoid the new conflict(s) . If unsuccessful, the Planner dynamically replans a new route. Effective cooperation is achieved through the use of global "rules of the road" and precedence rules, like those used by operators of small visually­ controlled aircraft, boats, and automobiles .

6.2. Object-Centered Autonomous-­

Limited Communication

In this version an aircraft can request plans from other aircraft. Intentions can therefore be posted with certainty and route maps accurately modeled rather than merely estimated . This ve r s ion of AUTOPILOT therefore requires the Communicator, communications channels, and protocols. Proscribing negotiation among aircraft places the burden of maintaining aircraft sepa ratiou on the aircraft attempting to formulate a plan. As each new plane enters the airspace, it must develop a conflict-free plan with respect to the fixed flight plans of other aircraft already in the airspace .

The Sensor first posts other aircraft locations and the Communicator collect s and posts lhe flighl plans for these aircraft. Initial plan generat ion by the Planner may be interleaved with the functions of the Sensor and Commu'nicator . The ~valuator simulates the outcome of plan execution with respect to other aircraft locations and plans. If necessary, the Planner attempts to patch the plan to eliminate conflicts detected by the Evaluator. When either a conflict-free plan or the best available plan is posted as final, the Controller monitors execution of the plan .

The utility of these autonomous versions of the object-centered architecture depends on several attributes of the problem space and task domai n . First, autonomous planning, with or without plan communication, should succeed only when the problem space is dense in solutions--that is, so long as it is possible to produce a conflict -free plan regardless of the number and routes of other aircraft in the airspace . Second, autonomous planning is preferred over cooperative planQing when the cost (in time or resources) of local inferencing and planning i s l ess than the cos t of communications, negotiation, and

coordination.

Introducing negotiation into AUTOPILOT's plauning behaviors entails both costs and benefits. Inter-aircraft cooperation is desirable because the conflicting aircraft may have different options for resolving the conflict. One aircraf t may discover a simple patch for its plan while it may be impossible· for another aircraft to

remove the conflict in its plan .

However, complications arise from the need to synchronize local replanning activities. For exampl e, assume A has a route that conflicts at pl with B and at p2 with C. Suppose that A can patch its plan to remove its conflict with C but must rely on B to replan to remove their mutual conflict . B cannot assume that A's plan will remain fixed since A is patching its plan to accommodate C. In general, different conflicts (subproblems) may not be independent, and local planning cannot guarantee a globally satisfactory plan. Thus, cooperation through negotiation and communication requires effective coordination rt'_&.i_ID~~- The following two archit<·ctu~aTVIuia-;;ts embody d~fferent techniques for coordination. In each case, r eques ts for cooperation are initiated by an aircraft that fails to find a conflict-free plan for itst>lf.

6.3. Object-Centered Hierarchically Cooperative

In this version, the aircraft currently planning (A) orchestrates the attempts to eliminate conflicts from its plan. Figure 3 illustrates the coordination regime. A's Evaluator first selects its best plan . The Communicator then passes a message to another aircraft (say B) that conflicts with A's plan. The message contains A's plan and requests that B patch its plan under the assumption that A will execute its plan. If B's return message contains a successful patch, A makes the same request of the next aircraft (say C) with a predicted conflict. A passes both its plan and B's tentative patch. If C cannot patch under the given constraints, then A's Evaluator will abandon this plan , select its next best plan, and the Communicator will begin the negotiation process again.

6 . 4. Object-Centered Asynchronously Cooperative

The same type of cooperation may be achieved through asynchronous, parallel replanning efforts. In this case, the planner requ1r1ng assistance does not dictate a particular, favored plan. Rather, the planning aircraft (A) broadcasts its set of potential plans to all aircraft in the conflict set (B, C, etc.), but sends no constraints concerning what assumptions they must adopt regarding A's or the others' patches. Each aircraft simultaneously attempts to patch its own plan to remove conflicts predicted between it and A. Solutions are communicated to A as tentative plan revisions .

When B returns a plan to A that removes a common conflict, B also sends the assumptions under which it generated the solution--that is, the plan for A that B assumed in its revision . A must maintain a record of all proposed partial solutions and halt the replanning process when (a) it has received a complete set of conflict elimination patches for one of its potential routes, and (b) the proposed patched plans of the

other aircraft do not conflict with each other.

Such cooperation accelerates the planning process by exploiting the parallel processing capabilities of multiple aircraft. When numerous pairwise conflicts must be resolved, the sequential solution method entailed by hierarchical control may require too much time to converge on a solution. However, in the asynchronous cooperation regime, speed is achieved at the cost of additional bookkeeping and evaluation at A.

7 . SYSTEM PERFOR~IANCE

We have implemented the limited-communication autonomous variant and the hierarchical ly cooperative variant of AUTOPILOT in INTERLISP on a DEC-2060 at Rand-Al . They communicate over the ARPANET with the ATC simulation, a C program residing on a PDP-11/70. These variants differ only in the architecture in which AUTOPILOT is embedded, but not in the planning or sensing capabilities of each aircraft. Table presents performance data for these two architectures. Both perform with low error rates on simulation runs in low- to medium-density airspaces (i . e., 50-60 minute runs). In high-density airspaces (i.e., 30-40 minute runs), the hierarchically cooperative variant outperforms the autonomous system. This reflects the additional planning options that can be considered in cooperative architectures and that are required when air traffic is heavy .

Table 1

Mean Number of Unresolved Conflicts per Simulation Run

8 0 CONCLUS IONS

We have illustrated several methods for distributing planning responsibil i ty among multiple processors working toward a common set of objectives. In future work we will implement and evaluate the performance of other architectures and other variants on the object-centered architecture. ln so doing, we will emphasize the development of more sophisticated bargaining methods and communications protoco ls. We also hope to determine how dense in solutions a problem space must be to utili ze each of our developed architectures s uccess fully.

In order to demonstrate our candidote architectures, we have introduced several simplifi cations to our distributed planning environment. These include (1) simulation of multiple planners by a single planning program, (2) error-free communications, (3) limited routC' planning and revising hruristics, and (4) complete cooperation ~<"ith no competition among different aircraft . Our future work will remove these simplifications from our task environment . In particular, we plan to achieve true distribution by demonstrating multi-processor control of real autonomous vehicles.

Our current work also addresses goals extending beyond a repertoire of domain-specific planning and patching techniques . In particular, the object-oriented programming techniques we have developed suggest a general frame~ork for functionally distributed, communicating planners. At the same time, we currently know more about how to model cooperation than about what cooperation should be modeled. We still lack a theory of cooperation that would provide answers to questions such as: When should I request a plan from another? How much effort should I expend planning before requesting another to replan? Unde r what conditions should objects plan for others in addition to themselves? Such questions are at the heart of effective cooperation in many distributed planning domains .

ACKNOWLEDGMENTS

This work has benefitted from the substantial cont ributions o1 James Gillogly, Frederick Hayes­ Roth, Randall Steeb, and Robert Wesson.