Personal Wiki of Subhrajit Bhattacharya

Download YAGSBPL library: External link not working? [X]
Please follow this link to an alternate source.
yagsbpl-2.1.zip (Licensed under GNU-GPL)
Or, download it from Google Code: http://code.google.com/p/yagsbpl/
Requirements: C++ compiler with STL
Installation: Read Installation and Compiling in the documentation below.

Download basic example programs: External link not working? [X]
Please follow this link to an alternate source.
yagsbpl-2.x_basic-examples.zip
Requirements: C++ compiler with STL and YAGSBPL library
This collection of programs demonstrate the 3 different ways of describing a graph (as detailed in the tutorial below):
i. The easiest way using global function pointers, ii. by inheriting and redefining virtual functions, iii. by using function container.

Download example programs with visualization: External link not working? [X]
Please follow this link to an alternate source.
yagsbpl-2.x_opengl-examples.zip
Requirements: C++ compiler, OpenCV library (including 'cvaux' and 'highgui') and YAGSBPL library
These example program illustrates the event handlers introduced in v2.0, and planning with topological constraints as discussed in http://goo.gl/kbL5V.

Suggested citation format: Subhrajit Bhattacharya (2013) "YAGSBPL: A template-based C++ library for large-scale graph search and planning". Available at http://subhrajit.net/index.php?WPage=yagsbpl

Bibtex entry:

 @misc{yagsbpl,
     title = {YAGSBPL: A template-based C++ library for large-scale graph search and planning},
     author = {Subhrajit Bhattacharya},
     note = {Available at http://subhrajit.net/index.php?WPage=yagsbpl },
     url = { http://subhrajit.net/index.php?WPage=yagsbpl },
     year = {2013}
 }

The primary considerations behind developing the library were:

• Dynamic graph construction: One shouldn't need to construct and store a complete graph before starting the search/planning process. The graph is constructed and states are expanded on the fly and as required. This makes it highly suitable for use with RRT-like graph construction. (This is an already-existing feature in SBPL)
• Should be easy to use: Specifically, defining a graph, even the complex ones, should be very easy to do. This was one of the most important motivating factor behind writing this library. YAGSBPL is a template-based library. Hence defining new arbitrary node-types, cost types, etc. is made easy. For graph connectivity, node accessibility tests, etc, pointers to user-defined functions can be used, which makes defining the graph structure very easy, yet highly flexible.
• Should be fast & efficient: Any graph search without the global knowledge of the graph from before typically needs a hash table for maintaining and creating the graph nodes, as well as needs an efficient heap for ordering the nodes in the open list. These are the components that tend to slow down the search processes. YAGSBPL uses an efficient hash table as well as an efficient "keyed heap" implementation that is fast and scales well with problem size. For example in the sample programs, with integer coordinates for nodes but floating point cost as well as cost function needing to compute floating point operations online, and an average degree of the graph being 8, YAGSBPL can expand more than 50,000 nodes in the graph in about 0.8 seconds.
• Multiple start and goals: In the graph search we should be able to have multiple start coordinates (seeds), store trajectories intermediately, and have multiple possible goals (or complex ways of defining possible goal nodes). This was one of the requirements in my applications because of which I started to write this library in the first place.

YAGSBPL supports:

• Directed graphs with complex cost functions.
• Dynamic graph construction.
• Arbitrary graph node type declaration.
• Arbitrary edge cost type declaration.
• Intermediate storage of paths during graph search.
• Multiple goals (or goal manifold) that determine when to stop search.
• Multiple seed nodes.
• Event handling.
• Ability to write new planners with much ease. Comes with a weighted A* (that includes Dijkstra's and normal A*) planner by default.

So without any further delay, we dive right into some tutorials on YAGSBPL.

The members of the class are described below. (skip to example instead)

Snippet from YAGSBPL library:

Typically, for creating a graph, in your code you'll create an instance of this class and set the function pointers to functions defined by you, and set the values of "hashTableSize", "SeedNode" and "TargetNode". The members are quite self-explanatory by their name. A brief explanation of each:

• hashTableSize - This MUST be provided.
  As discussed earlier, YAGSBPL maintains a hash table for keeping track of the nodes explored efficiently. This declares the size of the hash table. In other words, the value that (*getHashBin_fp) returns should lie between 0 and hashTableSize-1 (both inclusive). Otherwise a segmentation fault will be thrown.
• getHashBin_fp - This MUST be provided.
  Pointer to a function that maps nodes to hast bins in the hash table (i.e the hash function). Ideally this needs to be defined such that the nodes are distributed randomly and with uniform probability among all the bins. Please refer to http://en.wikipedia.org/wiki/Hash_function or any data-structure/programming book for more details.
  IMPORTANT: getHashBin_fp should return an integer value between (including) 0 and hashTableSize-1.
• isAccessible_fp - optional. All nodes will be considered accessible if not set.
  Takes in a node and tells whether or not is accessible. TIP: If you are already testing accessibility inside getSuccessors_fp, do not set this for avoiding repated testing.
• getSuccessors_fp - NOT optional for most planners.
  Takes a node 'n', and returns a vector of successor nodes 's', along with the respective transition costs 'c'. 's' and 'c' should be of equal length. This function defines the connectivity of the directed graph and edge costs.
• getPredecessors_fp - Not required if not required by planner. Weighted A* planner does not require it.
  Provision is kept. But not used by weighted A* planner. So you need not worry about this if you are using the default planner.
• getHeuristics_fp - optional. Zero heuristics is used if not set.
  The heuristics function for A*. The heuristics will be set to 0 (i.e. Dijkstra's) if this function is not set. The function must return a value less than or equal to the actual cost between nodes 'n1' and 'n2'.
• storePath_fp - optional.
  Determined based on the node 'n', whether to store the path up to that node. Graph search will continue as usual. Only the path to 'n' will be stored intermediately.
• stopSearch_fp - optional if "TargetNode" is provided.
  Determines whether or not to stop the search process when the node 'n' has been expanded. This function also stores the path up-to 'n'. Note that the function can be used to define multiple possible stop nodes, whichever is reached earlier (e.g. the body may contain the statement "return (n==n1 || n==n2);".)
• SeedNode and SeedNodes - Either SeedNode should be set, or at least one element should be there in the vector SeedNodes. isAccessible_fp should return true for the seed nodes.
  The nodes to put in the "open" list at the start of the graph search.
• TargetNode - optional if getHeuristics_fp is not set and stopSearch_fp is set.
  Goal/target node used for computing Heuristics. Not required if "getHeuristics_fp" is not set. This does NOT, in general, determine when to stop search. However, if "stopSearch_fp" is not set, TargetNode is used to determine when to stop the search.

TROUBLESHOOT: If stopSearch_fp is not provided, make sure that the TargetNode is accessible and can be reached from a seed node. Planner will typically not check that at the beginning of planning.

For planning using the provided A* planner, the template class and it's relevant members are as follows:

Snippet from YAGSBPL library:

where the class A_star_variables has members CostType g, bool expanded, bool accessible and int seedLineage. Thus function getNodeInfo can be used to probe these information about an arbitrary node. int seedLineage gives the index of the seed from which the node was reached.

In v2.0 couple of event handlers were introduced. The event handlers are basically pointers to user-defined functions that the class A_star_planner maintains and calls every time the corresponding event is triggered during the planning process. The two types of events that can be handled:

• Node expansion: Triggered when a node 'n' gets expanded (placed in the closed list). Any of the following two members of A_star_planner can be set to handle this:

Snippet from YAGSBPL library:

• Successor updated: Triggered when a successor 'nn' of a node 'n' is updated (generated, placed on the open list, or g-value is updated). Any of the following two members of A_star_planner can be set to handle this:

Snippet from YAGSBPL library:

For more details on use of events refer to the example programs.

If you do not intend to use event handlers, you may choose to set the value of _YAGSBPL_A_STAR__HANDLE_EVENTS to 0 in A_star.h. This may give some marginal speed-up.

Say, you want to use pointers to member functions of a class for 'isAccessible_fp', 'getSuccessors_fp', etc. The following will fail since "bool (*)(NodeType& n)" and "bool (envDescriptionClass::*)(NodeType& n)" are of incompatable types:

In order to be able to use class member functions, one of the following two approaches can be taken:

Creating a class that inherits and redefines virtual functions from "SearchGraphDescriptorFunctionContainer":

The preferred method is to derive the "envDescriptionClass" from YAGSBPL's "SearchGraphDescriptorFunctionContainer" and override the virtual functions declared in there. In YAGSBPL the following template class is declared:

Snippet from YAGSBPL library:

The following example illustrates how this can be used:

Using function container for direct pointers to member functions:

Alternatively, YAGSBPL also declares the following template class:

Snippet from YAGSBPL library:

This, along with the class "SearchGraphDescriptorFunctionContainer" (described later), can be used as follows for using class member functions.

Keyed Heap

The keyed heap data-structure used by YAGSBPL is a little different from the conventional heap. Typically heaps are stored in arrays (the container) with each array element containing pointers to its children and parent in the heap. Random access to array elements is required for the insert operation since the potential parents can be located only by computed index. So replacing the array with a linked list is not possible. Thus, while the insert operation for the heap itself is of complexity O(log n), resizing the array and inserting element in the array is of complexity O(n). This makes the overall heap operations ~ O(log n) + O(n).

The keyed heap used by YAGSBPL is basically a linked list which is also a priority queue. So the pop operations for the heap is O(1) complexity. Besides the priority linked list itself, which does not allow random access to elements, a list of pointers to k key elements in the linked list is maintained, that point to elements in the linked list at approximate equal intervals of n/(k+1). Typically k is a modest number from 5 to 50. These keys are used for semi-random access, i.e. to find a good approximate location in the linked list from where to start the search for exact location to insert a new element. The keys are also updated every time a new element is inserted in the queue. This makes the insert operation ~ O(log k) + O(n/k).
The following approximate complexities apply operations on keyed heap used by YAGSBPL:

• pop (obtain smallest element and remove it from heap): ~ O(1)
• insert: ~ O(log k) + O(n/k)
• remove (remove from somewhere middle, given the pointer): ~ O(1)

In brief, keyed heap is just a priority linked list (i.e. linked list with all elements in order), along with a separately maintained and updated list of pointers to elements inside the linked list in order to help in efficiently finding the position in the linked list to insert new elements. The default value of k in YAGSBPL_base is 20, that works well for small to medium sized problems (heap size going up to ~10,000). For large problems one may want to increase the value. The value can be set using the planner's setParams function.