 |
    |
Anytime Column Search
Satya Gautam Vadlamudi1, Piyush Gaurav1, Sandip Aine2, and Partha Pratim Chakrabarti1
1Indian Institute of Technology Kharagpur, Kharagpur, WB 721302, India
satya@cse.iitkgp.ernet.in
ppchak@cse.iitkgp.ernet.in
2Carnegie Mellon University, Pittsburgh, PA 15213, USA
asandip@andrew.cmu.edu
Abstract. Anytime heuristic search algorithms are widely applied where best-first search algorithms such as A* require large or often unacceptable amounts of time and memory. Anytime algorithms produce a solution quickly and iteratively improve the solution quality. In this paper, we propose novel anytime heuristic search algorithms with a common underlying strategy called Column Search. The proposed algorithms are complete and guarantee to produce an optimal solution. Experimental results on sliding-tile puzzle problem, traveling salesman problem, and robotic arm trajectory planning problem show the efficacy of proposed methods compared to state-of-the-art anytime heuristic search algorithms.
Keywords: problem solving, heuristic search, anytime algorithms
LNAI 7691, p. 254 ff.
lncs@springer.com
© Springer-Verlag Berlin Heidelberg 2012