The Experts below are selected from a list of 73113 Experts worldwide ranked by ideXlab platform
Hector Geffner - One of the best experts on this subject based on the ideXlab platform.
-
Heuristic Search for generalized stochastic shortest path mdps
International Conference on Automated Planning and Scheduling, 2011Co-Authors: Andrey Kolobov, Daniel S Weld, Hector GeffnerAbstract:ReSearch in efficient methods for solving infinite-horizon MDPs has so far concentrated primarily on discounted MDPs and the more general stochastic shortest path problems (SSPs). These are MDPs with 1) an optimal value function V* that is the unique solution of Bellman equation and 2) optimal policies that are the greedy policies w.r.t. V*. This paper's main contribution is the description of a new class of MDPs, that have well-defined optimal solutions that do not comply with either 1 or 2 above. We call our new class Generalized Stochastic Shortest Path (GSSP) problems. GSSP allows more general reward structure than SSP and subsumes several established MDP types including SSP, positive-bounded, negative, and discounted-reward models. While existing efficient Heuristic Search algorithms like LAO* and LRTDP are not guaranteed to converge to the optimal value function for GSSPs, we present a new Heuristic-Search-based family of algorithms, FRET (Find, Revise, Eliminate Traps). A preliminary empirical evaluation shows that FRET solves GSSPs much more efficiently than Value Iteration.
-
faster Heuristic Search algorithms for planning with uncertainty and full feedback
International Joint Conference on Artificial Intelligence, 2003Co-Authors: Blai Bonet, Hector GeffnerAbstract:Recent algorithms like RTDP and LAO* combine the strength of Heuristic Search (HS) and Dynamic Programming (DP) methods by exploiting knowledge of the initial state and an admissible Heuristic function for producing optimal policies without evaluating the entire space. In this paper, we introduce and analyze three new HS/DP algorithms. A first general algorithm schema that is a simple loop in which 'inconsistent' reachable states (i.e., with residuals greater than a given c) are found and updated until no such states are found, and serves to make explicit the basic idea underlying HS/DP algorithms, leaving other commitments aside. A second algorithm, that builds on the first and adds a labeling mechanism for detecting solved states based on Tarjan's strongly-connected components procedure, which is very competitive with existing approaches. And a third algorithm, that approximates the latter by enforcing the consistency of the value function over the likely' reachable states only, and leads to great time and memory savings, with no much apparent loss in quality, when transitions have probabilities that differ greatly in value.
-
planning as Heuristic Search
Artificial Intelligence, 2001Co-Authors: Blai Bonet, Hector GeffnerAbstract:In the AIPS98 Planning Contest, the HSP planner showed that Heuristic Search planners can be competitive with state-of-the-art Graphplan and SAT planners. Heuristic Search planners like HSP transform planning problems into problems of Heuristic Search by automatically extracting Heuristics from Strips encodings. They differ from specialized problem solvers such as those developed for the 24-Puzzle and Rubik’s Cube in that they use a general declarative language for stating problems and a general mechanism for extracting Heuristics from these representations. In this paper, we study a family of Heuristic Search planners that are based on a simple and general Heuristic that assumes that action preconditions are independent. The Heuristic is then used in the context of best-first and hill-climbing Search algorithms, and is tested over a large collection of domains. We then consider variations and extensions such as reversing the direction of the Search for speeding node evaluation, and extracting information about propositional invariants for avoiding dead-ends. We analyze the resulting planners, evaluate their performance, and explain when they do best. We also compare the performance of these planners with two state-of-the-art planners, and show that the simplest planner based on a pure best-first Search yields the most solid performance over a large set of problems. We also discuss the strengths and limitations of this approach, establish a correspondence between Heuristic Search planning and Graphplan, and briefly survey recent ideas that can reduce the current gap in performance between general Heuristic Search planners and specialized solvers. 2001 Elsevier Science B.V. All rights reserved.
-
planning with incomplete information as Heuristic Search in belief space
International Conference on Artificial Intelligence Planning Systems, 2000Co-Authors: Blai Bonet, Hector GeffnerAbstract:The formulation of planning as Heuristic Search with Heuristics derived from problem representations has turned out to be a fruitful approach for classical planning. In this paper, we pursue a similar idea in the context planning with incomplete information. Planning with incomplete information can be formulated as a problem of Search in belief space, where belief states can be either sets of states or more generally probability distribution over states. While the formulation (as the formulation of classical planning as Heuristic Search) is not particularly novel, the contribution of this paper is to make it explicit, to test it over a number of domains, and to extend it to tasks like planning with sensing where the standard Search algorithms do not apply. The resulting planner appears to be competitive with the most recent conformant and contingent planners (e.g., CGP, SGP, and CMBP) while at the same time is more general as it can handle probabilistic actions and sensing, different action costs, and epistemic goals.
-
planning as Heuristic Search new results
Lecture Notes in Computer Science, 1999Co-Authors: Blai Bonet, Hector GeffnerAbstract:In the recent AIPS98 Planning Competition, the hsp planner, based on a forward state Search and a domain-independent Heuristic, showed that Heuristic Search planners can be competitive with state of the art Graphplan and Satisfiability planners. hsp solved more problems than the other planners but it often took more time or produced longer plans. The main bottleneck in hsp is the computation of the Heuristic for every new state. This computation may take up to 85% of the processing time. In this paper, we present a solution to this problem that uses a simple change in the direction of the Search. The new planner, that we call hspr, is based on the same ideas and Heuristic as hsp , but Searches backward from the goal rather than forward from the initial state. This allows hspr to compute the Heuristic estimates only once. As a result, hspr can produce better plans, often in less time. For example, hspr solves each of the 30 logistics problems from Kautz and Selman in less than 3 seconds. This is two orders of magnitude faster than blackbox. At the same time, in almost all cases, the plans are substantially smaller. hspr is also more robust than hsp as it visits a larger number of states, makes deterministic decisions, and relies on a single adjustable parameter than can be fixed for most domains. hspr, however, is not better than hsp accross all domains and in particular, in the blocks world, hspr fails on some large instances that hsp can solve. We discuss also the relation between hspr and Graphplan, and argue that Graphplan can also be understood as a Heuristic Search planner with a precise Heuristic function and Search algorithm.
Eric A. Hansen - One of the best experts on this subject based on the ideXlab platform.
-
a Heuristic Search approach to planning with continuous resources in stochastic domains
arXiv: Artificial Intelligence, 2014Co-Authors: Nicolas Meuleau, Emmanuel Benazera, Ronen I Brafman, Eric A. HansenAbstract:We consider the problem of optimal planning in stochastic domains with resource constraints, where the resources are continuous and the choice of action at each step depends on resource availability. We introduce the HAO* algorithm, a generalization of the AO* algorithm that performs Search in a hybrid state space that is modeled using both discrete and continuous state variables, where the continuous variables represent monotonic resources. Like other Heuristic Search algorithms, HAO* leverages knowledge of the start state and an admissible Heuristic to focus computational effort on those parts of the state space that could be reached from the start state by following an optimal policy. We show that this approach is especially effective when resource constraints limit how much of the state space is reachable. Experimental results demonstrate its effectiveness in the domain that motivates our reSearch: automated planning for planetary exploration rovers.
-
anytime Heuristic Search
arXiv: Artificial Intelligence, 2011Co-Authors: Eric A. Hansen, Rong ZhouAbstract:We describe how to convert the Heuristic Search algorithm A* into an anytime algorithm that finds a sequence of improved solutions and eventually converges to an optimal solution. The approach we adopt uses weighted Heuristic Search to find an approximate solution quickly, and then continues the weighted Search to find improved solutions as well as to improve a bound on the suboptimality of the current solution. When the time available to solve a Search problem is limited or uncertain, this creates an anytime Heuristic Search algorithm that allows a flexible tradeoff between Search time and solution quality. We analyze the properties of the resulting Anytime A* algorithm, and consider its performance in three domains; sliding-tile puzzles, STRIPS planning, and multiple sequence alignment. To illustrate the generality of this approach, we also describe how to transform the memory-efficient Search algorithm Recursive Best-First Search (RBFS) into an anytime algorithm.
-
Breadth-first Heuristic Search
Artificial Intelligence, 2006Co-Authors: Rong Zhou, Eric A. HansenAbstract:AbstractRecent work shows that the memory requirements of A* and related graph-Search algorithms can be reduced substantially by only storing nodes that are on or near the Search frontier, using special techniques to prevent node regeneration, and recovering the solution path by a divide-and-conquer technique. When this approach is used to solve graph-Search problems with unit edge costs, we show that a breadth-first Search strategy can be more memory-efficient than a best-first strategy. We also show that a breadth-first strategy allows a technique for preventing node regeneration that is easier to implement and can be applied more widely. The breadth-first Heuristic Search algorithms introduced in this paper include a memory-efficient implementation of breadth-first branch-and-bound Search and a breadth-first iterative-deepening A* algorithm that is based on it. Computational results show that they outperform other systematic Search algorithms in solving a range of challenging graph-Search problems
-
KR - Breadth-first Heuristic Search
2004Co-Authors: Rong Zhou, Eric A. HansenAbstract:Recent work shows that the memory requirements of best-first Heuristic Search can be reduced substantially by using a divide-and-conquer method of solution reconstruction. We show that memory requirements can be reduced even further by using a breadth-first instead of a best-first Search strategy. We describe optimal and approximate breadth-first Heuristic Search algorithms that use divide-and-conquer solution reconstruction. Computational results show that they outperform other optimal and approximate Heuristic Search algorithms in solving domain-independent planning problems.
-
sweep a space efficient Heuristic Search in partially ordered graphs
International Conference on Tools with Artificial Intelligence, 2003Co-Authors: Rong Zhou, Eric A. HansenAbstract:We describe a novel Heuristic Search algorithm, called Sweep A*, that exploits the regular structure of partially ordered graphs to substantially reduce the memory requirements of Search. We show that it outperforms previous Search algorithms in optimally aligning multiple protein or DNA sequences, an important problem in bioinformatics. Sweep A* also promises to be effective for other Search problems with similar structure.
Antoni Guasch - One of the best experts on this subject based on the ideXlab platform.
-
deadlock free scheduling method for flexible manufacturing systems based on timed colored petri nets and anytime Heuristic Search
Systems Man and Cybernetics, 2015Co-Authors: Olatunde T Baruwa, Miquel Angel Piera, Antoni GuaschAbstract:This paper addresses the deadlock (DL)-free scheduling problem of flexible manufacturing systems (FMS) characterized by resource sharing, limited buffer capacity, routing flexibility, and the availability of material handling systems. The FMS scheduling problem is formulated using timed colored Petri net (TCPN) modeling where each operation has a certain number of preconditions, an estimated duration, and a set of postconditions. Based on the reachability analysis of TCPN modeling, we propose a new anytime Heuristic Search algorithm which finds optimal or near-optimal DL-free schedules with respect to makespan as the performance criterion. The methodology tackles the time-constrained problem of very demanding systems (high diversity production and make-to-order) in which computational time is a critical factor to produce optimal schedules that are DL-free. In such a rapidly changing environment and under tight customer due-dates, producing optimal schedules becomes intractable given the time limitations and the NP-hard nature of scheduling problems. The proposed anytime Search algorithm combines breadth-first iterative deepening A* with suboptimal breadth-first Heuristic Search and backtracking. It guarantees that the Search produces the best solution obtained so far within the allotted computation time and provides better solutions when given more time. The effectiveness of the approach is evaluated on a comprehensive benchmark set of DL-prone FMS examples and the computational results show the superiority of the proposed approach over the previous works.
Olatunde T Baruwa - One of the best experts on this subject based on the ideXlab platform.
-
deadlock free scheduling method for flexible manufacturing systems based on timed colored petri nets and anytime Heuristic Search
Systems Man and Cybernetics, 2015Co-Authors: Olatunde T Baruwa, Miquel Angel Piera, Antoni GuaschAbstract:This paper addresses the deadlock (DL)-free scheduling problem of flexible manufacturing systems (FMS) characterized by resource sharing, limited buffer capacity, routing flexibility, and the availability of material handling systems. The FMS scheduling problem is formulated using timed colored Petri net (TCPN) modeling where each operation has a certain number of preconditions, an estimated duration, and a set of postconditions. Based on the reachability analysis of TCPN modeling, we propose a new anytime Heuristic Search algorithm which finds optimal or near-optimal DL-free schedules with respect to makespan as the performance criterion. The methodology tackles the time-constrained problem of very demanding systems (high diversity production and make-to-order) in which computational time is a critical factor to produce optimal schedules that are DL-free. In such a rapidly changing environment and under tight customer due-dates, producing optimal schedules becomes intractable given the time limitations and the NP-hard nature of scheduling problems. The proposed anytime Search algorithm combines breadth-first iterative deepening A* with suboptimal breadth-first Heuristic Search and backtracking. It guarantees that the Search produces the best solution obtained so far within the allotted computation time and provides better solutions when given more time. The effectiveness of the approach is evaluated on a comprehensive benchmark set of DL-prone FMS examples and the computational results show the superiority of the proposed approach over the previous works.
-
anytime Heuristic Search for scheduling flexible manufacturing systems a timed colored petri net approach
The International Journal of Advanced Manufacturing Technology, 2014Co-Authors: Olatunde T Baruwa, Miquel Angel PieraAbstract:Given the fluctuations in demand, diversity in products, production flexibility requirements, and tight customer due dates, obtaining optimal production schedules is considered a complex reSearch problem. This can drastically affect the survival of some manufacturing companies in today’s fiercely competitive global market. In a very demanding decision-making environment, scheduling problems are dealt with in a short-term horizon, in which computation time is a critical factor. Producing optimal solutions is practically impossible given the time limitations and the nondeterministic polynomial (NP)-hard nature of scheduling problems. This paper presents an anytime-Heuristic Search approach based on a simulation-optimization framework that combines evaluation methods (simulation) and Search methods (optimization) through the reachability analysis (or state space) of timed colored Petri net models to schedule flexible manufacturing systems (FMS). The anytime Search algorithm is capable of finding a first suboptimal solution very quickly and continuously improves the solution quality over time. If given enough computation time, the algorithm eventually converges to an optimal solution. The proposed approach is aimed at obtaining optimal or near-optimal solutions to FMS scheduling problems in relatively short computation times with the objective of minimizing the makespan. Its effectiveness is highlighted with excellent results that outperform previous methods on benchmark examples with flexible material handling systems, machine, and routing configurations. The approach can also serve as a decision support tool to assist production schedulers that require rapid and almost real-time responses to time-critical production scheduling on the shop floor.
Nathan R. Sturtevant - One of the best experts on this subject based on the ideXlab platform.
-
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.
-
extended abstract an improved priority function for bidirectional Heuristic Search
Annual Symposium on Combinatorial Search, 2016Co-Authors: Guni Sharon, Robert C Holte, Ariel Felner, Nathan R. SturtevantAbstract:Bidirectional Search algorithms interleave a Search forward from the start state (start ) and a Search backward (i.e. using reverse operators) from the goal state (goal). We say that the two Searches “meet in the middle” if neither Search expands a node whose g-value (in the given direction) exceeds C*/2 , where C* is the cost of an optimal solution. The only bidirectional Heuristic Search algorithm that is guaranteed to meet in the middle under all circumstances is the recently introduced MM algorithm (Holte et al. 2016). The feature of MM that provides this guarantee is its unique priority functions for nodes on its open lists. In this short note we present MMe, which enhances MM’s priority function and is expected to expand fewer nodes than MM under most circumstances. We sketch a proof of MMe’s correctness, describe conditions under which MMe will expand fewer nodes than MM and vice versa, and experimentally compare MMe and MM on the 10-Pancake problem.
-
graph abstraction in real time Heuristic Search
Journal of Artificial Intelligence Research, 2007Co-Authors: Vadim Bulitko, Nathan R. Sturtevant, Timothy YauAbstract:Real-time Heuristic Search methods are used by situated agents in applications that require the amount of planning per move to be independent of the problem size. Such agents plan only a few actions at a time in a local Search space and avoid getting trapped in local minima by improving their Heuristic function over time. We extend a wide class of real-time Search algorithms with automatically-built state abstraction and prove completeness and convergence of the resulting family of algorithms. We then analyze the impact of abstraction in an extensive empirical study in real-time pathfinding. Abstraction is found to improve efficiency by providing better trading offs between planning time, learning speed and other negatively correlated performance measures.
