Canadian Space Agency
A goal decomposition hierarchy (GDH) is a way of specifying behaviors for onboard autonomy and allows high level goals to be broken down into simpler subgoals that can execute sequentially or in parallel. We are nearing completion of a pipeline-based implementation of GDH in VHDL that can be executed on an FPGA. Simulation results indicate very high performance for this implementation. We intend to deploy this GDH implementation on a very low mass, low power, low cost FPGA card; these characteristics together with the ASIC-like speed up of programmable logic should facilitate the inclusion of autonomous behavior in onboard systems.
The Canadian Space Agency and Xiphos Technologies have been developing a low power, low mass computing node to support onboard spacecraft networking. The current version of the network node (called a Q-card) for laboratory development is based on an industrial grade Xilinx FPGA for which a radiation tolerant equivalent is available. The Q-card supports high speed networking between nodes, analog and digital I/O with external devices and simple command processing. Each Q-card provides a small increment in computing capacity with a corresponding small increment in the power requirement and therefore a Q-card based network can provide a better balance between power requirements and computational demand than is possible using larger processing modules of the traditional microprocessor-based solution. Q-cards support independent development of subsystems and simplify integration since hardware and software components can interact through simple well-defined network interfaces instead of the much more complex shared operating environment of a single processor. In addition the onboard network provides a certain level of fault tolerance since there are simple network topologies that for a given number n can tolerate n link or node failures. Tasks carried out on a failed node can be relocated to other nodes. Xiphos Technologies has also implemented a fault tolerant network solution [Edwards2003] that is able to monitor for faults, identify them and isolate them from the rest of the network.
Other programmable logic based implementations approximating ASIC-like performance for special purpose applications include Java interpreters [Gale03], encryption [Kancharla03], scientific computing [Storaasli03]. Goal decomposition hierarchies [Hartman02] provide a simple mechanism to organize alternative ways of achieving subgoals. This architecture is based on elements of hierarchical task networks [Erol94], Reactive Action Packages [Firby96] and Brooks' subsumption architecture [Brooks89, Brooks91]. Each goal has an activation condition that must be true in order for the goal to become active. In general a goal will have one or more decompositions into simpler subgoals or primitive actions with each decomposition having its own activation condition. The decompositions are ordered and, once a goal is active, the first one of its decompositions whose activation condition is true also becomes active. If none is true, no decomposition is applicable and the goal returns "fail". A decomposition can be a sequence of subgoals to be achieved in order or a set of subgoals to be achieved in parallel. Static parameters (evaluated once) can be passed from a goal to a decomposition and returned by a decomposition to the goal that invoked it. Similarly stream parameters, which are updated continuously, can be shared between a goal and the active decomposition. When a subgoal of a decomposition fails, the decomposition fails and the goal and decomposition activation conditions are evaluated again in order to find a new decomposition to activate. The activation process carries out a depth first search among the decompositions within a goal decomposition hierarchy looking for successful termination of the top level goal and in this way implements a simple kind of goal oriented behavior.
FPGA implementation of GDH
Executing a goal decomposition hierarchy involves several basic steps: for each active goal or decomposition, fetch parameters, evaluate the associated activation condition, interpret success or failure terminations by activating subsequent decompositions or subgoals or propagating the termination upward in the hierarchy and updating the representation of the current state of the goal or decomposition to reflect the result of the execution step. In the case of primitive actions, their execution continues given that the parent subgoal remains active and the primitive action has not yet generated its own success or failure indication.
There are at least several ways in which GDH execution could be implemented in programmable logic. The initial approach that we chose includes a pipeline for evaluating a single execution cycle of a goal or decomposition and off chip RAM storage for the GDH structure and parameters. The basic operation of the pipeline involves cycling through a list of active goals, subgoals and decompositions. Each such active object is fetched from the active list along with its parameters. The object's activation condition is evaluated; if it is false, currently active descendants are queued for termination in the next cycle. Success and failure termination indications of descendants are fetched and appropriate actions are taken: sequential decompositions activate the next subgoal or signal success to its parent, parallel decompositions signal failure to the parent or decrement the count of successful descendants and goals or subgoals signal success to the parent or look for new decompositions to activate in the case of failure.
In general performance of this design will be limited by bandwidth between the FPGA and RAM. Simulation of the VHDL implementation of the pipeline for the Xilinx Virtex II indicates that the basic execution rate of the pipeline could be as high as 100Mhz. For the Xiphos Q-card the transfer rate between RAM and the Virtex II is as high as 100MB/sec for contiguous blocks and about 20MB/sec for random access. Conservatively estimating an average of 50 bytes per active goal or decomposition to be fetched for each execution cycle, the execution rate of the pipeline including memory access time should be between 0.5Mhz and 2Mhz due to a combination of random and sequential access to RAM. Primitive actions that access large blocks of RAM will have an impact on this execution rate.
The end goal of the project is to demonstrate an onboard autonomy solution that has low mass, low power and low cost. Preliminary simulation results of our first VHDL implementation of GDH indicate a satisfactory rate for the basic execution step for an active goal. Completion and subsequent testing of this implementation should yield a relatively high performance system that can exhibit sophisticated autonomous behavior on Xiphos Technologies' Q-card, a platform that imposes very low requirements on onboard resources. The poster and paper will discuss the implementation and available test data in greater detail.
[Brooks89] Rodney A. Brooks, "The Behavior Language User's Guide", MIT AI Lab internal publication.
[Brooks91] Rodney Brooks, "Intelligence without representation", Artificial Intelligence 47 (1991), 139-160.
[Edwards03] Edwards, E., Lamorie, J., Hubert, M., Ricci, F., Lorenzini, D., "Flight Demonstration of a Fault-Tolerant Onboard Network ", ESA Data Systems in Aerospace (DASIA), May 2003.
[Erol94] K. Erol, J. Hendler, and D. S. Nau, "UMCP: A Sound and Complete Procedure for Hierarchical Task Network Planning," in Artificial Intelligence Planning Systems: Proceedings of the Second International Conference, K. J. Hammond, editor, pp. 249=96254, Los Altos, CA, 1994, Morgan Kaufmann Publishers, Inc.
[Firby96] J.Firby, Modularity Issues in Reactive Planning, Proceedings of the Third International Conference on AI Planning Systems, Edinburgh Scotland, May 1996, pp 78-85.
[Gale03] J.C.Gale, Gregory L. Wickstrom, Kwok Kee Ma, "Sandia Secure Processor a Native Java Processor", MAPLD 2003.
[Hartman02] L.Hartman, Reactive goal decomposition hierarchies for on-board autonomy, 53rd International Astronautical Congress, October 2002.
[Kancharla03] Pradeep Kancharla and Duncan A. Buell, The Advanced Encryption Standard on the HC 36m Reconfigurable Computer, MAPLD 2003.
[Storaasli03] Olaf O. Storaasli , Scientific Applications on a Reconfigurable, FPGA-based Hypercomputer, MAPLD 2003.
2004 MAPLD International Conference Home Page