Agent Itineraries

At the time this article was written, the authors were members of the engineering staff at Lockheed Martin Advanced Technology Laboratories. They can be contacted at [email protected], grao@gradient. cis.upenn.edu, and [email protected]. upenn.edu, respectively.

Itineraries are used in many agent architectures, including the Concordia, IBM-Aglets, Voyager, Oddessey, and EMAA agent architectures. These architectures treat an itinerary as an enumeration or list of tasks to be performed by an agent. In this article, we'll take a different approach, treating an itinerary as a metaprogram -- a way of programming an agent and inadvertently its goal. In the process, we'll show how easy it is to build agent architectures using Java and a few straightforward concepts. Our ultimate goal is to illustrate how you can enhance agent architectures by concentrating on a critical data structure -- the itinerary. A flexible, generic itinerary data structure allows for greater expressive power when defining application-specific agents.

To illustrate itineraries, we'll present an itinerary that performs a straightforward database query. However, we've implemented itineraries on several real-world applications, including a distributed fault-tolerant information discovery system. In that system, agents performed abstract queries using a syntax similar to what you would use on the Web through, say, Lycos or Alta Vista. The agents were able to overcome problems such as low-bandwidth, frequently disconnecting networks, or even database machines being temporarily unavailable. Another application in which we've used itineraries is a distributed data fusion/threat-assessment engine, where the agent moves among computers monitoring real-time signals from sensors. The system then uses the data-fusion logic to sense nearby threats.

Our approach to agent itinerary borrows ideas from a fundamental computing model -- the Finite State Machine (FSM). Theoretically, FSMs attempt to capture the general nature of computation of certain computational procedures. Conceptually, FSMs have a finite set of states, alphabets, and instructions. Physically, they can be visualized as a model of computation that has storage capable of remembering their current state. They also have the capability to read input and compute both a next state function and an output function. The next state function determines the next state the machine should be in based on the current state, the input, and a simple set of instructions that map input signal and state pairs to a new state. The output function determines the output alphabet of a machine for a state (see Figure 1).

Formally, an FSM is a sextuple like that in Figure 2(a), where K is a finite set of states that the machine can be in, is a finite set of input symbols, O is a finite set of output symbols, and s is the initial state. The Next State function, _s in Figure 2(b), is the program to the FSM and is called the "transition" function. It specifies, for each combination of current state s K and current symbol i , a new state s' K; see Figure 2(c).

Finally, _o: K O, the output function, specifies the output symbol for each state. A configuration of an FSM is an instantaneous description of the machine in its computation path. A configuration specifies the current state, and input symbol being scanned by the machine and the output symbol.

So what does this mean? FSMs can be used to simulate certain computational procedures. They are good for describing the general flow of an algorithm responding to input. The implicitly generic nature of the transition function provides much of this power. At the same time, we view an agent's itinerary as a metaprogram, or as a way of programming an agent. It is basically a set of commands for controlling an agent by specifying the tasks that are to be performed under certain conditions. We start by borrowing some concepts of an FSM with the hope that the metalanguage is flexible and has the expressive power to describe complicated itineraries.

Formally, we define a Finite State (FS) itinerary as the quadruple in Figure 2(d), where K is a set of states that the agent can be in. The state of an agent describes the task or program that the agent executes. is a set of conditions where a condition is basically a trigger upon which the agent acts, much like an FSM's computation path depending on the input alphabet. Simply put, the result of the evaluation of a condition occurring in real time is what causes an agent to enter a state, executing the program represented by that state.

We define c as the initial configuration of the FS itinerary, where a configuration is a state-condition pair; see Figure 2(e). In other words, the configuration is the current state of the agent and the most recent condition that has been evaluated. Configurations arising during execution of the itinerary are generated in real time. This lets the agent react to real-time situations.

Finally, , the transition function, is the metaprogram for the agent's itinerary. It describes the transition from the current configuration to the next configuration. The transition function is basically a way of programming an agent to execute certain programs (specified by a state) under certain conditions. Any subsequent configuration is obtained by examining the current configuration's state and by evaluating its corresponding condition at run time. This is the fundamental difference between the FS itinerary approach and that taken by existing agent systems that incorporate the concept of an itinerary.

As Figure 3 shows, the FS itinerary is basically a data structure capable of storing a transition graph of various configurations that describe to the agent how to move from one configuration to another. The data structure is similar to an FSM.

Any particular instance of an agent will define to its FS itinerary the metaprogram (transition function graph) that will navigate the agent through various configurations. The initial state of the initial configuration is spurious and is not the result of any condition. The FS itinerary will start with the initial configuration and evaluate the initial condition specification. Evaluating a condition specification will depend on real-time conditions that exist around the agent (analogous to input symbols to the FSM) and the result of this evaluation is an indication of the current conditions. Once the current conditions have been evaluated, the FS itinerary invokes the transition function to get the next configuration to move into. The transition function determines the next configuration based upon the current conditions and the state of the agent. This new configuration indicates the new state for the agent, and the FS itinerary will execute the program associated with this state. The FS itinerary again evaluates the condition specification of this new configuration and in this manner, continues to execute the metaprogram of the agent, until a final (halting) configuration has been reached.

Java and a Layered Agent Architecture

As Figure 4 illustrates, the agent system we present here is implemented as a layered architecture. At its core lies the FS itinerary, with functionality added in layers. The agent layer provides an interface around the system to the agent applications. A good design for the agent layer would shield you from the intricacies of mobility and state transitions.

Listings One through Five present the Java package finitestateitinerary, which defines five components that comprise the FS itinerary block.

The State component (Listing One) generically represents the program to be executed by the itinerary on reaching this state. The component is implemented as a Java abstract class. Its functionality is defined in the run() method and is application dependent. Furthermore, it declares two static states, INIT and HALT, that are standard to any agent metaprogram.

The Transition Function interface (Listing Two) represents the transition policy in choosing the next configuration for the FS itinerary. Your implementation of this interface will evaluate run-time conditions to select a new configuration. As we will see in our example, such conditions may depend on previous states. As far as the FS itinerary is concerned, all that is required of this component is the ability to return the next configuration.

Listing Three is the Configuration component, a placeholder for the State component and the transition function at that node in the FS itinerary. This component extends the State class and implements the Transition Function interface. The class FSIConfiguration (Listing Eight) implements the Configuration component. FSIConfiguration stores a reference to the state that is to be executed when the FS itinerary enters this configuration. It defines an addTransition() method that maps a condition (Listing Nine) to a new configuration. This is a key function in building the finite-state-transition graph that defines the metaprogram. In its implementation of nextConfiguration(), this class returns the configuration associated with the first condition that was satisfied, giving a very simple transition policy. The run() implementation of this class calls the run() method on the state object that it contains. We will see in our example that there will be certain configuration transitions that do not depend on any condition evaluation. The condition component defines static DEFAULT_CONDITION for this purpose and it always returns True, causing the configuration that it is associated with to always execute.

In Listing Six, we define a mobility condition. This is the first building block toward agent mobility and a good example of a condition object. The purpose of this condition is to evaluate whether there is a need for the agent to migrate to a destination machine. The run() implementation of the MigrateState class (Listing Seven) migrates the FS itinerary to the desired machine. The combined effect of the mobile condition and state is that when the mobility condition is added to a configuration, it causes a transition to a migrate state and all subsequent configurations will execute at the specified machine. The MigrateState actually migrates the entire FS itinerary to the destination machine. A network communication with a machine requires a daemon process to be running at the receiving host. For this, we define a communication link object, which defines a startService() method that creates a server socket monitored for incoming connection requests. (By the way, the communication link service startService() must have already been started on the machines that the agent will visit.) The actual socket code has been omitted for the sake of brevity. The method's implementation would receive an object using java.io.ObjectInputStream.readObject(), which is the FS itinerary class from some other machine. The code would then proceed to execute the FS itinerary from its current configuration (Java object serialization maintains the state of an object). The migrate() method of the migrate state would contain code to make a client connection to another machine that had executed the startService() method, and transmit the FS itinerary using java.io.ObjectOutputStream.writeObject().

Listing Four is the Finite State Itinerary component, the actual data structure that executes the itinerary. It requires, during construction, a reference to a configuration component (the root node of the finite-state-transition graph). The run() follows a simple logic:

1. Instruct the current configuration's conditions to be evaluated.

2. Retrieve the next configuration from the nextConfiguration() method of the current configuration and set the current configuration to be equal to this new configuration.

3. Execute the program associated with this new configuration. Return to step one.

At any point during execution of the itinerary, a finitestateitinerary.Halt (Listing Five) may be thrown, causing the itinerary to stop execution. Compare step one with the MobileCondition object that we defined. The evaluate() method will return False when invoked on the destination machine and True otherwise. When MobileCondition.evaluate() returns True, nextConfiguration() returns a configuration that contains a MigrateState, which will cause the itinerary to be transmitted to the correct machine. There, it will resume execution from its current configuration. This ensures that all states are executed at their correct destination machines. The current configuration is automatically maintained because we use Java Object Serialization in the CommunicationLink, which again starts the execution of the received itinerary.

We have omitted the listing for the Agent component since it is fairly straightforward to visualize an agent wrapper around the finitestateitinerary package. This finitestateitinerary.agent package, at the least, would contain an agent class that encapsulates the FS itinerary, mobility conditions, a custom configuration component, and a transition policy. Such a package would correspond with the notional concept of the agent paradigm, while providing a uniform and consistent interface into the underlying packages. The database application we present is straightforward and does not require this special agent class. However, building such a wrapper would be essential to a complete mobile-agent package.

The Database Application

To illustrate the FS itinerary, Listing Ten illustrates the building of the metaprogram transition graph that implements the flow chart in Figure 5. With the power of the FS itinerary, we are able to construct contingency plans at each step along the way. Tracing the flow chart, you can see that a database query is to be executed at a machine called ENIAC. However, if the itinerary is at some other machine, the mobility condition will cause a transition to a migrate state configuration, which moves the itinerary to ENIAC. The itinerary then performs the database query and tests the number of records retrieved. The query state has two conditions that are now evaluated. If the number of records is less than one hundred, the itinerary executes some alternative query. If the number of records is more than one hundred, the itinerary halts. This metaprogram is a direct mapping to the FS automaton in Figure 6. Although this metaprogram exhibits a simple task list with simple contingencies, arbitrarily large metaprograms could be built in this fashion to map directly to their own FS automaton.

Conclusion

An enhancement to our implementation would be to add the capability of the transition function to return more than one configuration from the nextConfiguration() method. This would require a change in the run() method of the FS itinerary to handle an enumeration of configurations. This change would represent the spawning of multiple FS itinerary evaluations for a given configuration, and would allow states to be executed in parallel -- a powerful addition to the implementation presented.

Here, we have used an iterative approach in executing the itinerary. However, another implementation of this concept might be programmed to be event driven. Using Java event notification, the next configuration can be computed automatically on the previous configuration raising an event.

We have presented an adaptable design for creating agent itineraries. FS Itinerary is based on a fundamental model of computation, which is applied here as a powerful representation of an agent's goal solving strategy.

DDJ

Listing One

// FILE State.java 
package finitestateitinerary;
/** 
 *  This class is an encapsulation of the program that must be run by 
 *  the FS Itinerary when it is in a particular configuration.
 *  The entry point is the run method.
 */
public abstract class State implements java.io.Serializable {
    /* INIT state is the initial state representation of the finite 
     * state machine. */
    public static final State INIT = new State() {
        public void run() {
        }
    };
    /* HALT state is the final state representation of the finite 
     * state machine */
    public static final State HALT = new State() {
        public void run() throws Halt {
            throw new Halt("HALT : Halted because of normal termination");
        }
    };

    /* Applications must implement this method for functionality */
    public abstract void run() throws Halt;
}

Back to Article

Listing Two

// FILE TransitionFunction.java
package finitestateitinerary;
/**
 *  The application must implement the TransitionFunction class to return
 *  the next configuration.
 */
public interface TransitionFunction {
    public Configuration nextConfiguration() throws Halt;
}

Back to Article

Listing Three

// FILE Configuration.java
package finitestateitinerary;
/**
 *  The configuration class holds the state to be executed and transitions
 *  from this configuration to new ones based on real-time conditions.  The
 *  next configuration is chosen by the implementation of the 
 *  TransitionFunction
 */
public abstract class Configuration extends State 
                                    implements TransitionFunction {

}

Back to Article

Listing Four

// FILE FiniteStateItinerary.java
package finitestateitinerary;
import java.io.*;
/**
 *  The run method of this class actually starts running the meta-program.
 *  It begins with the initial configuration, calls it's nextConfiguration 
 *  method.  The nextConfiguration method evaluates real time conditions and
 *  and returns the next configuration.  The initial state is a spurious state
 *  and is never executed by the itinerary.
 */ 
public class FiniteStateItinerary implements Serializable {
    private Configuration configuration = null;
    public FiniteStateItinerary(Configuration configuration) {
        this.configuration = configuration;
    }
    public void run() {
        try {
            /* Loop while the current  condition specifies that the itinerary 
             * should continue evaluation. */
            while (true) {
                /* Get the next configuration and hence the corresponding
                 * state to move into. */
                configuration = configuration.nextConfiguration();
                if (configuration == null) {
                    return;
                }
                /* Run the program associated with the state object. */
                configuration.run();
            }
        } catch (Halt halt) {
        }
        /* At this point, either final condition or an unsatisfyable 
         * condition has been encountered, or the machine was halted. */
    }
}

Back to Article

Listing Five

// FILE Halt.java 
package finitestateitinerary;
public class Halt extends Throwable {
}

Back to Article

Listing Six

// FILE MobileCondition.java
package finitestateagent;
import java.io.*;
import java.net.*;
import finitestateitinerary.*;
/**
 *  This implementation of the Condition object provides the mobile nature
 *  to agent applications.  It causes the Finite State Itinerary to be written
 *  to a computer.  It relies on the CommunicationLink class to accomplish this
 *  via object serialization.  If the evaluate() method returns true, the
 *  transition fucntion will choose the corresponding configuration as the
 *  next configuration.  If this configuration conatins a migrate state, the
 *  FS itinerary will migrate to the destination machine.
 */
public class MobileCondition extends Condition implements Serializable {
    private InetAddress destination = null;
    public MobileCondition(InetAddress destination) {
        this.destination = destination;
    }
    public boolean evaluate() {
        try {
            if (InetAddress.getLocalHost().equals(destination)) {
                return false;
            }
            else {
                return true;
            }
        } catch (UnknownHostException e) {
            throw new Halt();
            /* This computer is not suitable for IP communications */
        }
    }
}

Back to Article

Listing Seven

// FILE MigrateTask.java
package finitestateagent;
import java.net.*;
import finitestateitinerary.*;
/**
 *  This state causes the entire finite state itinerary to be sent to the
 *  destination machine via the CommunicationLink, where the finite state 
 *  itinerary will resume execution.  This state then halts the execution of
 *  the itinerary on the current machine by halting the current thread, since
 *  a copy of the FS itinerary is now running at the destination machine.
 */
public class MigrateState extends State {
    public MigrateState(InetAddress destination, FiniteStateItinerary 
                        itinerary)
        this.destination = destination;
        this.itinerary = itinerary;
    }
    /**
     *  The run method is implemented to migrate the agent
     *  that owns this state, to a new machine
     */
    public void run() throws Halt {
        /* Migrate this finite state itinerary to the destination machine */
        
        /* Stop the local execution of this instance of finitestateitinerary
         * since a copy is now running on a new machine */
        throw new Halt("HALT : Because itinerary transfered to destination" );
    }
}

Back to Article

Listing Eight

// FILE FSIConfiguration.java 
package finitestateagent;
import java.net.*;
import java.io.*;
import java.util.*;
import finitestateitinerary.*;
/**
 *  A configuration with a default deterministic transition function with 
 *  mobility support
 */
public class FSIConfiguration extends Configuration 
                              implements Serializable {
    private State state = null;
    protected Vector transitions = new Vector();
    public FSIConfiguration(State state) {
        this.state = state;
    }
    /**
     *  Add a condition and a target configuration branch on the finite 
     *  state machine
     */
    public void addTransition(Condition condition, 
                              Configuration configuration) {
        transitions.addElement(new Transition(condition, configuration));
    }
    /**
     *  Retreive the first met configuration to move into
     */
    public Configuration nextConfiguration() throws Halt {
        for (int i = 0; i < transitions.size(); i++) {
            if (((Transition)transitions.elementAt(i)).condition.evaluate()) {
                return ((Transition)transitions.elementAt(i)).configuration;
            }
        }
        throw new Halt("HALT : No satisfiable condition");
    }
    /**
     *  Execute the state
     */
    public void run() throws Halt {
        state.run();
    }
    /**
     *  Represents one transition mapping
     */
    private class Transition implements Serializable {
        private Condition condition = null;
        private Configuration configuration = null;
        public Transition(Condition condition, Configuration configuration) {
            this.condition = condition;
            this.configuration = configuration;
        }
    }
}

Back to Article

Listing Nine

// FILE Condition.java
package finitestateagent;
import java.io.*;
import com.lmco.atl.finitestateitinerary.*;
public abstract class Condition implements Serializable {
    /* This static class always causes a transition to the associated 
     * configuration */
    public static final Condition DEFAULT_CONDITION = new Condition() {
        public boolean evaluate() {
            return true;
        }
    };
    public abstract boolean evaluate() throws Halt;
}

Back to Article

Listing Ten

import finitestateitinerary.*;
import finitestateagent.*;
import java.net.InetAddress;

public class DemoAgent {
    public FiniteStateItinerary createMetaProgram(InetAddress eniac) {
        // Create the root configuration
        FSIConfiguration root = new FSIConfiguration(State.INIT);
        // Create the itinerary
        FiniteStateItinerary fsi = new FiniteStateItinerary(root);
        // Now create all other configurations
        // NOTE : jdbc.JDBCQueryTask would be implemented to simply 
        // perform the query passed on some database.
        jdbc.JDBCQueryTask jdbcTask1 = new jdbc.JDBCQueryTask(
           "SELECT Something FROM Somewhere");
        jdbc.JDBCQueryTask jdbcTask2 = new jdbc.JDBCQueryTask(
           "SELECT SomethingElse FROM SomewhereElse");
        FSIConfiguration dbConfig1 = new FSIConfiguration(jdbcTask1);
        FSIConfiguration dbConfig2 = new FSIConfiguration(jdbcTask2);
        FSIConfiguration migrateConfig = new FSIConfiguration(
            new MigrateState(eniac, fsi));
        FSIConfiguration haltConfig = new FSIConfiguration(State.HALT);
        // Link the above configurations using conditions
        // NOTE : In our implementation of 
        // TransitionFunction.nextConfiguration, we traverse a Vector to 
        // test conditions.  This means that the conditions will be 
        // tested in the order they are added.
        root.addTransition(new MobileCondition(eniac), migrateConfig);
        root.addTransition(Condition.DEFAULT_CONDITION, dbConfig1);
        migrateConfig.addTransition(Condition.DEFAULT_CONDITION, dbConfig1);
        // NOTE : DBCondition tests for the number of records 
        // retreived by a query.  In this example, if the number of records 
        // is less than 100, the condition returns true.  Otherwise, 
        // the 2nd transition will be taken.
        dbConfig1.addTransition(new DBCondition(jdbcTask1, 100), dbConfig2);
        dbConfig1.addTransition(Condition.DEFAULT_CONDITION, haltConfig);
        dbConfig2.addTransition(Condition.DEFAULT_CONDITION, haltConfig);
        // Return the transition graph
        return fsi;
    }
}

Back to Article