Dijkstra’s Algorithm is the most basic search algorithm for a planning problem. For a given start state, goal state and a weighted graph, Dijkstra’sAlgorithm can find the sequence of states with the smallest sum of edge costs connecting these states. But unaware of the direction in which goal state actually lies, this algorithm finds the shortest path from the start state to every other state which is closer to start state than goal state. This seemingly uninteresting fact appeared as a revelation to me as I noticed the metaphorical resemblance it had with life.
Later on an extension to Dijkstra’s Algorithm was proposed by Nilsson et al. known as A* search algorithm which would lay the foundation of heuristic search methods. A* search algorithm performed better because of its ability to guide the search tree towards goal states using heuristic information. Properties such as admissibility and consistency were defined for heuristic function.
Properties of Heuristic Function
If heuristic function is admissible, A* search algorithm will expand all the states present on the optimal path before termination and thus will identify the optimal path. In terms of heuristic function, to be admissible for a minimization problem means, for every state \(n\) , \(h(n)\le h^{*}(n)\) where \(h(n)\) is heuristic function and \(h^*(n)\) is optimal path length from state \(n\) to goal state.
To give a rough outline of proof : If we can somehow show that state on optimal path will always be expanded if the above mentioned condition is true, then we know that optimal path will be explored and found. So what should be the condition for a state \(n\) belonging to graph to expand during A* search ? Let a state \(n\) be expanded, then it must have achieved it’s optimal path i.e \(g(n) = g^{*}(n)\) and we have assumed that \(h(n)\le h^{*}(n)\) so \(f(n)\le f^{*}(n)\) at the time of expansion. So all the states on the optimal path and satisfying \(f(n)\le f^{*}(s)\) will be expanded before termination of algorithm and thus the optimal path will be found.
If the heuristic function is exactly equal to optimal heuristic function then only the nodes on optimal path to goal will be expanded What about the case when more than one optimal path exist?. If heuristic function is not admissible then depending on which nodes are overestimated it may be possible that optimal path is still generated although not guaranteed.
A heuristic function is said to be consistent if, \(h(n_i) \le h(n_{i+1}) + c(n_i,n_{i+1})\) where \(h(n)\) is the heuristic function and \(c(n_i,n_{i+1})\) is the cost of edge connecting state \(n_i\) and \(n_{i+1}\). The possibility that a closed set can be part of an algorithm comes with the condition that heuristic function must be consistent. If heuristic is not consistent then the states might need to be expanded multiple times to ensure optimal path from start state to goal state is found. Also consistency of heuristic function implies admissibility.
Research
Hybrid A* Motion Planner
This is a search-based motion planner for non-holonomic vehicles navigating in unconstrained environments. The usual practise in motion planning is to adopt two level planning hierarchy where a global planner plans a long distance optimal path and local planner defines path w.r.t to sequence of motion primitives. This two level planning often leads to sub-optimal planning and can easily be replaced by this planner. Hybrid A* generates its neighbouring states considering motion primitives of robots and thus the path generated by A* algorithm is feasible for navigation. It uses maximum of two admissible heuristics: Dubin’s Cost and Backward A*. It also uses analytic expansions after every few steps to improve search speed.
This planner was integrated with Gazebo ROS framework and tested successfully on AGV, IIT KGP’s autonomous car.
Island Search Algorithm
Our effort in this work was to use the heuristic information present in the form of special states (called island states) in state space to improve search performance. The development of this algorithm has been orthogonal to recent developments which stress upon using heuristic function value effectively while popping from open-list and thus will improve the performance of any algorithm in general.
Applications of such a search algorithm include robotic path planning in regions with narrow passages and mitigating heuristic depressions in state space. A large section of path planning algorithms performs poorly when the goal state lies across narrow passages. The reason search tree is not able to expand through such narrow passages is mainly attributed to poor heuristic guidance. Also, states with incorrect heuristic information can be detected over multiple iterations of a search algorithm. Such states must be dealt with, to improve performance through experience.
The purpose of this research is to develop an algorithm that utilises a set of island states as heuristics to improve the performance of the search algorithm and produce a bounded optimal path connecting start state and goal state.
For more details, check out my Thesis!