A* Search has implemented as a base search program in this project. It is an Artificial Intelligence search technique, known as Heuristic Search. The idea behind heuristic search is that instead of expanding every possible node, it expands the node that is most likely to be nearest to the goal. To do this, the search algorithm uses an Evaluation function, f(n) to calculate a value to indicate which node to expand next. The function has two components. g(n) = path cost so far from start and h(n) = estimated cost from current to the goal. Therefore, f(n) = g(n) + h(n).
When the heuristic estimate function h(n) is "admissible", A* search will then guarantee optimal solution, shortest path.
Further improvement of the search can be achieved by using Hierarchical search methods. It breaks the search into smaller searches to the different levels of abstraction. Each of the levels contains the abstraction of the previous level. Thus, abstractions will have smaller size of search space and the complexity of the search in the abstractions is reduced.
In this project, we have created 2 levels of abstaction. Level 1 contains all the roads. Level 0 contains only motorways. This would produce routes more focus on the motorway for long distance. Thus, the route is easier to drive.
For full details, please look at my Final Report.
Back