Veloxiti's Cognitive Engine
Veloxiti’s knowledge engineering framework (or cognitive engine), VELOX, is based on McCarthy's view of AI which includes the topics of knowledge representation, inference, and planning.
Knowledge representation deals with how we represent the elements of a problem in software. Veloxiti’s approach to knowledge representation can be described in just a couple of sentences. First, we represent knowledge explicitly using knowledge graphs not by using IF-THEN rules or cases. Secondly, we use a knowledge acquisition approach for determining how these graphs are structured, and hence Velox is not a machine learning system.
An inference is a conclusion that can be drawn from the facts at hand. In an intelligent system, inference techniques enable a system to draw conclusions about the state of the world and to determine what should be done to deal with conditions of interest.
The Decide-Act components of the OODA loop correspond to McCarthy’s AI branch of planning. We can think of the Decide-Act graph as a way of organizing important goals to be achieved and the plans, which can be used for achieving these goals.
Velox Engineering Framework
A software engineer staring at a blank editor screen and a great American novelist staring at a blank sheet of paper share the same problem: How should I begin? The novelist begins by imagining a world populated with characters driven by a plot line. The software engineer begins by imagining how to create in software a model of the world that is good enough to solve the problem at hand. Of course, instead of characters and a plot line, software engineers think in terms of data sources, user interfaces, business rules, and algorithms. Knowledge representation deals with how we represent the elements of a problem in software.
Due in great part to AI research, engineers have a lot of representation options. To cite two examples, we might
- Use IF-THEN rules to explicitly represent knowledge in terms of antecedents (the “IF” part of the rule) and consequences (the “THEN” part of the rule).
- Use a neural net to implicitly represent knowledge within the hidden layers of the network.
We say that rules are explicit because it is possible to examine a rule and understand what elements of knowledge are being expressed. We say that neural nets are implicit because it is typically not possible to examine a network’s inner workings. In addition to distinguishing between explicit and implicit knowledge representation, we can also distinguish between representation formats that require knowledge acquisition vs. formats that provide for machine learning. IF-THEN systems typically require knowledge acquisition while neural net systems can be trained.
Knowledge representation is an enormous topic. We could expand the discussion by talking about additional kinds of neural techniques (e.g., associative memories), by considering approaches such as case-based reasoning, by discussing statistically based methods for both supervised and unsupervised learning and so on. All of these approaches are driven by underlying knowledge representation strategies – and each approach has strengths and weaknesses depending upon the problem to be solved.
Veloxiti’s approach to knowledge representation can be described in just a couple of sentences. First, we represent knowledge explicitly using knowledge graphs not by using IF-THEN rules or cases. Secondly, we use a knowledge acquisition approach for determining how these graphs are structured, and hence Velox is not a machine learning system. (However, later in this paper we explain how Velox can be integrated with many different kinds of AI components, including IF-THEN systems, Case Based Reasoners, neural nets, and so on.)
Graphs are widely used in a broad range of software contexts, particularly in AI applications. In a typical AI system the set of possible solutions to a problem can be represented as a graph, which can be searched to determine the “best” solution. Much of the early work in AI focused on development of efficient graph search algorithms.
Figure 3: The Observe-Orient and Decide-Act Graph
Consistent with our bias for OODA loop problem solving, Velox represents information about the state of the world in an Observe-Orient graph and information about plans in a Decide-Act graph (Figure 3). Consistent with our bias towards BDI models, the Observe-Orient graph represents beliefs, and the Decide-Act represents goals (i.e., desires) and plans (i.e., intentions). Though the graphs differ with respect to their detailed implementation, both the OO and DA graphs are acyclic, directed graphs.
Note that knowledge graphs are not the same as rule sets. As is done in all software, Velox applications do use If-Then statements: there is no escaping IF statements in programming. However, Velox does not represent domain knowledge as simply a collection of IF-THEN rules – we represent knowledge as beliefs, desires (goals), and intentions (plans) in a graph. Furthermore, the “engine” Velox uses for executing knowledge is not at all like the Rete algorithm typically used in rule-based systems.
However, there is a deeper distinction between Velox and IF-THEN systems. Conventional rule-based systems boil human reasoning down to antecedents and consequents – nothing more. We believe that human reasoning is too complex to be represented solely as IF-THEN rules. In fact, we believe that Boyd’s OODA loop and Bratman’s Belief-Desires-Intentions model provide a much richer context for problem solving. For example, the Velox Decide-Act graph provides developers with methods for controlling when a plan is proposed to a user, who has authority to execute a plan (i.e., the user or the system), the conditions under which plan execution should begin, and what should be done if a plan fails. Strictly speaking, it is possible to build IF-THEN systems with these capabilities but doing so is typically awkward and difficult.
In addition, the Velox framework is not based on machine learning. Unlike machine-learning approaches like neural nets, case-based reasoners, and statistical classifiers, the knowledge in a Velox application is more-or-less “fixed” during construction of the system’s Observe-Orient and Decide-Act graph. Velox applications are not trained – they are designed and constructed.
Unfortunately, this last statement implies that Velox knowledge is not only “fixed” during development but “set in stone”. This is an exaggeration since various techniques exist for parameterizing knowledge or adapting system behavior during execution. For example, the Army C-CAT application includes knowledge for selecting IR assets to be used for monitoring critical battlefield events. While the underlying logic is embedded within a knowledge graph, C-CAT provides a user interface for adding new kinds of IR platforms to the system’s table of assets. Innovative engineering enables development of knowledge graphs that provide a surprising amount of flexibility in the field.
Furthermore, Velox was designed from the outset to facilitate integration with external procedures and programs, which might well leverage machine learning. For example, it is surprisingly easy to incorporate Bayesian reasoning within the OO graph to facilitate probabilistic assessment of conditions in the world. Integrating with other kinds of AI is equally easy, making it possible to combine the benefits of OODA-loop problem solving with external components implemented using rules, neural nets, case-based reasoners, statistical classifiers, and so on.
An inference is a conclusion that can be drawn from the facts at hand. In an intelligent system, inference techniques enable a system to draw conclusions about the state of the world and to determine what should be done to deal with conditions of interest. Knowledge representation and inference techniques are inseparable topics. For example, conventional rule-based systems capture knowledge in rules. For large systems, the core challenge is to decide which rule(s) should be executed during each processing cycle. The Rete algorithm commonly used in rule bases provides an efficient means for selecting and “firing” rules. Because Velox represents knowledge in graphs, its inference component is essentially a graph traversal engine. Explaining how this engine works requires discussion of several detailed concepts.
Concept 1: Pattern and instance graphs
The discussion above describes the two knowledge graphs in a Velox application – the Observe-Orient graph and the Decide-Act graph. This description is a simplification; in fact, an executing Velox application actually has 4 graphs. In addition to distinguishing between a system’s OO and DA graphs, Velox makes a distinction between pattern and instance graphs.
Figure 4: The Class Definitions vs. Instances
Programmers who work with object-oriented languages such as C++ and Java are familiar with the distinction between a class definition and a class instance. Consider an application whose function is to determine whether an enemy air track is a threat to my aircraft. During development, we might define a class AirTrack that has attributes such as an ID, a Friend-Foe flag, an aircraft type, a maximum weapons range, a speed and a heading. Using these attributes, we could write a method for determining whether the enemy aircraft is – or will soon be – in range to be a threat. During execution, the system must track many air tracks, and thus the AirTrack class definition serves as a template (i.e., a pattern) for creating many AirTrack instances, one instance for each aircraft detected. Figure 4 illustrates this basic idea with a class definition on the left of the diagram and a class instance – which represents an actual track – on the right.
This distinction between patterns and instances is fundamental in Velox. During application implementation, Velox developers create two pattern knowledge graphs, a pattern OO graph and a pattern DA graph. These graphs are like class definitions in standard object-oriented programming. We can think of the pattern OO graph as a specification of all the beliefs that the system is capable of reasoning about. For example, an agent designed for use in air-to-air combat must be able to reason about the enemy’s weapons systems (air-to-air, ground-to-air, hand-held), sensors (radar, IR), and threat platforms. The OO pattern graph must represent the knowledge required for determining whether any particular platform like an aircraft or SAM site is a threat. Hence the pattern graph must represent all of the beliefs that are included in the scope of the system.
Figure 5: OO Pattern vs. OO Instance Graphs
At any point in time, an executing application’s OO instance graph will be a snapshot of threats believed to exist in the world. Consider Figure 5. A simple OO pattern graph is shown on the left hand side of the illustration. This instance graph will be structured in a manner that is consistent with the structure of the pattern graph. Hence, we might have 0, 1 or many active threats in the OO instance graph, depending upon what is happening in the world.
Engineers create the pattern graphs at design time. The Velox cognitive engine creates the instance graphs when data are provided to the system at runtime.
Figure 6: OO Graph Nodes and Links
Concept 2: Graph Nodes and Links
Like any graph, OO and DA graphs are composed of nodes and links. Figure 6 illustrates a notional OO graph in the air combat domain. In this case, the objective is to determine whether an air track is a threat given its position and the own ship position.
Without going into elaborate detail, we can make several generalizations about nodes and links.
- Graph nodes are primarily containers for keys and attributes – i.e., the properties or variables that describe an object
- Nodes may contain compute methods for setting the values of attributes
- Links contain methods known as constraints for determining under what conditions we can cross from a parent link to a child link
- Links also contain logic for setting the keys and attributes of child nodes
Recall the distinction between a pattern graph and an instance graph. Remember that the pattern graph is designed and implemented when a system is developed. Instance graphs, though, come into existence only when a system is running. The OO instance graph captures what we know about the world, and the DA instance graph captures what we are doing to deal with conditions of interest in the world.
So, we can think of the template graph as a set of instructions for creating the OO and DA instance graphs during system execution. Links are important because they contain the control logic for determining when nodes in the instance graph should be created. Links are also important because they contain the logic for propagating data values from parents to children in the graph.
Though both are composed of nodes and links, the OO and DA graphs have some important differences. We refer to nodes in the OO graph as Beliefs, a convention that is consistent with the BDI software model. The DA graph is composed of Goal nodes and Plan nodes. A Goal corresponds to a BDI desire; a Plan corresponds to a BDI intention. As was done in the PA programs Plan-Goal Graphs (Figure 2 above), goals and plans in a DA graph are organized as an And-Or graph governed by the following rules:
- Goal and Plan nodes alternate in the graph. In other words, Goals may have child plans and Plans may have child Goals
- All of a Plan’s sub-Goals need to be accomplished in order for a Plan to succeed
- Any one of a Goal’s sub-Plans should be sufficient to satisfy the parent Goal
Concept 3: Graph Traversal
Recall that McCarthy identifies inference as one of AI’s key branches. The Veloxi cognitive engine is an inference engine that performs a very basic function during system execution: using the instructions encoded in the OO and DA template graphs, it uses currently available data to incrementally create the OO and DA instance graphs.
Referring to the Air Track example shown above, assume that own ship’s radar system has just detected an air track for the first time. When provided with this data, the Velox cognitive engine will either create a new node instance or update an existing instance of the AirTrack belief. Then the engine will use the instructions in the OO pattern graph to instantiate additional instance graph nodes. Starting with new AirTrack node, the engine will evaluate the constraint logic contained in the link between AirTrack and AirTrackThreatStatus. If the constraint returns TRUE, then the engine will create an instance of AirTrackThreatStatus and set key and attribute values in AirTrackThreatStatus using the link’s setKey and setAttribute methods.
Concept 4: Monitors
The cognitive engine’s core function is to incrementally create the OO and DA instance graphs using the logic coded in the OO and DA template graphs. That being said, there are some details that need to be considered.
OODA loop problem solving is typically driven by changes in the situation. So too is processing in a Velox agent. A cognitive processing cycle begins when the situation changes. When data describing the situation are provided, the engine updates the OO instance graph according to the instruction in the pattern knowledge. This may result in belief instances being created, updated, or revoked.
Some changes in the situation are important; other changes are not. For example, it is useful to know that an enemy aircraft is far away and on a heading that will take it even farther away. However, it is critical to know that an aircraft has just approached close enough to be capable of attacking one's own ship. In the first case, the changed situation likely does not require a change in tactics. In the second case, survival depends on the pilot’s response. The OO graph handles these high priority conditions of interest by way of monitors.
A monitor is similar in principle to a database trigger. A monitor “fires” when a condition of interest is detected. Monitors serve to bridge the gap between OO graph processing and DA graph processing. The firing of a monitor triggers processing in the DA graph that focuses on addressing the challenge posed by a condition of interest. For example, the monitor that fires when an enemy aircraft gets too close might be linked to a DA goal node labeled “Threats Neutralized.”
The cognitive engine’s processing cycle begins when new data become available in the OO instance graph. The engine incrementally updates the OO instance graph. If a condition of interest is detected, the engine fires a monitor and turns its attention to the DA graph. Because monitors point from a Belief node to a Goal / Plan node, the cognitive engine knows where to begin processing when a monitor fires. As is done in the OO graph, the engine uses knowledge encoded in the DA pattern graph to incrementally construct a DA instance graph.
The cognitive engine’s underlying algorithm is “greedy”, meaning that the engine aggressively tries to instantiate OO and DA nodes. When the engine can do no more processing in both the OO and DA graphs, it pauses and waits for new situational data to be provided to the OO graph.
The Decide-Act components of the OODA loop correspond to McCarthy’s AI branch of planning. In the discussion above we described the Decide-Act (DA) graph as an And-Or graph composed of alternating Goal and Plan nodes. We can think of the Decide-Act graph as a way of organizing important goals to be achieved and the plans, which can be used for achieving these goals. Using BDI terms, goals are desires and plans are intents. If we think of the DA graph as simply a means of organizing knowledge, then we can treat implementation as a separate topic. In other words, we could use any kind of technology for building the Decide-Act portion of an OODA-loop system. In fact, during the Pilot’s Associate program, an And-Or graph was used primarily for organizing and structuring air combat domain knowledge.
Now, it turns out that Veloxiti’s approach uses DA graphs in a very direct manner. The Velox planner is a skeletal planner. Specifically, we generate plans by decomposing high-level goals into lower-level plans. Using AI-speak, the Velox cognitive engine performs top-down, decompositional planning. This approach differs from a number of different planning approaches such as case-based reasoning, generative planning, or methods that rely on machine learning techniques.
Note also that the Velox planner is a reactive planner, meaning that it is designed to respond to changes in the situation. The planner selects plans that are capable of satisfying parent goals, but these plans may not be optimal. This feature enables the planner to be quick. When a plan is instantiated, the planner continuously monitors the plan to ensure that it remains viable given the changing situation. If the situation has changed sufficiently that the plan is no longer capable of satisfying its parent goal, the plan is revoked and re-planning occurs.
As is done for the OO graph, the DA graph created during development is a pattern graph. During execution, the Velox cognitive engine uses this knowledge graph as a template for creating an instance graph, just as is done in the OO graph. When new data become available, the cognitive engine traverses the DA pattern graph and incrementally constructs a DA instance graph. In addition, though, there are a number of subtleties that need to be addressed during planning that do not apply to situation assessment. For example, when should plan execution begin and how do we know when a plan either completes successfully or fails? Furthermore, who should be responsible for executing the plan – the user or the system acting on behalf of the user? Velox addresses these issues by tagging plans and goals with a lifecycle state to provide fine-grained control over plan execution.
Are Other AI Techniques Compatible with Velox?
Veloxiti builds intelligent systems that leverage the OODA loop and the BDI model. Does this mean that Velox precludes other AI techniques such as machine learning, statistical algorithms, generative planning, pattern recognition and so on? Actually NO – our approach to intelligent systems is compatible with many different AI technologies.
Recall that a Velox knowledge graph is composed of nodes and links. Nodes in the OO graph are beliefs; nodes in the DA graph are goals and plans. Links in either graph are just links. Recall also that the Velox cognitive engine traverses the OO and DA pattern graphs to create an instance graph that represents our beliefs about the state of the world plus goals to be achieved and plans for achieving goals.
Broadly speaking, the Velox cognitive engine has two fundamental functions:
- As it traverses the template graph, the cognitive engine evaluates logic contained in links to determine which paths to follow in the graph. This control logic is embedded in the link’s constraint method
- When it creates a node (i.e., a belief, goal, or plan), the engine sets the values of attributes in the node using a compute method
Stripped down to bare-bones basics, the Velox cognitive engine evaluates link constraints to determine how to traverse the OO and DA graphs, and it uses computes to set values of attributes in nodes. That’s essentially all it does.
In most cases, constraint logic and compute logic can be encapsulated within links and nodes using plain Java code. However, we need not think in such limited terms. Velox is enormously flexible and it is perfectly feasible – almost trivial – to invoke external algorithms and programs, from link constraints or node computes.
For example, Veloxiti used a statistical algorithm known as Continuous Value at Risk (CVAR) to identify vehicles on a road segment whose speeds were significantly slower than average based on MTI (moving target indicator) data. Though originally developed for use in financial modeling, the CVAR algorithm was adopted for use with MTI (moving target indicator) radar data. For this application, the CVAR algorithm was invoked from a node compute statement to identify vehicle speed outliers on road segments. In this case, the external algorithm was a statistical technique, but a neural net, an associative memory or some other AI technique could perhaps serve the same function.
Recall the discussion above dealing with the PAL framework and the Universal Information Management Architecture (UIMA). Both PAL and UIMA are specifically designed for integrating many kinds of AI. We see a similar role for Velox. In our case, the OODA loop and BDI principles provide a model for organizing and controlling higher-level thinking and decision-making. Other AI techniques such as rules, pattern recognizers, case-based reasoners, and machine learning components can provide lower level services that can be invoked as needed. This layered view of problem solving reinforces the value of integrating Velox systems with external AI systems.
The Velox Tookit
Figure 7: The Velox Implementation "Stack"
Not too many years ago, true AI researchers wrote code in Lisp, a programming language invented in the mid-1950’s. Though elegant and powerful, Lisp is also difficult to learn and infrequently used today.
Velox is a development toolkit for engineers who may not know Lisp and may not have graduate training in AI. Velox leverages Java and the Eclipse framework, two of today’s most commonly used development tools. Figure 7 illustrates how Velox works.
The Velox toolkit is a set of Eclipse plug-ins. Eclipse is an open source software development framework. A “plug-in” is an extension to Eclipse’s core capabilities. One of our key objectives was to simplify development so that ordinary Java engineers – rather than AI graduate students – can build intelligent systems. To that end, we created two graphical editors, one for creating OO graphs and one for creating DA graphs. These graphical editors allow users to draw, connect, and annotate beliefs, links, goals, and plans. Because it would be tedious to graphically create all of the code for a program, the graphical editors are synchronized with text editors that function much like the text editors developers typically use. The graphical and text editors are synchronized, meaning that changes in a graphical editor are reflected in the text editors and vice versa. Inside the text editor, knowledge is represented in the Velox Domain Specific Language (DSL), a simple dialect of Java specialized for building knowledge graphs that are composed of beliefs, monitors, goals, and plans. Developers write code using this DSL.
Returning to Figure 7, note the Cognitive Engine at the base of the diagram. The base classes defined at this layer contain the core logic used for setting attribute values, traversing graphs, firing monitors, and so on. Base classes exist for beliefs, monitors, goals, plans, and links. The Cognitive Engine classes are provided in a library that developers need not modify.
Figure 8: The Velox Development Tool in Eclipse
Sitting between the DSL Code layer and the Cognitive Engine are a set of Generated Java classes. When a developer creates a node or link using the graphical and text editors, the Velox toolkit automatically generates a Java class definition that derives from a cognitive engine class and that has specialized behavior based on the DSL written by the developer. Code generation is absolutely transparent – developers need not do anything special to generate code.
Figure 8 illustrates the Velox Designer. The top pane in the figure is a text editor displaying a DSL snippet; the bottom pane is a graphical view of an OO graph. Velox has a look and feel similar to the numerous Integrated Development Markets available via Eclipse. The Velox learning curve for a reasonably capable Java programmer is minimal.
Because Velox generates plain Java code, it’s possible to integrate a Velox application with external data bases, programs, user interfaces, web services, and so on using any of the mechanisms supported by Java. Furthermore, the toolkit includes modules for choreographing the behavior of multiple Velox agents in a system of systems.
The Warfighter’s Associate is an instance of an intelligent decision support system implemented using Velox, Veloxiti’s framework for building AI systems. Velox is a uniquely capable tool for building military domain applications because it leverages the OODA loop and the BDI software architecture, a well-respected theory of human action.
Velox is not a rule-based system, nor is it a machine learning system. Velox represents knowledge using two graphs – one for Observing and Orienting and one for Deciding and Acting. The Velox uses the OO and DA pattern graphs during system execution to build a model of the situation in an OO instance graph and a model of actions to be taken in a DA instance graph. Like commercially developed frameworks such as IBM’s Unstructured Information Management Architecture, Velox is designed for integrating many kinds of AI.
The Velox design tool is an Eclipse-based set of graphical and text editors for creating and integrating intelligent systems. It has been explicitly designed to simplify the implementation of complex OODA-loop applications.
The Data Analysis Tool (DAT) is an application for measuring both individual and team performance. It has been used successfully in a number of human-in-the-loop experiments performed by ARL’s Human Research & Engineering Directorate.