Heuristically guided bi-directional search in real-time for solving problems of discrete optimization

Master of Science in Computational Science 2013-2015 EXT T.K Manoj Kumar Ambuj Mahanti (MIS Group)
"Indian Institute Of Management, Calcutta"

For very long time, searching techniques such as A* and IDA* have been used extensively. Search algorithms are widely used in real world problems like Combinatorial Auctions, Flow Shop Scheduling, Robot Navigation, etc. All these applications of heuristic search require optimal solutions. As such, the search technique should be very efficient. The Sliding Tiles Problem of 15-Puzzle has been used as a test-bed for a long time. These algorithms work fine for problems like 15-puzzle problem. However, the standard heuristic that is used for these algorithms the Manhatan heuristic is not the best possible heuristic as it does not account for interaction of tiles. While it would be impossible to account for all tile interactions the Disjoint Additive Pattern Database Heuristic provides us with a better heuristic than Manhattan thereby reducing the number of nodes explored for finding solution.This could be of particular effect on larger instances of the n-puzzle, such as 24-puzzle problem where standard algorithms have proved to be unsuccessful. A*requires huge amount of memory, while IDA* requires huge amount of time.
In this project, a modified version of Bidirectional search has been taken into consid-eration which gives near optimal solution using less time and space. The performance of this search has been compared with the performance of IDA* search. We have taken 15-puzzle into consideration along with Additive Pattern Database heuristic. We have also used a Block depth first search method to find near optimal results for 24-puzzle problems.