Description

Abstract Heuristic search is one of the fundamental problem solving techniques in artificial intelligence, which is used in general to efficiently solve computationally hard problems in various domains, especially in planning and optimization. In this paper, we present an anytime heuristic search algorithm called anytime pack search (APS) which produces good quality solutions quickly and improves upon them over time, by focusing the exploration on a limited set of most promising nodes in each iteration. We discuss the theoretical properties of APS and show that it is complete. We also present the complexity analysis of the proposed algorithm on a tree state-space model and show that it is asymptotically of the same order as that of A*, which is a widely applied best-first search method. Furthermore, we present a parallel formulation of the proposed algorithm, called parallel anytime pack search (PAPS), which is applicable for searching tree state-spaces. We theoretically prove the completeness of PAPS. Experimental results on the sliding-tile puzzle problem, traveling salesperson problem, and single machine scheduling problem depict that the proposed sequential algorithm produces much better anytime performance when compared to some of the existing methods. Also, the proposed parallel formulation achieves super-linear speedups over the sequential method.Keywords Heuristic search State-space search Anytime algorithms Parallel algorithms NP-hard problems

1 Introduction State-space search with heuristic guidance has been widely applied over the years across many domains, such as, Bayesian learning (Malone and Yuan 2013; Yuan and Malone 2013), image processing (Martelli 1976; Rubin 1978), decision making (Martelli and Montanari 1978), machine learning (Dietterich and Michalski 1981), data mining (Vadlamudi et al. 2012a), scheduling (Muscettola et al. 1989; Sabuncuoglu and Bayiz 1999; Vadlamudi et al. 2013b), speech recognition (Lee et al. 1989), multi-objective optimization (Dasgupta et al. 1994), planning (Bonet and Geffner 2001), computational biology (Zhou and Hansen 2002), bio-informatics (Keedwell and Narayanan 2005), network design (Bagchi and Mahanti 1985), pattern analysis and game playing (Kumar and Kanal 1982), and so on. Many of these search algorithms proceed in a best-first manner, wherein the most promising nodes are chosen for exploration based on their distances from start node and estimates of their closeness to a goal node. A* (Hart et al. 1968) is one of the widely adapted algorithms in this genre. A* guarantees that the first goal node encountered by it is an optimal solution when admissible and consistent heuristics are used (Russell and Norvig 2003). While it takes advantage of the heuristic guidance available, the number of nodes expanded by it is still of the exponential