Graph Search and Artificial Inteligence, direction/angle based search

I recently started reading a great book: Artificial Intelligence: A Modern Approach by Stuart Russell and Peter Norvig. I’m on Chapter 3, Solving Problems by Searching. There very cool part of the book is that it’s accompanied by source code (available from the linked page, publicly available; I’m using the python version).

The model problem for graph search is a road map of Romania (using Google image search I found this picture which shows the map as found in the book), in which cities are chosen in such way that their first letters are unique, and serve as array indexes, very convenient. Inside search.py there is a nicely written class representing a graph which in turn represents the said road map. This is further extended into GraphProblem class, which additionally holds start and end nodes, and allows to test whether the current state, which is modified by search algorithms is the goal state, for example. All is very convenient after you get the general feel of it, and includes a number of search algorithms, and a compare_graph_searchers function that evaluates them according to the number of different operations performed (lower is better).

All the time that I’ve been reading about different approaches (traverse all the nodes breadth or depth first, evaluate their path’s costs (distance in this case) and so on) I wanted to see how angle-based search fare. By angle-based I mean measuring the bearing from the initial node to the goal node, and expand the node that lies closest to the bearing line (by evaluating angular differences). I wrote the algorithm for this kind of search, and tested it together with the others. The results surprised me very positively, my code scored the best*! (if you are curious about the metrics, have a look at InstrumentedProblem class in search.py)

Searcher                      Romania(A, B)        Romania(O, N)           Australia          
breadth_first_tree_search   <  21/  22/  59/B>  <1158/1159/3288/N>    <   7/   8/  22/WA>
breadth_first_search        <   7/  11/  18/B>  <  19/  20/  45/N>    <   2/   6/   8/WA>
depth_first_graph_search    <   8/   9/  20/B>  <  16/  17/  38/N>    <   4/   5/  11/WA>
iterative_deepening_search  <  11/  33/  31/B>  < 656/1815/1812/N>    <   3/  11/  11/WA>
depth_limited_search        <  54/  65/ 185/B>  < 387/1012/1125/N>    <  50/  54/ 200/WA>
recursive_best_first_search <   5/   6/  15/B>  <5887/5888/16532/N>   <  11/  12/  43/WA>
my_search                   <   4/   5/  13/B>  <  13/  13/  34/None> <   2/   3/   6/WA>

* There is however one interesting thing you should be aware of. In Romania (O, N) case (road from Oradea to Neamt) the algorithm actually does not return a solution (None in the fourth field). This is due to a very interesting case.

In going from Arad to Bucharest, the problem is relatively straightforward. I will list the debug output my algorithm follows A->S->R->P->B which is the most angle-aligned and the shortest path.

In going from Oradea to Neamt, it follows O->S->F->B and here is inclined to go back to Fagaras, since this seems to have the angle closest to it’s goal (Bucharest->Urziceni is much further from the imaginary Bucharest->Neamt, in degrees). Then it wants to go back to Bucharest, and back and forth till the end of time. I have added a set of explored nodes, and coded the algo so that it does not go over the ones it’s already been to. Much to my surprise (but perfectly according to the laws of geometry, and I’m sensing the AIMA’s authors careful choice of problem here), the algorithm prefers Bucharest->Pitesti to Bucharest->Urziceni that would likely lead it to the solution. More over, after going to Pitesti, the algorithm is trapped because it’s “bagged” inside the nodes it already expanded. This way it goes all the way up to Oradea and returns no solution. I have a number of ideas for improvement, but for now I’m moving on to reading what’s next in the book, because it’s so masive (over 1100 pages in paper form, though I recommend Kindle version [I read it on my Android phone]).

If anybody’s interested I’m sharing the code I used for calculating angle (bearing) between two poitns a and b:

  def angle(a, b):
    len_x = float(b[0] - a[0])
    len_y = float(b[1] - a[1])
    angle = atan2(len_x, len_y)*180.0/pi
    if (angle < 0):
      angle += 360
    return angle

and for calculating the relative difference between two bearings:

  def rel_ang_diff(a, b):
    if (b > a):
      a, b = b, a
    diff = a - b
    if (diff > 180):
      diff = (b + 360 - a)
    return diff

and this is the algorithm itself, with the debugging info stripped for readability:

  curr = Node(problem.initial)
  explored = set()

  def rec_angle_search(problem, curr):
    explored.add(curr.state)
    if problem.goal_test(curr.state):
      return curr
    frontier = curr.expand(problem)

    min = sys.maxint
    desired = angle(loc[curr.state], loc[problem.goal])
    for cand in frontier:
      actual = angle(loc[curr.state], loc[cand.state])
      diff = rel_ang_diff(desired, actual)
      if diff < min:
        if (cand.state not in explored):
          min = diff
          next_node = cand
        else:
          continue
    if min == sys.maxint:
      return None