The Experts below are selected from a list of 123 Experts worldwide ranked by ideXlab platform
Nathan R. Sturtevant - One of the best experts on this subject based on the ideXlab platform.
-
IJCAI - Front-to-End Bidirectional Heuristic Search with Near-Optimal Node Expansions
Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence, 2017Co-Authors: Jingwei Chen, Robert C. Holte, Sandra Zilles, Nathan R. SturtevantAbstract:It is well-known that any admissible unidirectional Heuristic search algorithm must expand all states whose f-value is smaller than the optimal solution cost when using a Consistent Heuristic. Such states are called “surely expanded” (s.e.). A recent study characterized s.e. pairs of states for bidirectional search with Consistent Heuristics: if a pair of states is s.e. then at least one of the two states must be expanded. This paper derives a lower bound, VC, on the minimum number of expansions required to cover all s.e. pairs, and present a new admissible front-to-end bidirectional Heuristic search algorithm, Near-Optimal Bidirectional Search (NBS), that is guaranteed to do no more than 2VC expansions. We further prove that no admissible front-to-end algorithm has a worst case better than 2VC. Experimental results show that NBS competes with or outperforms existing bidirectional search algorithms, and often outperforms A* as well.
-
Front-to-End Bidirectional Heuristic Search with Near-Optimal Node Expansions
arXiv: Artificial Intelligence, 2017Co-Authors: Jingwei Chen, Robert C. Holte, Sandra Zilles, Nathan R. SturtevantAbstract:It is well-known that any admissible unidirectional Heuristic search algorithm must expand all states whose $f$-value is smaller than the optimal solution cost when using a Consistent Heuristic. Such states are called "surely expanded" (s.e.). A recent study characterized s.e. pairs of states for bidirectional search with Consistent Heuristics: if a pair of states is s.e. then at least one of the two states must be expanded. This paper derives a lower bound, VC, on the minimum number of expansions required to cover all s.e. pairs, and present a new admissible front-to-end bidirectional Heuristic search algorithm, Near-Optimal Bidirectional Search (NBS), that is guaranteed to do no more than 2VC expansions. We further prove that no admissible front-to-end algorithm has a worst case better than 2VC. Experimental results show that NBS competes with or outperforms existing bidirectional search algorithms, and often outperforms A* as well.
-
AAAI - Worst-case solution quality analysis when not re-expanding nodes in best-first search
2014Co-Authors: Richard Valenzano, Nathan R. Sturtevant, Jonathan SchaefferAbstract:The use of inConsistent Heuristics with A* can result in increased runtime due to the need to re-expand nodes. Poor performance can also be seen with Weighted A* if nodes are reexpanded. While the negative impact of re-expansions can often be minimized by setting these algorithms to never expand nodes more than once, the result can be a lower solution quality. In this paper, we formally show that the loss in solution quality can be bounded based on the amount of inconsistency along optimal solution paths. This bound holds regardless of whether the Heuristic is admissible or inadmissible, though if the Heuristic is admissible the bound can be used to show that not re-expanding nodes can have at most a quadratic impact on the quality of solutions found when using A*. We then show that the bound is tight by describing a process for the construction of graphs for which a best-first search that does not re-expand nodes will find solutions whose quality is arbitrarily close to that given by the bound. Finally, we will use the bound to extend a known result regarding the solution quality of WA* when weighting a Consistent Heuristic, so that it also applies to other types of Heuristic weighting.
-
SOCS - Estimating Search Tree Size with Duplicate Detection
2014Co-Authors: Levi H. S. Lelis, Roni Stern, Nathan R. SturtevantAbstract:In this paper we introduce Stratified Sampling with Duplicate Detection (SSDD), an algorithm for estimating the number of state expansions performed by Heuristic search algorithms seeking solutions in state spaces represented by undirected graphs. SSDD is general and can be applied to estimate other state-space properties. We test SSDD on two tasks: (i) prediction of the number of A* expansions in a given f-layer when using a Consistent Heuristic function, and (ii) prediction of the state-space radius. SSDD has the asymptotic guarantee of producing perfect estimates in both tasks. Our empirical results show that in task (i) SSDD produces good estimates in all four domains tested, being in most cases orders of magnitude more accurate than a competing scheme, and in task (ii) SSDD quickly produces accurate estimates of the radii of the 4x4 Sliding-Tile Puzzle and the 3x3x3 Rubik's Cube.
-
InConsistent Heuristics
2007Co-Authors: Uzi Zahavi, Ariel Felner, Jonathan Schaeffer, Nathan R. SturtevantAbstract:In the field of Heuristic search it is well-known that improving the quality of an admissible Heuristic can significantly decrease the search effort required to find an optimal solution. Existing literature often assumes that admissible Heuristics are Consistent, implying that consistency is a desirable attribute. To the contrary, this paper shows that an inConsistent Heuristic can be preferable to a Consistent Heuristic. Theoretical and empirical results show that, in many cases, inconsistency can be used to achieve large performance improvements.
Robert C. Holte - One of the best experts on this subject based on the ideXlab platform.
-
IJCAI - Front-to-End Bidirectional Heuristic Search with Near-Optimal Node Expansions
Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence, 2017Co-Authors: Jingwei Chen, Robert C. Holte, Sandra Zilles, Nathan R. SturtevantAbstract:It is well-known that any admissible unidirectional Heuristic search algorithm must expand all states whose f-value is smaller than the optimal solution cost when using a Consistent Heuristic. Such states are called “surely expanded” (s.e.). A recent study characterized s.e. pairs of states for bidirectional search with Consistent Heuristics: if a pair of states is s.e. then at least one of the two states must be expanded. This paper derives a lower bound, VC, on the minimum number of expansions required to cover all s.e. pairs, and present a new admissible front-to-end bidirectional Heuristic search algorithm, Near-Optimal Bidirectional Search (NBS), that is guaranteed to do no more than 2VC expansions. We further prove that no admissible front-to-end algorithm has a worst case better than 2VC. Experimental results show that NBS competes with or outperforms existing bidirectional search algorithms, and often outperforms A* as well.
-
Front-to-End Bidirectional Heuristic Search with Near-Optimal Node Expansions
arXiv: Artificial Intelligence, 2017Co-Authors: Jingwei Chen, Robert C. Holte, Sandra Zilles, Nathan R. SturtevantAbstract:It is well-known that any admissible unidirectional Heuristic search algorithm must expand all states whose $f$-value is smaller than the optimal solution cost when using a Consistent Heuristic. Such states are called "surely expanded" (s.e.). A recent study characterized s.e. pairs of states for bidirectional search with Consistent Heuristics: if a pair of states is s.e. then at least one of the two states must be expanded. This paper derives a lower bound, VC, on the minimum number of expansions required to cover all s.e. pairs, and present a new admissible front-to-end bidirectional Heuristic search algorithm, Near-Optimal Bidirectional Search (NBS), that is guaranteed to do no more than 2VC expansions. We further prove that no admissible front-to-end algorithm has a worst case better than 2VC. Experimental results show that NBS competes with or outperforms existing bidirectional search algorithms, and often outperforms A* as well.
-
SOCS - Common Misconceptions Concerning Heuristic Search
2010Co-Authors: Robert C. HolteAbstract:This paper examines the following statements about Heuristic search, which are commonly held to be true: More accurate Heuristics result in fewer node expansions by A* and IDA*. A* does fewer node expansions than any other equally informed algorithm that finds optimal solutions. Any admissible Heuristic can be turned into a Consistent Heuristic by a simple technique called pathmax. In search spaces whose operators all have the same cost A* with the Heuristic function h(s)=0 for all states, s, is the same as breadth-first search. Bidirectional A* stops when the forward and backward search frontiers meet. The paper demonstrates that all these statements are false and provides alternative statements that are true.
-
AAAI - Searching without a Heuristic: efficient use of abstraction
2010Co-Authors: Bradford Larsen, Ethan Burns, Wheeler Ruml, Robert C. HolteAbstract:In problem domains where an informative Heuristic evaluation function is not known or not easily computed, abstraction can be used to derive admissible Heuristic values. Optimal path lengths in the abstracted problem are Consistent Heuristic estimates for the original problem. Pattern databases are the traditional method of creating such Heuristics, but they exhaustively compute costs for all abstract states and are thus usually appropriate only when all instances share the same single goal state. Hierarchical Heuristic search algorithms address these shortcomings by searching for paths in the abstract space on an as-needed basis. However, existing hierarchical algorithms search less efficiently than pattern database constructors: abstract nodes may be expanded many times during the course of a base-level search. We present a novel hierarchical Heuristic search algorithm, called Switchback, that uses an alternating direction of search to avoid abstract node re-expansions. This algorithm is simple to implement and demonstrates superior performance to existing hierarchical Heuristic search algorithms on several standard benchmarks.
-
Predicting the performance of IDA* using conditional distributions
Journal of Artificial Intelligence Research, 2010Co-Authors: Uzi Zahavi, Ariel Felner, Neil Burch, Robert C. HolteAbstract:Korf, Reid, and Edelkamp introduced a formula to predict the number of nodes IDA* will expand on a single iteration for a given Consistent Heuristic, and experimentally demonstrated that it could make very accurate predictions. In this paper we show that, in addition to requiring the Heuristic to be Consistent, their formula's predictions are accurate only at levels of the brute-force search tree where the Heuristic values obey the unconditional distribution that they defined and then used in their formula. We then propose a new formula that works well without these requirements, i.e., it can make accurate predictions of IDA*'s performance for inConsistent Heuristics and if the Heuristic values in any level do not obey the unconditional distribution. In order to achieve this we introduce the conditional distribution of Heuristic values which is a generalization of their unconditional Heuristic distribution. We also provide extensions of our formula that handle individual start states and the augmentation of IDA* with bidirectional pathmax (BPMX), a tech nique for propagating Heuristic values when inConsistent Heuristics are used. Experimental results demonstrate the accuracy of our new method and all its variations.
Xiaoping Chen - One of the best experts on this subject based on the ideXlab platform.
-
Extracting optimal actionable plans from additive tree models
Frontiers of Computer Science in China, 2017Co-Authors: Qiang Lu, Yixin Chen, Xiaoping ChenAbstract:Although amazing progress has been made in machine learning to achieve high generalization accuracy and efficiency, there is still very limited work on deriving meaningful decision-making actions from the resulting models. However, in many applications such as advertisement, recommendation systems, social networks, customer relationship management, and clinical prediction, the users need not only accurate prediction, but also suggestions on actions to achieve a desirable goal (e.g., high ads hit rates) or avert an undesirable predicted result (e.g., clinical deterioration). Existing works for extracting such actionability are few and limited to simple models such as a decision tree. The dilemma is that those models with high accuracy are often more complex and harder to extract actionability from. In this paper, we propose an effective method to extract actionable knowledge from additive tree models (ATMs), one of the most widely used and best off-the-shelf classifiers. We rigorously formulate the optimal actionable planning (OAP) problem for a given ATM, which is to extract an actionable plan for a given input so that it can achieve a desirable output while maximizing the net profit. Based on a state space graph formulation, we first propose an optimal Heuristic search method which intends to find an optimal solution. Then, we also present a sub-optimal Heuristic search with an admissible and Consistent Heuristic function which can remarkably improve the efficiency of the algorithm. Our experimental results demonstrate the effectiveness and efficiency of the proposed algorithms on several real datasets in the application domain of personal credit and banking.
-
Extracting optimal actionable plans from additive tree models
Frontiers of Computer Science, 2017Co-Authors: Qiang Lu, Zhicheng Cui, Yixin Chen, Xiaoping ChenAbstract:© 2017, Higher Education Press and Springer-Verlag Berlin Heidelberg.Although amazing progress has been made in machine learning to achieve high generalization accuracy and efficiency, there is still very limited work on deriving meaningful decision-making actions from the resulting models. However, in many applications such as advertisement, recommendation systems, social networks, customer relationship management, and clinical prediction, the users need not only accurate prediction, but also suggestions on actions to achieve a desirable goal (e.g., high ads hit rates) or avert an undesirable predicted result (e.g., clinical deterioration). Existing works for extracting such actionability are few and limited to simple models such as a decision tree. The dilemma is that those models with high accuracy are often more complex and harder to extract actionability from. In this paper, we propose an effective method to extract actionable knowledge from additive tree models (ATMs), one of the most widely used and best off-the-shelf classifiers. We rigorously formulate the optimal actionable planning (OAP) problem for a given ATM, which is to extract an actionable plan for a given input so that it can achieve a desirable output while maximizing the net profit. Based on a state space graph formulation, we first propose an optimal Heuristic search method which intends to find an optimal solution. Then, we also present a sub-optimal Heuristic search with an admissible and Consistent Heuristic function which can remarkably improve the efficiency of the algorithm. Our experimental results demonstrate the effectiveness and efficiency of the proposed algorithms on several real datasets in the application domain of personal credit and banking.
Jianhua Hu - One of the best experts on this subject based on the ideXlab platform.
-
A Multi-Heuristic A* Algorithm Based on Stagnation Detection for Path Planning of Manipulators in Cluttered Environments
IEEE Access, 2019Co-Authors: Kai Mi, Jun Zheng, Yunkuan Wang, Jianhua HuAbstract:We consider the problem of planning an obstacle avoidance path for manipulators in cluttered environments especially with narrow passages. Compared to sampling-based planners, Heuristic search-based planners are more suitable for such environments due to the Consistent Heuristic guidance. In order to solve the problem of search stagnation caused by inappropriate Heuristic guidance, we use the Shared Multi-Heuristic A* (SMHA*) algorithm and predefine multiple inadmissible Heuristics. Meanwhile, when the Consistent Heuristic guidance is correct and appropriate, in order to avoid the unnecessary inadmissible Heuristics to increase the search burden, we improve it by adding Heuristic-based stagnation detection for each extended node and the improved algorithm is called SD-SMHA*. Only when the algorithm detects that it ceases to make significant progress towards the goal, the predefined inadmissible Heuristics will be introduced. Finally, multiple simulation experiments are carried out and the results show that the improved algorithm effectively improves the planning efficiency and planning success rate in different scenarios.
Qiang Lu - One of the best experts on this subject based on the ideXlab platform.
-
Extracting optimal actionable plans from additive tree models
Frontiers of Computer Science in China, 2017Co-Authors: Qiang Lu, Yixin Chen, Xiaoping ChenAbstract:Although amazing progress has been made in machine learning to achieve high generalization accuracy and efficiency, there is still very limited work on deriving meaningful decision-making actions from the resulting models. However, in many applications such as advertisement, recommendation systems, social networks, customer relationship management, and clinical prediction, the users need not only accurate prediction, but also suggestions on actions to achieve a desirable goal (e.g., high ads hit rates) or avert an undesirable predicted result (e.g., clinical deterioration). Existing works for extracting such actionability are few and limited to simple models such as a decision tree. The dilemma is that those models with high accuracy are often more complex and harder to extract actionability from. In this paper, we propose an effective method to extract actionable knowledge from additive tree models (ATMs), one of the most widely used and best off-the-shelf classifiers. We rigorously formulate the optimal actionable planning (OAP) problem for a given ATM, which is to extract an actionable plan for a given input so that it can achieve a desirable output while maximizing the net profit. Based on a state space graph formulation, we first propose an optimal Heuristic search method which intends to find an optimal solution. Then, we also present a sub-optimal Heuristic search with an admissible and Consistent Heuristic function which can remarkably improve the efficiency of the algorithm. Our experimental results demonstrate the effectiveness and efficiency of the proposed algorithms on several real datasets in the application domain of personal credit and banking.
-
Extracting optimal actionable plans from additive tree models
Frontiers of Computer Science, 2017Co-Authors: Qiang Lu, Zhicheng Cui, Yixin Chen, Xiaoping ChenAbstract:© 2017, Higher Education Press and Springer-Verlag Berlin Heidelberg.Although amazing progress has been made in machine learning to achieve high generalization accuracy and efficiency, there is still very limited work on deriving meaningful decision-making actions from the resulting models. However, in many applications such as advertisement, recommendation systems, social networks, customer relationship management, and clinical prediction, the users need not only accurate prediction, but also suggestions on actions to achieve a desirable goal (e.g., high ads hit rates) or avert an undesirable predicted result (e.g., clinical deterioration). Existing works for extracting such actionability are few and limited to simple models such as a decision tree. The dilemma is that those models with high accuracy are often more complex and harder to extract actionability from. In this paper, we propose an effective method to extract actionable knowledge from additive tree models (ATMs), one of the most widely used and best off-the-shelf classifiers. We rigorously formulate the optimal actionable planning (OAP) problem for a given ATM, which is to extract an actionable plan for a given input so that it can achieve a desirable output while maximizing the net profit. Based on a state space graph formulation, we first propose an optimal Heuristic search method which intends to find an optimal solution. Then, we also present a sub-optimal Heuristic search with an admissible and Consistent Heuristic function which can remarkably improve the efficiency of the algorithm. Our experimental results demonstrate the effectiveness and efficiency of the proposed algorithms on several real datasets in the application domain of personal credit and banking.