Every now and again, I think about Graphplan.

Graphplan is an algorithm for automated planning, which consists of solving planning problems. A planning problem specifies a starting state, a set of goal states, and a set of actions on states. This is similar to a classical search problem, but planning problems generally impose richer structure upon and allow greater complexity within states and actions.

For example, while finding the path from one node to another in a static graph is a search problem, finding a path from one node to another in a graph when the actor can change the graph is a planning problem. Planning algorithms excel in these sorts of complex environments, where taking some actions either enables or prevents taking others.

Planning problems are often described with planning languages. These are specialized domain-specific languages that define planning problems in terms of states, actions, and goals. Such a problem is then fed into an automated planning algorithm, which presents a solution in the form of a plan. A plan is a sequence of actions that transitions from the problem's start state to one of the problem's acceptable goal states. Graphplan is a fairly basic planning algorithm that performs reasonably well on such problems, but general automated planning is in PSPACE. There's only so much one can do with that.

Nevertheless, I've wanted a Graphplan implementation in Racket on and off throughout the years. Mainly I want this because planning languages are really unpleasant to use. They're often highly specialized software made by research terms with wonky installation requirements and general "research software" usability issues.

But, Racket works wonders on DSLs. So tonight I started sketching out my own planning DSL with the idea of eventually turning it into a racket #lang. I didn't bother implementing anything, but it's fun to just write out code and imagine it doing something. Here's how expressing simple graph traversal problems might look:

// Before defining specific prolems, we define the
// planning domain. This is typical in planning languages.
domain SimpleGraphTraversal {

  // This isn't OOP, this is a "class" more like in the
  // sense of set theory. This is a type of object which
  // the current state might be defined in terms of, and
  // different classes are guaranteed to have no overlap.
  class Vertex;

  // The current state is defined by a set of *facts*.
  // Predicates define what possible facts exist.
  predicate At(vertex: Vertex);
  predicate Edge(start: Vertex, end: Vertex);

  // The actions one can take are defined in terms of
  // preconditions and effects. Actions are quantified
  // over state variables, which are objects that are
  // used in predicates to refer to facts about the
  // current state.
  action Move(start: Vertex, end: Vertex) {

    // Each fact in an action's preconditions must be
    // true (that is, present in the current state) for
    // the action to be applied.
    preconditions {
      At(start);
      Edge(start, end);
    }

    // The effects of an action may introduce new facts
    // and/or retract existing facts. All other facts
    // present in the current state are assumed to be
    // left unchanged.
    effects {
      At(end);
      not At(start);
    }
  }
}

That defines a SimpleGraphTraversal planning domain. Planning domains can be used to solve many different instances of the same kinds of planning problems. This planning domain lets us answer basic graph search questions. To do that, we define a specific problem using the planning domain:

// We name the problem and specify what domain it uses.
// Each problem specifies what objects exist, what the
// starting state is, and what counts as a goal state.
problem Problem1(SimpleGraphTraversal) {

  objects Vertex(v1, v2, v3);

  // Our goal is to get to v3. This goal is satisfied
  // by any state that contains At(v3), regardless of
  // what other facts are in the state.
  goal { At(v3) }

  // We start at v1, and declare which vertices are
  // connected together.
  start {
    At(v1);
    Edge(v1, v2);
    Edge(v2, v3);
  }
}

Plugged into an automated planner, the above problem should spit out the plan Move(v1, v2); Move(v2, v3). That plan, applied to the starting state, produces the following series of states:

{ At(v1); Edge(v1, v2); Edge(v2, v3); }
{ At(v2); Edge(v1, v2); Edge(v2, v3); }
{ At(v3); Edge(v1, v2); Edge(v2, v3); }

So far there's nothing too surprising here. This is basic graph traversal. But let's notice something interesting: the edges are part of the current state. This gives us an inkling of what planning problems can do: what if an action is allowed to change the graph?

A fun and practical example of such a problem is one where some edges are locked, and require the actor to find and pick up a key to traverse that edge. One can imagine many real-world cases of this kind of thing: locked doors, ledges that can't be climbed without a ladder, finding a boat to cross a river, etc. We can model this by giving the actor a simple inventory system along with actions to pick up items and unlock edges using items:

domain GatedGraphTraversal {

  class Vertex;
  class Item;

  predicate At(vertex: Vertex);
  predicate Edge(start: Vertex, end: Vertex);

  predicate HasItem(item: Item);
  predicate ItemAt(item: Item, vertex: Vertex);

  predicate LockedEdge(
      start: Vertex,
      end: Vertex,
      key: Item);

  // Basic movement is the same as before
  action Move(start: Vertex, end: Vertex) { ... }

  // If the actor is at the same location as an item,
  // they can pick it up and add it to their inventory.
  action PickUpItem(vertex: Vertex, item: Item) {
    preconditions {
      At(vertex);
      ItemAt(item, vertex);
    }
    effects {
      not ItemAt(item, vertex);
      HasItem(item);
    }
  }

  // Locked edges can be unlocked using the corresponding
  // key item. Unlocking replaces the locked edge with a
  // normal edge.
  action UnlockEdge(
      start: Vertex,
      end: Vertex,
      key: Item) {
    preconditions {
      At(start);
      HasItem(key);
      LockedEdge(start, end, key);
    }
    effects {
      not LockedEdge(start, end, key);
      Edge(start, end);
    }
  }
}

Our new GatedGraphTraversal planning domain introduces two new actions: PickUpItem and UnlockEdge. The former picks an item up from the current vertex and adds it to the inventory, and the latter uses key items in the inventory to turn LockedEdge facts into regular Edge facts. Let's define a new planning problem using this domain:

problem Problem2(GatedGraphTraversal) {

  objects Vertex(v1, v2, v3);
  objects Item(redKey);

  goal { At(v3) }

  start {
    At(v2); // We start at v2 this time
    ItemAt(redKey, v1); // We'll have to go back for this
    Edge(v1, v2);
    Edge(v2, v1);
    LockedEdge(v2, v3, redKey);
  }
}

Plugging Problem2 into an automated planner should spit out the following plan:

Move(v2, v1);
PickUpItem(v1, redKey);
Move(v1, v2);
UnlockEdge(v2, v3, redKey);
Move(v2, v3);

And here's the succession of states we get by applying this plan:

// Start
{
  At(v2);
  ItemAt(redKey, v1);
  Edge(v1, v2);
  Edge(v2, v1);
  LockedEdge(v2, v3, redKey);
}

// Move(v2, v1)
{
  At(v1);
  ItemAt(redKey, v1);
  Edge(v1, v2);
  Edge(v2, v1);
  LockedEdge(v2, v3, redKey);
}

// PickUpItem(v1, redKey)
{
  At(v1);
  HasItem(redKey);
  Edge(v1, v2);
  Edge(v2, v1);
  LockedEdge(v2, v3, redKey);
}

// Move(v1, v2)
{
  At(v2);
  HasItem(redKey);
  Edge(v1, v2);
  Edge(v2, v1);
  LockedEdge(v2, v3, redKey);
}

// UnlockEdge(v2, v3, redKey)
{
  At(v2);
  HasItem(redKey);
  Edge(v1, v2);
  Edge(v2, v1);
  Edge(v2, v3);
}

// Move(v2, v3)
{
  At(v3);
  HasItem(redKey);
  Edge(v1, v2);
  Edge(v2, v1);
  Edge(v2, v3);
}

// GOAL REACHED

Pretty neat. Maybe someday I'll even get around to actually implementing this.