We found a match
Your institution may have rights to this item. Sign in to continue.
- Title
Path-Cost Bounds for Parameterized Centralized Variants of A* for Static and Certain Environments.
- Authors
Mali, Amol D.; Tang, Minh
- Abstract
A* search and its variants have been used in various fields for solving problems with large search spaces where state transitions occur because of application of operators. The key values in A* search are g(n) and h(n), where g(n) is the cost of the path from root (or start) node to node n, and h(n) is the estimated cost of cheapest path from n to goal. In this paper, we report on a space of variants of A* based on the following ideas: (i) using weighting functions for g(n) and h(n), (ii) evaluating different nodes with different heuristics, (iii) evaluating nodes with computationally cheap heuristics and re-evaluating some nodes with computationally expensive heuristics, and (iv) changing the size of the set of nodes from which the node to be expanded next is selected. We report on the bounds on the costs of solutions found by these variants of A*. We also report on the bounds for meta-variants of A* that invoke these variants sequentially. We show how the results can be used to obtain a more flexible search control without increasing the bound on the cost of the solution found by a variant or a meta-variant.
- Subjects
PATH analysis (Statistics); MATHEMATICAL bounds; PARAMETERIZATION; PROBLEM solving; SET theory
- Publication
International Journal on Artificial Intelligence Tools, 2016, Vol 25, Issue 4, p-1
- ISSN
0218-2130
- Publication type
Article
- DOI
10.1142/S0218213016500287