The Experts below are selected from a list of 35640 Experts worldwide ranked by ideXlab platform
David Maxwell Chickering - One of the best experts on this subject based on the ideXlab platform.
-
learning equivalence classes of bayesian network structures
Journal of Machine Learning Research, 2002Co-Authors: David Maxwell ChickeringAbstract:Two Bayesian-network structures are said to be equivalent if the set of distributions that can be represented with one of those structures is identical to the set of distributions that can be represented with the other. Many scoring criteria that are used to learn Bayesian-network structures from data are score equivalent; that is, these criteria do not distinguish among networks that are equivalent. In this paper, we consider using a score equivalent criterion in conjunction with a Heuristic Search Algorithm to perform model selection or model averaging. We argue that it is often appropriate to Search among equivalence classes of network structures as opposed to the more common approach of Searching among individual Bayesian-network structures. We describe a convenient graphical representation for an equivalence class of structures, and introduce a set of operators that can be applied to that representation by a Search Algorithm to move among equivalence classes. We show that our equivalence-class operators can be scored locally, and thus share the computational efficiency of traditional operators defined for individual structures. We show experimentally that a greedy model-selection Algorithm using our representation yields slightly higher-scoring structures than the traditional approach without any additional time overhead, and we argue that more sophisticated Search Algorithms are likely to benefit much more.
-
learning equivalence classes of bayesian network structures
Uncertainty in Artificial Intelligence, 1996Co-Authors: David Maxwell ChickeringAbstract:Approaches to learning Bayesian networks from data typically combine a scoring function with a Heuristic Search procedure. Given a Bayesian network structure, many of the scoring functions derived in the literature return a score for the entire equivalence class to which the structure belongs. When using such a scoring function, it is appropriate for the Heuristic Search Algorithm to Search over equivalence classes of Bayesian networks as opposed to individual structures. We present the general formulation of a Search space for which the states of the Search correspond to equivalence classes of structures. Using this space, any one of a number of Heuristic Search Algorithms can easily be applied. We compare greedy Search performance in the proposed Search space to greedy Search performance in a Search space for which the states correspond to individual Bayesian network structures.
Eric A. Hansen - One of the best experts on this subject based on the ideXlab platform.
-
solving pomdps by Searching in policy space
arXiv: Artificial Intelligence, 2013Co-Authors: Eric A. HansenAbstract:Most Algorithms for solving POMDPs iteratively improve a value function that implicitly represents a policy and are said to Search in value function space. This paper presents an approach to solving POMDPs that represents a policy explicitly as a finite-state controller and iteratively improves the controller by Search in policy space. Two related Algorithms illustrate this approach. The first is a policy iteration Algorithm that can outperform value iteration in solving infinitehorizon POMDPs. It provides the foundation for a new Heuristic Search Algorithm that promises further speedup by focusing computational effort on regions of the problem space that are reachable, or likely to be reached, from a start state.
-
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.
-
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.
-
LAO: a Heuristic Search Algorithm that finds solutions with loops
Artificial Intelligence, 2001Co-Authors: Eric A. Hansen, Shlomo ZilbersteinAbstract:Classic Heuristic Search Algorithms can find solutions that take the form of a simple path (A*), a tree, or an acyclic graph (AO*). In this paper, we describe a novel generalization of Heuristic Search, called LAO*, that can find solutions with loops. We show that LAO* can be used to solve Markov decision problems and that it shares the advantage Heuristic Search has over dynamic programming for other classes of problems. Given a start state, it can find an optimal solution without evaluating the entire state space. 2001 Elsevier Science B.V. All rights reserved.
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.
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.
P L Lee - One of the best experts on this subject based on the ideXlab platform.
-
petri net based formulation and Algorithm for short term scheduling of batch plants
Computers & Chemical Engineering, 2005Co-Authors: M Ghaeli, Parisa A Bahri, P L LeeAbstract:Effective scheduling of operations in batch plants has a great potential for high economic returns, in which the formulation and optimal solution Algorithm are the main issues of study. Petri-nets have proven to be a promising technique to solve many difficult problems associated with the modeling, formal analysis, design and coordination control of discrete event systems. One of the major advantages of using a Petri-net model is that the same model can be used for the analysis of behavioral properties and performance evaluation, as well as for the systematic construction of discrete event simulators and controllers. This paper aims to present a Petri-net based approach for the scheduling of operations in batch plants. Firstly, the short-term scheduling of batch plants is formulated using timed Petri-net. Secondly, the Heuristic Search Algorithm for scheduling of batch plants is given, which is based on generating and checking the markings in the reachability tree of the Petri-net model. Finally, the novel formulation and Algorithm are tested using two simulation case studies, and compared against traditional methods.
-
timed petri nets based scheduling for batch plants with the consideration of clean up operation
Bahri P.A. ORCID: 0000-0003-4661-5644 Gu T. and Lee P. (2001) Timed petri nets based scheduling for batch plants with the consideration of Clean-up op, 2001Co-Authors: Parisa A Bahri, P L LeeAbstract:In this paper, timed Petri nets-based approach is extended to deal with the scheduling problems of batch plants with the consideration of clean-up times. Firstly, timed Petri nets formulation approach is given, where two different categories of cleaning requirements, sequence dependent and frequency dependent, are considered. Different Petri net structures or sub-nets are presented respectively. Secondly, a Heuristic Search Algorithm for the optimal scheduling of batch plants with the consideration of clean-up times is presented. From the complete Petri net model of the batch plant obtained, the optimal schedule can be solved through Searching the reachability tree of the firing sequence of the transitions. Finally, the effectiveness of the proposed approach and Algorithm is illustrated through case studies.