OptimalPathPlanningWithASearchAlgorithm
Michael Nourai
December 12, 2011
Attach:mnourai_optimalpath.pdf
I live 8 miles from my work in Salem MA, but it takes minimum of 40 minutes to an hour and half to get to work. Over the years this has become a daily challenge since I commute everyday to a very busy city and in addition I need to have a consistent work schedule. My project addresses this real-world problem with AI path planning solution finding an optimal path using A* search algorithm.
Concepts Demonstrated
A* search - A heuristic driven A* search is used for finding an optimal path from Danvers to Salem.
Innovation
For the A* Search algorithm to work efficiently, h(n), the heuristic part of the f(n) function must be an admissible heuristic, i.e. it must not overestimate the distance to the goal. To satisfy the A* Search algorithm's admissibility requirement, the Haversine formula has been implemented for calculating h(n).
The haversine formula is an equation important in navigation, giving great-circle distances between two points on a sphere from their longitudes and latitudes. It is a special case of a more general formula in spherical trigonometry, the law of haversines, relating the sides and angles of spherical "triangles". [http://en.wikipedia.org/wiki/Haversine_formula]
The longitudes and latitudes of every node in the earth map has been calculated using an online tool that GIS expert and professional use. The tool requires Microsoft Silverlight, and can be found at http://explorer.arcgis.com/
Researching and finding the Haversine formula and its concept was an incredible innovation for my project. Before finding this innovation, calculating h(n), the heuristic part of the A* search algorithm for a 12-13 miles map seemed like a big job. With Haversine, no map problem is too big. I can map a very large area that stretches to thousands of miles with incredible accuracy. Using this technique also guarantees that the heuristic h(n) is admissible.
With the GIS mapping tool (shown below) paired with Haversine formula, I can successfully tackle much bigger problems applying the A* admissible search algorithm for finding an optimal path for areas as big as the USA or areas across the continents.
Another innovation that went into my project is the implementation of the code. The code was designed and developed in CSharp 4.0 with .NET Framework 4.0, using object-oriented programming techniques, including encapsulation, inheritance, and polymorphism. The CSharp features such as Func, Delegate, and Lambda Expressions have also been used for more efficient coding.
Evaluation of Results
The program successfully finds the optimal path from the start point in Danvers to the destination point in Salem. The solution has been tested with simulated road conditions and has performed exceptionally well, i.e. the A* Search algorithm worked every time and was able to find the optimal path.
A menu driven interface has been designed and implemented to simulate the road blockage condition which can be due to heavy traffic, road construction, or bad weather condition. The calculated optimal path is then displayed on the console, giving step by step directions from the start to the destination.
To determine if the solution is successful in the real-world, a variety of driving conditions needs to be tested using this solution. I am planning to put the solution to test in the real-world for several months, while collecting and compiling its result. The solution is successful in the real-world when the average arriving time is consistently low for variety of commute conditions.
Additional Remarks
My project mapped out all the practical routes from Danvers to Salem in a form of a graph with nodes. Where each node is a starting point of a street. Then the A* Search algorithm is used to efficiently traverse path between the nodes.
As A* traverses the graph, it follows a path of the lowest known cost, keeping a sorted priority queue of alternate path segments along the way. If, at any point, a segment of the path being traversed has a higher cost than another encountered path segment, it abandons the higher-cost path segment and traverses the lower-cost path segment instead. This process continues until the goal is reached.
The distance-plus-cost heuristic function f(n) is used to determine the order in which the search visits nodes in the tree. The distance-plus-cost heuristic is a sum of two functions g(n) and h(n). Where g(n) is the cost of reaching node n from the start state and h(n) is an heuristic estimate of the distance from node n to the nearest goal node.