Stripslet: a Robocup-playing STRIPS Planner based on Krislet

QuickStart

Source: http://www.employees.org/~alokem/robocup-sw/stripslet.
Other utils: http://www.employees.org/~alokem/robocup-sw

The Stripslet application was written using the JDK 1.3. Copy the files into one directory, type

% javac *.java

Boot up the soccerserver and the soccermonitor and then in the same directory type:

% java Stripslet [-host hostname -port portname -team teamname]

(same arguments as Krislet, but default teamname is now "stripslet")

You'll notice the behaviour to be a slowed down version of Krislet. This is because essentially the same series of actions are being deduced, but using the STRIPS planner.

Customizing Stripslet

The real fun of customizing Stripslet is in these areas:

Actors

These are objects that encapsulate an execute() method. Each Actor is designed to perform a specific action such as "run-to-ball" or "score-goal". When designing a new Actor its okay to assume some prerequisites...see the later section on Actions. How to add a new Actor:

1. Add a new class into Actor.java. It must implement the Actor interface: a function to return a name and an execute() function designed to carry out some action. I'll refer to classes which implement the Actor interface as Actors from now on. The name attribute is important since it is used as a key to look up your Actor object in a hashtable. No spaces are allowed in the name!
2. Instantiate your Actor and add it into the ActorTable hash. This is done by adding a line to the function initializeActorTable in StripsBrain.java.

class actorFindBall implements Actor
{ 
  public static final String name = "find-ball"; // name is IMPORTANT!
                                                 // used as hash key
  public String getName(){
    return name;
  }
  public boolean execute(Memory m, SendCommand actuator, char side){
    ... code to perform the action, check memory, etc ...
  }
}; // actorFindBall

Sensors

These are objects that encapsulate a sense() method. Each Sensor is designed to calculate the truth of a specific predicate such as "can-see-goal" given the current environment. How to add a new Sensor:

1. Add your Sensor into Sensor.java. It must implement the Sensor interface: a function to get the name and a sense() function designed to return the truth-value of some statement. I'll refer to classes which implement the Sensor interface as Sensors. The name attribute is important since it is used as a key to look up your Sensor object. No spaces are allowed in the name!
2. Instantiate your Sensor and add it into the SensorTable hash. This is done by adding a line to the function initializeSensorTable in StripsBrain.java.

class sensorCanSeeBall implements Sensor
{
  public static final String name = "can-see-ball"; // did i mention this was
                                                 // important!
  public String getName(){
    return name;
  }
  public boolean sense(Memory m, char side)
  {
    ObjectInfo object = m.getObject("ball");
    return !(object == null);
  }
}; // sensorCanSeeBall

Actions

• name - for example "score-goal"
  These correspond directly to the name property of Actors. If a specific Action is required to achieve the goal then this member will be used to get a handle of an Actor whose execute() method we can call.
• preconditionList - for example "have-ball can-see-goal"
  This is a list of predicates that must be true before this Action may be executed. The names correspond directly to the name attributes of Sensor objects. If evaluation of these predicates is required, these strings will be used to get the handle of a Sensor whose sense() method we can call.
• addList - for example "ball-in-net"
  This is a list of predicates that will become true if this Action is executed. Again the names should correspond to the names of Sensor objects. When this action is executed, the predicates in the addList will become true. The addList is crucial in choosing an action: we are only interested in actions that advance us towards our goal - the addList is the list of positive side-effects that will occur after executing this action.
• deleteList - for example "have-ball"
  This is a list of predicates that will become false if this Action is executed. The names should correspond to the names of Sensor objects. When this action is executed, the predicates in the deleteList will be made false in the worldView (regardless of the Sensor values).

1. Actions are instantiated and added to a master list of actions (the cleverly named actionList) in the function initializeActionList in StripsBrain.java.

    actionList.add(new Action("score-goal",             // name
                              "have-ball can-see-goal", // pre
                              "ball-in-net",            // add
                              "have-ball"));            // delete

By creating custom Sensors, Actors and Actions you can create a richer set of possible paths of action for the agent.

GoalList

The list of goals is another source of customization. This is defined in the main run() loop of the StripsBrain as being the single predicate "ball-in-net". The Sensor for this predicate always returns false causing the agent to continuously plan to achieve this goal. Some interesting customizations are possible here:

• Multiple goals in the goal list
• Generate a new goallist for each planning cycle based on environment or some random factor

How Stripslet integrates with Krislet

It is useful to describe how Krislet works to see how Stripslet alters it:

 Krislet::main
   parse command-line and init inet connection
   init, parseInitCommand - handshake w/server
     start thinking thread
     start sensing thread

  SENSING THREAD [
    Krislet::parseSensorInformation (look and listen)
      if it is a see message
        what objects can I see? -  see VisualInfo::parse
        tell brain - see Brain::see()
      if it is a hear message
        tell brain - Brain::hear() - note: brain is deaf out of the box

    VisualInfo::parse (catalogue visible objects)
      for all objects:
        type, direction, distance, distance_change, direction_change
      object types: player, goal, ball, flag, line
        specific properties defined in ObjectInfo?.java

    Brain::see (remember)
      store list of objects in Memory member
  ] end SENSING THREAD

  THINKING THREAD [
    Brain::run
      look for the ball - see Memory::getObject {
        cannot see ball:
          turn, wait for new memories - see Memory::waitForNewInfo
        ball is far away:
          turn to face it and then dash towards it
        ball is nearby: {
          look for the goal {
            cannot see goal:
               turn, wait for new memories
            can see goal:
               kick towards goal
          } end look for goal
      } end look for ball
      sleepy time

    Memory::getObject
      if no memory, wait for new memories
      otherwise look through memory (array) for specified object

    Memory::waitForNewInfo
      forget everything
      sleep until sensing thread creates new memories
  ] end THINKING THREAD      

The sensing thread remains untouched in Stripslet. The change is in the thinking thread. The StripsBrain class defines an alternate brain which replaces the hard-coded reflexive behaviour of Krislet with a planning approach based on the STRIPS algorithm. The StripsBrain still makes use of the Memory functionality embodied in the getObject and waitForNewInfo methods. But Stripslet has adaptors (Sensors) to change raw information from Memory into a form comprehensible by the planner. Adaptors are also used to convert the abstract list of strings produced by the planner into actual action (Actors).

STRIPS algorithm

The heart of the agent is the function doStripsPlanning which is in the StripsBrain class. The key to the STRIPS algorithm is the Action structure which contains the four elements: action, preconditionList, addList and deleteList. The STRIPS algorithm also requires the list of goals and the current state of the world (I call it worldview) as inputs.

The planner first checks whether the goals are already satisfied by looking at the worldview. If some goals are not satisfied, a backwards chaining procedure is applied. Each Action's addlist enumerates the goals that it will achieve. By looking through the Action's addlists, the planner finds Actions that will result in the goal being achieved.

Since each Action has a set of preconditions (preconditionList), it may not be possible to execute that action. This is where the recursive element of the algorithm kicks in. The preconditions for the desired Action become the goallist for another iteration of the planner, and the planner attempts to find Actions which will satisfy this new list of goals. By recursing backwards through the chain of events, the agent may eventually arrive at a sequence of Actions which will satisfy all the intermediate goals and the original goal.

This algorithm was simplified for Stripslet. STRIPS planning Actions support predicates which take arguments. These arguments can then be unified with facts in the world in order to form bindings for the arguments. In order to avoid the task of writing routines to perform unification I chose predicates that have no arguments - the subject of the action is encoded in the predicate name: e.g. can-see-ball.

Each predicate and action is encoded as a string which allows easy manipulation. Checking whether a given Action satisfies a given goal is simply of matter of iterating over the Action's add list and doing string comparisons with the goal string. This also makes it easier to print useful debugging messages, and Stripslet dumps out a reasonably verbose explanation of its (repetitive) planning processes.

Connecting to the "real" world

As mentioned earlier the Stripslet planner mostly manipulates Strings for ease of use and debugging, but how are these related to the real world?

The Krislet brain (and the Stripslet brain) has two interfaces to the outside world: the SensorInput interface which is used to turn soccerserver messages into objects contained in the Brain's memory member and the SendCommand interface which is used to send soccerserver understandible commands to implement some basic actions: move, turn, dash, kick, etc.

The planner has a more abstract view of the world. Facts about the world are represented as Strings. The final plan that it comes up with is also represented as a Vector of Strings. The translation mechanism for facts about the world is implemented using the WorldView object. The WorldView object acts as a cache for information about predicates. When the planner wishes to check if a given predicate is true in the world, it calls the WorldView.evaluate method.

The WorldView consists of two major components. A hashtable called factStates which stores whether any given fact is true or false. The trick is that factStates is initially empty. As queries come in, WorldView will begin to populate factStates, but how does it find out whether a fact is true or not?

WorldView also contains a hashtable called SensorTable which maps predicate strings to objects which implement the Sensor interface (i.e. they have a sense() method which returns a boolean). When WorldView receives a request to evaluate a predicate it has not previously seen it looks up the corresponding Sensor (which is designed to give a true or false answer for a specific predicate such as "can-see-ball") and then calls its sense() method. The result is then cached in factStates for future queries.

The Sensor methods themselves don't interact directly with the environment by parsing soccerserver messages: they actually interact with the Krislet's original memory object. This object is filled in periodically by the sensing thread mentioned earlier (implemented in the Brain's see method which in turn implements the SensorInput interface), and is an abstracted representation of the environment. For example to check whether the agent can see a ball is simply a matter of checking the return value from Memory.getObject("ball"). A return value of null indicates that it doesn't exist in our Memory, and hence can't actually be seen by the agent.

The mapping between action strings and the actual SendCommand is similar. The ActorTable is a hashtable where objects implementing the Actor interface to achieve a well-defined goal (i.e. kick the ball into the net) are keyed by the String which describes them (i.e. "score-goal"). This allows the plan, really a Vector of Strings, to be mapped into an Actor. The Actor in turn implements the calls to the SendCommand interface which finally, when they reach the soccerserver, cause the player to interact with its environment.

Stripslet files

• Action.java: object which describes a STRIPS action using strings that can be mapped into Sensors and Actors using the SensorTable and ActorTable.
• Actor.java: object/function which can cause the player to interact with its environment to achieve a well-defined goal.
• Sensor.java: object/function which can prove or disprove a well-defined fact (a.k.a. predicate) by querying the Brain's memory object.
• StripsBrain.java: contains the ActionList, ActorTable and SensorTable objects. ActionList defines the list of available Action objects. The ActorTable is a hash mapping strings describing actions to an Actor capable of performing the action. The SensorTable is a hash mapping strings describing facts to a Sensor capable of assessing the facts truth-value. Also contains the main loop and doStripsPlanning which implements the STRIPS algorithm. This file is adapted from Brain.java in the original Krislet.
• WorldView.java: hashtable containing fact names as a key to the fact's truth value. If the value is not found, this class is also able to convert the fact into a Sensor which can return its truth value.

• Stripslet.java (Krislet.java with slight changes)
• Memory.java
• ObjectInfo.java
• SoccerInterfaces.java
• SoccerParams.java
• VisualInfo.java

Relevant links