Route Finding Code

I uploaded the full source-code for the Route Finding Problem and the Touring Problem.

Source Code (box.net)

Read more...

Groovy/Java Problem Solving Agent

Today I'm going to look at implementing a simple problem-solving agent using Java and Groovy. This is based on chapter 3 in my old A.I. textbook, "Solving Problems By Searching." I am going to tackle the route-finding problem which takes a number of cities in Romania (p 68 on Google Books) with paths between them with the goal of having to find the shortest route between any two cities.

Let's get started. First, I created a few simple Java classes to represent a Node (a city), an Action (go from one node to another), a Path (list of Actions that have gotten me where I am now), and a State (what Node am I at and how did I get here). These classes are not that interesting, but here are the basics of each one without the implementations:

Node:

public class Node {
  public Node(String nodeName, List availableActions) {  }
  public String getNodeName() {  }
  public List getAvailableActions() {  }
}

Action:

public class Action {
  public Action(String actionName, int stepCost) { }
  public Node resultOfAction(List availableNodes) {
      //if I execute this action, where am I?
  }
  public int getStepCost() { }
}

Path:

public class Path {
  public void addAction(Action action) {  }
  public int getPathCost() {  }
  public List<action> getActions() {  }
  public Path clone() {  }
}

State:

public class State {
  public State(Node currentNode, Path currentPath, List closedNodes){ }
  public Node getCurrentNode() { }
  public Path getCurrentPath() { }
  public List getClosedNodes() { }
}

I also created a couple simple data structures to represent a Queue and a Stack (called SimpleQueue and SimpleStack). When searching for the solution, I needed to decide if I wanted to do a Depth-first search (using a Stack - LIFO) or a Breadth-first search (Queue - FIFO). I decided to use a depth-first search since I tried to be a little smart about only finding solutions that are shorter than any others I've already found. By doing a depth-first search, I tried to expand the search tree until I found a solution, then went back and tried to find other solutions that were shorter.

Now is where the actual searching happens. I created another Java class called RouteFindingProblem. I'll describe each part of that class starting with the "solve" method:

solve:

public Path solve(final Node initialNode, final Node goalNode) {
  if (initialNode.getNodeName().equalsIgnoreCase(goalNode.getNodeName())) {
      resultPath = new Path(new Action("Stay" + initialNode.getNodeName(), 0));
  } else {
      resultPath = null;
      lowestPathCost = Integer.MAX_VALUE;

      // find the paths
      doSearch(initialNode, goalNode);
  }
  return resultPath;
}

This is the entry point into the solving logic. It will return the shortest path from the initialNode to the goalNode. The first check is just to make sure the initialNode is not the same as the goalNode. If it is I am done and I'll just create a new "stay" action. Next (in the else statement) I initialize some variables and then call doSearch.

doSearch:

private void doSearch(final Node initialNode, final Node goalNode) {
  stateDataStructure = new SimpleStack<State>();

  // create the first state
  stateDataStructure
      .put(new State(initialNode, new Path(), new ArrayList<node>()));

  while (!stateDataStructure.isEmpty()) {
      if (goalTest(stateDataStructure.peek(), goalNode)) {
          handleGoalReached(stateDataStructure.get());
      } else {
          successorFunction(stateDataStructure.get(), goalNode);
      }
  }
}

I basically create the first state and add it to the stack. Then I keep going until the stack is empty. If I've reached the goal, then I just check if this is the shortest path (in handleGoalReached). If I haven't reached the goal, then I find all the successors of this state and add them to the Stack.

The last interesting piece of code in this class is the successorFunction method. I don't love this name, but that is what they call it my book. It would be more appropriately called "addSubStates" or something.

successorFunciton:

private void successorFunction(final State currentState, final Node goalNode) {
  // make a copy of the closed list for each sub state
  final List<Node> cloneClosedList = cloneClosedList(currentState
      .getClosedNodes());
  cloneClosedList.add(currentState.getCurrentNode());

  // for each action after this, add it to the queue
  for (Action nextAction : currentState.getCurrentNode()
      .getAvailableActions()) {
      final Node nextNode = nextAction.resultOfAction(nodes);
      // make sure I haven't already checked this node (circular)
      if (!cloneClosedList.contains(nextNode)) {
          final Path clonePath = currentState.getCurrentPath().clone();
          clonePath.addAction(nextAction);

          // only add the next state if the current path is
          // lower than any previous paths
          if (clonePath.getPathCost() < lowestPathCost) {
              stateDataStructure.put(new State(nextNode, clonePath,
                  cloneClosedList));
          }
      }
  }
}

In a nutshell, this just finds the next set of states and adds them to the stack.

All that is left is to set up the actual data and run some tests. To do this I used Groovy, partly because I thought it would be easier to script some of the setup and tests, and partly because I don't know much about Groovy so this was a chance for me to learn more about it.

First off, I created some helper methods (closures) to use in my Groovy script.

createActionList = {actionMap ->
  List<Action> actions = new ArrayList<Action>();
  actionMap.each {place,cost -> actions.add(new Action("Go(" + place + ")", cost)) };
  return actions;
}

createNode = {nodeName, actionMap ->
  return new Node("In(" + nodeName + ")", createActionList(actionMap));
}

findNode = {nodeList, nodeToFind ->
  for(nextNode in nodeList){
      if(nextNode != null && nextNode.getNodeName().equalsIgnoreCase("In(" + nodeToFind + ")")){
          return nextNode;
      }
  }
}

Then I set up all the nodes in this problem (cities in Romania):

nodes = [
  createNode("Arad", ["Zerind":75, "Sibiu":140, "Timisoara":118]),
  createNode("Bucharest", ["Pitesti":101, "Fagaras":211, "Giurgiu":90, "Urziemi":85]),
  createNode("Craiova", ["Drobeta":120, "Rimnieu Vilcea":146, "Pitesti":138]),
  createNode("Drobeta", ["Mehadia":75, "Craiova":120]),
  createNode("Eforie", ["Hirsova":86]),
  createNode("Fagaras", ["Sibiu":99, "Bucharest":211]),
  createNode("Giurgiu", ["Bucharest":90]),
  createNode("Hirsova", ["Urziemi":98, "Eforie":86]),
  createNode("Iasi", ["Vaslui":92, "Neamt":87]),
  createNode("Lugoj", ["Timisoara":111, "Mehadia":70]),
  createNode("Mehadia", ["Lugoj":70, "Drobeta":75]),
  createNode("Neamt", ["Iasi":87]),
  createNode("Oradea", ["Zerind":71, "Sibiu":151]),
  createNode("Pitesti", ["Rimnieu Vilcea":97, "Craiova":138, "Bucharest":101]),
  createNode("Rimnieu Vilcea", ["Sibiu":80, "Craiova":146, "Pitesti":97]),
  createNode("Sibiu", ["Oradea":151, "Arad": 140, "Fagaras":999, "Rimnieu Vilcea":80]),
  createNode("Timisoara", ["Arad":118, "Lugoj":70]),
  createNode("Urziemi", ["Bucharest":85, "Vaslui":142, "Hirsova":98]),
  createNode("Vaslui", ["Urziemi":142, "Iasi":92]),
  createNode("Zerind", ["Oradea":71, "Arad":75])
];

Update:See this post about defining Segments instead of Nodes.

Then I set up some Groovy unit tests to make sure this was working as expected:

RouteFindingProblem problem = new RouteFindingProblem(nodes);

//same initial/goal
assert 0 == (problem.solve(findNode(nodes, "Arad"), findNode(nodes, "Arad"))).getPathCost();
//neighbors
assert 75 == (problem.solve(findNode(nodes, "Arad"), findNode(nodes, "Zerind"))).getPathCost();
assert 75 == (problem.solve(findNode(nodes, "Zerind"), findNode(nodes, "Arad"))).getPathCost();
//2 hops
assert 215 == (problem.solve(findNode(nodes, "Zerind"), findNode(nodes, "Sibiu"))).getPathCost();
//one end to the other
assert 698 == (problem.solve(findNode(nodes, "Oradea"), findNode(nodes, "Eforie"))).getPathCost();

Finally I did a test to print out the path from one end of Romania to the other:

Path resultPath = problem.solve(findNode(nodes, "Oradea"), findNode(nodes, "Eforie"));
//display the results
println("Shortest path from " + findNode(nodes, "Oradea").toString() + " to " + findNode(nodes, "Eforie").toString());
for (Action nextAction : resultPath.getActions()) {
  println(nextAction.toString());
}

The output is:

Shortest path from In(Oradea) to In(Eforie)
Go(Sibiu)(151)
Go(Rimnieu Vilcea)(80)
Go(Pitesti)(97)
Go(Bucharest)(101)
Go(Urziemi)(85)
Go(Hirsova)(98)
Go(Eforie)(86)

Next Steps:
This is just one simple problem-solving agent. I tried to make this fairly generic, but to implement the other examples from the book (sliding block puzzle, 8-queens problem, touring problem), it will take a little work.


Update 7/27/10: Uploaded the source code.

Read more...