Migration Notice (June, 2015):

The new home for YAGSBPL on github is https://github.com/subh83/YAGSBPL .
This page on google code will be discontinued.

Description:

"Yet Another Graph-Search Based Planning Library (YAGSBPL)" is a fast, efficient and easy-to-use graph construction and search (using algorithms like A-star, Dijkstra's, etc.) library written in C++, designed specifically for searching medium to large scale graphs for optimal paths.

Quick start: * Download the latest library (v2.1): yagsbpl-v2.1.zip. * Download the basic example programs and follow instructions in README file: yagsbpl-2.x_basic-examples.zip. * Read the detailed documentation at http://goo.gl/q7WGE

YAGSBPL is designed to be: * Fast (e.g., with integer coordinates for nodes but floating point cost as well as cost function needing to perform floating point operations online, and an average degree of the graph being 8, the library can expand about 70,000 nodes in the graph in just 1 second on a 2.1GHz processor machine with 2GB RAM.) * Easy to use (being template-based, 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.)

Basic code structure for the simplest usage: http://www.subhrajit.net/files/Projects-IT/Cpp-Libraries/yagsbpl/yagsbpl1.png'>http://www.subhrajit.net/files/Projects-IT/Cpp-Libraries/yagsbpl/yagsbpl1.png' width='80%' /> http://www.subhrajit.net/files/Projects-IT/Cpp-Libraries/yagsbpl/yagsbpl2.png'>http://www.subhrajit.net/files/Projects-IT/Cpp-Libraries/yagsbpl/yagsbpl2.png' width='85%' /> 1. A class describing the node/vertex type andfunctions describing graph structure are defined2. Initialization of graph, execution of search,and reading the result done in the main function

For a detailed documentation and tutorial visit: http://goo.gl/q7WGE

YAGSBPL supports:

• Directed graphs with complex cost functions.

• On the fly graph construction (i.e. no need to construct and store a complete graph before starting the search/planning process - makes it highly suitable for RRT-like 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 (start nodes) for wave-front expansion type graph exploration, and ability to trace seed lineage for any node.

• Event handling (i.e., call to user-defined functions upon generation, g-score updating or expansion of a node during the search process).

• Ability to write new planners with much ease. Comes with a weighted A-star (that includes Dijkstra's and normal A-star) planner by default.
  

If you found the library useful in research, please cite it as follows:

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} }

Upcoming release: Planned release of v3.0 some time in mid/late 2013. Besides complete re-structuring and modularization of the code for greater flexibility and ease of development, there will be bug fixes, improved performance (with significant attention on code optimization), extensive support for multi-thread applications, and backward compatibility with v2.0. This will be accompanied by a more friendly documentation/tutorial.