Framework Architecture

This section provides a brief description of the architecture of the provided framework.

Directories

The framework has a number of directories at the highest level. 'bin' holds the binaries, 'build' holds the compile information (as just a Makefile at the moment), 'obj' holds the object files created during compilation, 'docs' holds the information used to document the framework (in Doxygen) and the documentation itself when Doxygen is called, and 'src' which holds the bulk of the C++ source code.

'src' has a number of main directories as well. 'generic_defs' holds a number of generic definitions, often used as abstract classes for other parts of the framework. 'utils' has various utility files. 'algorithms' holds subdirectories for the different search algorithms. 'domains' holds subdirectories, one for each domain. 'experiments' holds the '.cpp' files that have 'main' functions and can be compiled into runnable binaries.

Constructing a Domain

The heart of the framework is in the ability to easily add new domains. Domains are defined by a description of the state and applicable actions (each as a separate class or type), and then a number of different components. First, a goal test function must be created, which inherits from the abstract GoalTestFunction. Domains must also have a transition system which denotes what actions are applicable in any state. This system must inherit from TransitionSystem.

A generic goal test function called SingleGoalTest is provided which can be used if there is a single goal state. In that case, the test simply checks if the given state is the stored state.

Example Domain

As an example domain, consider two dimensional map pathfinding. For this domain, the MapLocation class defines a state in the domain as an x and y coordinate in a map. The 'enum' MapDir provides a list of the possible actions applicable in any state, including the one-step movements in the cardinal directions North, East, South, and West, as well as the diagonal moves in relevant problems. The transition system for map pathfinding is defined by MapPathfindingTransitions, which loads in a map and can be used to determine which actions are applicable in any particular map location. This object can be set as 4-connected (only cardinal moves are allowed) or 8-connected (diagonal moves are also allowed).

Finally, we can create a SingleGoalTest with template argument MapLocation to build our goal test for this domain. We can then set the goal of this test, so that it returns true if and only if we have arrived at the desired map location.

Algorithms

All search algorithms must inherit from SearchEngine which defines the common properties of different search algorithms. Of note, to call for a search, the user will use the 'getPlan' function, but all search algorithms should overload 'searchForPlan'. 'getPlan' will call 'searchForPlan' after calling all necessary initialization methods and checks that the algorithm is properly configured.

Abstract classes have also been provided for items such as a Heuristic and StateHashFunction, which are common across many different algorithms.

Example Algorithm

As an example algorithm, consider A*. For this algorithm, we have defined BestFirstSearch which is the code shared between various versions of best-first search. This code uses a NodeTable to check what states have been visited, and an OpenClosedList to store the nodes in the open and closed list. BestFirstSearch requires a Heuristic to be set using the setHeuristic function, as well as a StateHashFunction to be set using setHashFunction.

BestFirstSearch is an abstract class, with a pure abstract function in nodeEval that defines the evaluation function. AStar is an instantiation of BestFirstSearch where this function is defined.

If we wanted to run A* for two dimentional map pathfinding, we would need the components described in Example Domain, along with a heuristic and hash function. For the heuristic, we can use MapManhattanDistance for 4-connected maps or MapOctileDistance for 8-connected maps. To use this function, a goal must be set, with (0,0) being used by default. The MapLocHashFunction then provides a hash function for the A* code to use. To use this function, the dimensions of the map must be set.

An A* instance can then be run on a given problem by calling 'getPlan' on a given initial MapLocation.

Additional Information

This section just lists some additional important information.

• string_utils.h has several functions that simplify inputting and outputting files.
• combinatorics.h has several functions for handling permutations, or combinatorial structures.
• floating_point_utils.h has functions for doing reasonable floating point arithmetic comparisons. In particular, when comparing two floating point values, fp_less, fp_greater, and fp_equal should be used instead of <, >, and ==. This is to avoid precision errors.