learnprogramming / libastar Goto Github PK

The current definition of Generator is std::function<std::vector<T>(const T&)>, for some type T. This requires construction of a new std::vector for every call to the Generator, which is once for every evaluated state, which may be a very large number. Each construction requires a corresponding heap allocation. It would be better for performance to reuse already allocated memory.

Therefore I propose the following signature for Generator: std::function<void(std::vector<T>&, const T&)>. This function will be passed an empty std::vector in which objects can be directly constructed via emplace_back. Objects can subsequently be moved out of the vector, allowing the storage to be reused on the next call. This should significantly reduce the number of heap allocations in large search spaces.

The biggest downside to this approach is the less intuitive interface. It may be possible to achieve both purposes with a some other design, (a policy-based one, perhaps?), but such inevitably come with other trade-offs and would require a complete shift in both implementation of the library as well as code using the library. The proposed shift breaks merely one function, and in a way that is trivially fixable on both sides. A complete redesign should be evaluated separately.

Currently nodes are passed around via std::shared_ptr objects. These are convenient, but very slow due to their thread safety, which is not a concern for the current single-threaded implementation. Our usage pattern is similar to the one here which sees roughly a 4x slowdown using std::shared_ptr. Therefore we can expect nearly a 4x speedup if we can replace std::shared_ptr usage with a non-thread-safe reference-counting pointer, or perhaps std::unique_ptr and raw pointers.

Presently any Node can exist in up to three places simultaneously: the open set, the closed set, and as part of a dynamic list via shared pointers. Since a Node contains a user-provided object, it is possible that it can be very large. To reduce memory use we should make the open and closed sets purely based on shared pointers.

Presently it is possible for a given state to be present in the open set multiple times. This can occur when it is possible to get to a given state multiple times through the neighbor-generation process before that state is evaluated and placed in the closed set.

Because the open set is a heap structured by cost, it is impractical to search through the open set by state in order to prevent duplicate insertions, as such a search would be linear and very time consuming in large search spaces.

We should investigate a data structure that allows heap ordering by one metric and efficient state search by another. This may be as simple as a wrapper around a heap with a std::set to keep track of states. Shared pointers should be used to keep memory use down.

The std::priority_queue creates a binary heap, which is generally quite good, but it may pay off to use a custom implementation of a Fibonacci heap, splay tree, HOT queue, indexed array, hash table, or (similar to the existing HeapSet) combination thereof.

There has been some research on improving the general A* algorithm. We should see if any of these optimizations may be (optionally) applied.

• Extensions and Applications of the A* Algorithm - presents a method of dynamically improving a given heuristic so that no node is visited more than once.
• Optimizing the A* Algorithm - presents a couple high-level improvements: replace closed list with a boolean flag, conditional use of a priority queue, and early expansion of nodes
• Fast Pathfinding via Symmetry Breaking - may apply only to rectangular grid path finding, but can significantly reduce the search space

See also: http://theory.stanford.edu/~amitp/GameProgramming/

Right now the implementation is generic and works for arbitrary types, but does not allow for much customization, which means that optimizations cannot easily be used when they are applicable. A design that allows feature injection would enable, for instance, the use of jump point search when the state is known to be a grid with uniform costs. Such an implementation should provide reasonable defaults in order that the user is able to specify as little as possible but as much as desired.

As of stdlibc++-4.7.2 there is no support for the emplace or emplace_hint member functions for associative containers. According to bug 44436 this has been resolved and slated for release in libstdc++-4.8. Changes should be made upon release.

Other implementations include:

• http://code.google.com/p/a-star-algorithm-implementation/
• https://github.com/arirahikkala/astar-jps
• http://code.google.com/p/recastnavigation/

We should measure both quantitative and qualitative differences to these other implementations for identical problems with comparable implementations, e.g. the 8-puzzle problem, and document them in the wiki. Some characteristics might be:

• Run time
• Memory use
• Ease of use
• Extensibility

Code for #13 increased some memory use over #10 and reduced some. We should check for the root cause of the unexpected difference.

Currently the implementation uses a min-heap and so always finds the least expensive path. In some cases it is possible to find the most expensive path by pre-processing the input and negating values, but this is not always feasible. It would be good to allow finding the most expensive path through the use of a max-heap.