It is commonly appreciated that solving search problems optimally can take too long. Bounded suboptimal search algorithms trade increased solution cost for reduced solving time. Explicit Estimation Search (EES) is a recent state-of-the-art algorithm specifically designed for bounded suboptimal search. Although it tends to expand fewer nodes than alternative algorithms, such as weighted A* (WA*), its per-node expansion overhead is higher, causing it to sometimes take longer. In this paper, we present simplified variants of EES (SEES) and an earlier algorithm, A*epsilon (SA*epsilon), that use different implementations of the same motivating ideas to significantly reduce search overhead and implementation complexity. In an empirical evaluation, we find that SEES, like EES, outperforms classic bounded suboptimal search algorithms, such as WA*, on domains tested where distance-to-go estimates enable better search guidance. We also confirm that, while SEES and SA*epsilon expand roughly the same number of nodes as their progenitors, they solve problems significantly faster and are much easier to implement. This work widens the applicability of state-of the-art bounded suboptimal search by making it easier to deploy.

List of organizing committee members for the Twenty-Fourth International Conference on Automated Planning and Scheduling.

The papers in this proceedings present the latest advances in the field of automated planning and scheduling, ranging in scope from theoretical analyses of planning and scheduling problems and processes, to new algorithms for planning and scheduling under various constraints and assumptions, and the empirical evaluation of planning and scheduling techniques. They reflect recent research trends in subareas such as optimal planning, probabilistic and nondeterministic planning, path planning, multiagent planning, and new developments in heuristics and their analysis for planning algorithms.

Multiple sequence alignment (MSA) is a central problem in computational biology. It is well known that MSA can be formulated as a shortest path problem and solved using heuristic search, but the memory requirement of A* makes it impractical for all but the smallest problems. Partial Expansion A* (PEA*) reduces the space complexity of A* by generating only the most promising successor nodes. However, even PEA* exhausts available memory on many problems. Another alternative is Iterative Deepening Dynamic Programming, which uses an uninformed search order but stores only the nodes along the search frontier. However, it too cannot scale to the largest problems. In this paper, we propose storing nodes on cheap and plentiful secondary storage. We present a new general-purpose algorithm, Parallel External PEA* (\xppea), that combines PEA* with Delayed Duplicate Detection to take advantage of external memory and multiple processors to solve large MSA problems. In our experiments, \xppea\ is the first algorithm capable of solving the entire Reference Set 1 of the standard BAliBASE benchmark using a biologically accurate cost function. This work suggests that external best-first search can effectively use heuristic information to surpass methods that rely on uninformed search orders.

In looking back on the last five to ten years of work in heuristic search a few trends emerge. First, there has been a broadening of research topics studied. Second, there has been a deepened understanding of the theoretical foundations of search. Third, and finally, there have been increased connections with work in other fields. This paper, corresponding to a AAAI 2012 invited talk on recent work in heuristic search, highlights these trends in a number of areas of heuristic search. It is our opinion that the sum of these trends reflects the growth in the field and the fact that heuristic search has come of age.

There has been much interest recently in problems that com-bine high-level task planning with low-level motion planning.In this paper, we present a problem of this kind that arises inmulti-vehicle mission planning. It tightly integrates task al-location and scheduling, who will do what when, with pathplanning, how each task will actually be performed. It ex-tends classical vehicle routing in that the cost of executing aset of high-level tasks can vary significantly in time and costaccording to the low-level paths selected. It extends classi-cal motion planning in that each path must minimize costwhile also respecting temporal constraints, including thoseimposed by the agent’s other tasks and the tasks assigned toother agents. Furthermore, the problem is a subtask withinan interactive system and therefore must operate within se-vere time constraints. We present an approach to the problembased on a combination of tabu search, linear programming,and heuristic search. We evaluate our planner on represen-tative problem instances and find that its performance meetsthe demanding requirements of our application. These resultsdemonstrate how integrating multiple diverse techniques cansuccessfully solve challenging real-world planning problemsthat are beyond the reach of any single method.

It assumes that the Consider the problem faced by a unmanned aerial vehicle probability distribution over incoming goals is either known (UAV) dispatcher who must plan for a set of UAVs to service or learn-able and employs the technique of optimization a set of observation requests. To service a request, one of the in hindsight, previously developed for online scheduling UAVs must fly over a given strip of land with its observation and recently investigated for planning with stochastic actions equipment turned on. The dispatcher wants to minimize the (Mercier and van Hentenryck 2007; Yoon et al. 2008; time between when a request arrives and when an UAV has 2010). This technique first samples from the distribution of completed the flyover. Even when the actions of the UAV, possible future goal arrivals and then considers which next such as flying particular routes or switching on/off observational action optimizes the expected cost when averaged over the equipment, can be regarded as deterministic, the sampled futures. By using this anticipatory technique, our stochastic arrival of new requests can make for a challenging planner is able to take future goals into account.

The memory requirements of basic best-first heuristic search algorithms like A* make them infeasible for solving large problems. External disk storage is cheap and plentiful com- pared to the cost of internal RAM. Unfortunately, state-of- the-art external memory search algorithms either rely on brute-force search techniques, such as breadth-first search, or they rely on all node values falling in a narrow range of in- tegers, and thus perform poorly on real-world domains with real-valued costs. We present a new general-purpose algo- rithm, PEDAL, that uses external memory and parallelism to perform a best-first heuristic search capable of solving large problems with real costs. We show theoretically that PEDAL is I/O efficient and empirically that it is both better on a stan- dard unit-cost benchmark, surpassing internal IDA* on the 15-puzzle, and gives far superior performance on problems with real costs.

Suboptimal search algorithms offer shorter solving times by sacrificing guaranteed solution optimality. While optimal searchalgorithms like A* and IDA* require admissible heuristics, suboptimalsearch algorithms need not constrain their guidance in this way. Previous work has explored using off-line training to transform admissible heuristics into more effective inadmissible ones. In this paper we demonstrate that this transformation can be performed on-line, during search. In addition to not requiring training instances and extensive pre-computation, an on-line approach allows the learned heuristic to be tailored to a specific problem instance. We evaluate our techniques in four different benchmark domains using both greedy best-first search and bounded suboptimal search. We find that heuristics learned on-line result in both faster search andbetter solutions while relying only on information readily available in any best-first search.

Our approach is conceptually simple: we perform a the search algorithm. In video game pathfinding and robot standard dynamic search but interrupt it periodically to move motion planning, the search is often required to be real-time, the agent according to a real-time search. In this paper, we that is, return the next move for the agent within a strict time use D* Lite (Koenig and Likhachev 2002) or Anytime D* bound, so that the agent can continue acting in the world. To (Likhachev et al. 2005) as the dynamic search algorithm and accommodate this constraint, real-time search algorithms interleave LRTA* (Korf 1990) or LSS-LRTA* (Koenig and Sun 2009) planning and moving. Because the agent must make as the real-time search algorithm. D* Lite and Anytime D* a choice of which move to execute next before finding a perform a global search backwards from the goal, trying to complete path to a goal, real-time search algorithms achieve reach the agent's current location. LRTA* and LSS-LRTA* fast response times at the cost of sub-optimality of the resulting perform a local search forward from the agent's current location, trajectories. There has been much research on real-time trying to reach the goal. Therefore, RTD* is a form of search algorithms, starting with LRTA* (Korf 1990).