As it is only the introduction it is mainly non-technical. I've also made some additional alterations in an effort to make it as accessible as possible for a non-computer science audience. Anyways, here goes:
Consider the problem of finding a route from one location in a city to another when navigating with a map. Before any travel can begin, a route for travel (or at least a partial route) must be found. Unfortunately, there may be a large number of candidate partial paths that must be considered before a complete route is found.
In this example, a single agent has the task of path finding. In general, all agents — whether they be living or artificial — are faced with some number of tasks to perform. In order to complete these tasks, agents must develop plans for action.
The effectiveness with which an agent plans is evaluated in terms of two different measures. The first is the time required to find a plan that will complete the given tasks. The second is the cost of the plan, the value of which will depend on the agent’s objectives. In the case of navigation, the possibilities for plan cost include distance travelled --- if the agent is to find a short path --- or the expected travel time --- if the agent is to find a quick path (ie. when navigating in a map, such an agent would prefer the use of highways over city streets).
In many domains, there is additional information that can be used to inform and thereby speed up planning. For example, when navigating between locations in Edmonton, Canada, it is reasonable to initially disregard routes through distant locations such as Madagascar. Moreover, if the desired destination is east of the starting location, the first routes to consider are naturally those that initially proceed eastward (if such paths exist).
Such information can be used to build heuristics which estimate the cost of the remaining path to the goal from any area in the domain. The field concerned with the development of heuristics and the construction of algorithms that use heuristics for planning is called single-agent search. In this field, planning is performed by building complete plans from some partial plans by a process which is guided by the given heuristic.
Single-agent search remains an important field for research due to the large number of real-world applications in which search algorithms have proven to be effective problem-solving techniques. These applications include autonomous robot navigation, in which heuristics are used to
guide pathfinding [6]; DNA sequence alignment [5]; and, computer games [7].
There is a class of single-agent search algorithms that will provably find the lowest cost solution provided that the heuristic satisfies certain conditions. Unfortunately, as problem domains grow larger, these optimal algorithms will often take too long to find a solution. To address this issue, suboptimal single-agent search algorithms have been developed. These algorithms sacrifice solution quality for a decrease in search time and are ideal when a solution (often near optimal) is needed quickly.
When constructing a single-agent search system, it must first be determined if suboptimal solutions will suffice or if optimal solutions are desired. Another consideration is if planning will precede execution or if the system is to work in real-time, with planning and plan execution being interleaved. The system designer is then faced with decisions regarding the proper selection of an algorithm and a heuristic function for the given domain(s). There are also often subtle choices such as tie-breaking (the order in which equally promising candidate paths are considered) that can significantly affect the planning speed. With all of these possible choices, properly recognizing and evaluating all of the necessary design decisions is a vital aspect of building an effective search system.
In the case of suboptimal problem solving, additional options arise as almost all applicable algorithms involve some kind of parameterization (where a parameter refers to some sort of numerical setting that can affect algorithm performance). For example, in the weighted variants of A*, IDA*[3], and RBFS [4], the value of the weight parameter must be set. Similarly, beam-search variants like BULB [2] and Beam-stack search [8] require the selection of a value for the beam width parameter.
Any adjustment of these parameter values can change both the solution quality and the search speed. In a few cases, there are theoretical results that indicate how changing a parameter will affect the search (such as the bounds on solution quality in weighted A*, weighted IDA*, and weighted RBFS [4]). Unfortunately, it is much more common that a significant amount of pre-computation is needed so as to determine how different parameter settings affect the search. In practice, parameter values are tested on a set of training examples through a process commonly referred to as parameter tuning. The single parameter setting that satisfies any given constraints on solution quality and exhibits the best average performance is then used in all future runs of the algorithm.
One drawback of parameter tuning is that it generally customizes the search algorithm for a specific problem domain (ie. an algorithm used for navigation may be tuned specifically for city-driving as opposed to for highway driving). As such, the results of this expensive process cannot effectively be transferred across domains — a fact that is of particular concern when designing general search systems such as automated heuristic search planners. In these systems, general heuristics are used to guide a suboptimal search algorithm over many domains. In practice, planners such as HSP [1] commit to a single parameter value that will hopefully be effective over a diverse class of problems.
Parameter tuning also suffers from another deficiency: there is no guarantee that a tuned value will perform well on each individual problem. Tuning only finds the setting that has the best average performance. On a per problem basis, there can be other parameter values which significantly outperform the tuned setting. In this thesis, we will demonstrate that it is often the case that if a search system could properly select the correct parameter setting for each problem, the planning speed over a number of problems can be greatly improved.
In this end, we will consider the dovetailing procedure as an approach to this problem. Dovetailing involves running several independent instances of an algorithm — each of which has a different set of parameter settings — at the same time by interleaving the execution of the instances. The
procedure can also be trivially extended so as to work with multi-processor computers. This aspect of the algorithm is important due to the increasing availability of such machines. As such, we will also analyze the performance of the algorithm when used in this fashion.
The main contributions of this thesis can be summarized as follows:
- The single-agent search algorithms of WA*, WIDA*, WRBFS, and BULB are described, and the weaknesses of WA*, WIDA*, and WRBFS as suboptimal search algorithms are demonstrated. The behaviour of these algorithms in the sliding tile and pancake puzzles as a function of the weight parameter will also be shown. Similarly, the behaviour of BULB in these domains as a function of the beam width will be demonstrated.
- Dovetailing is explored as an approach to proper parameter selection. Dovetailing is shown to significantly enhance WIDA* in the domains of the sliding tile puzzle and the pancake puzzle. The parallel version of dovetailing is also shown to exhibit massive improvements in search time when used with this algorithm. In the case of WRBFS, dovetailing without any pre-computation is shown to improve the speed of the algorithm in the sliding tile puzzle domain, and offer comparable performance in the pancake puzzle domain. Dovetailing with WRBFS over different tie-breaking schemes will also improve the quality of the solutions. We will also demonstrate that parallel dovetailing offers an effective parallelization of this algorithm.
- The sequential version of dovetailing will be shown to decrease the search speed of BULB and WA*, but improve the quality of the solutions when considered over different tie-breaking schemes. The reasons for this behaviour are discussed. The parallel version of dovetailing will also be shown to offer the best performance of all known parallelizations of WA* when higher weights are used in the sliding tile puzzle domain.
[1] Blai Bonet and Hector Geffner. Planning as heuristic search. Artif. Intell., 129(1-2):5–33, 2001.
[2] David Furcy and Sven Koenig. Limited Discrepancy Beam Search. In IJCAI, pages 125–131, 2005.
[3] Richard E. Korf. Iterative-Deepening-A*: An Optimal Admissible Tree Search. In IJCAI, pages 1034–1036, 1985.
[4] Richard E. Korf. Linear-Space Best-First Search. Artif. Intell., 62(1):41–78, 1993.
[5] Matthew McNaughton, Paul Lu, Jonathan Schaeffer, and Duane Szafron. Memory-Efficient A* Heuristics for Multiple Sequence Alignment. In AAAI/IAAI, pages 737–743, 2002.
[6] Anthony Stentz. The Focussed D* Algorithm for Real-Time Replanning. In IJCAI, pages 1652–1659, 1995.
[7] Bryan Stout. Smart moves: Intelligent Pathfinding. Game Developer Magazine, October:28–35, 1995.
[8] Rong Zhou and Eric A. Hansen. Beam-Stack Search: Integrating Backtracking with Beam Search. In Susanne Biundo, Karen L. Myers, and Kanna Rajan, editors, ICAPS, pages 90–98. AAAI, 2005.
By the way, if you'd like to read the whole thing, send me an email and I can pass it along.
Posts
