By Craig A. Knoblock
Generating Abstraction Hierarchies offers a totally computerized method of producing abstractions for challenge fixing. The abstractions are generated utilizing a tractable, domain-independent set of rules whose merely inputs are the definition of an issue house and the matter to be solved and whose output is an abstraction hierarchy that's adapted to the actual challenge. The set of rules generates abstraction hierarchies that fulfill the `ordered monotonicity' estate, which promises that the constitution of an summary resolution isn't replaced within the means of refining it. An abstraction hierarchy with this estate permits an issue to be decomposed such that the answer in an summary area should be held invariant whereas the remainder elements of an issue are solved. The set of rules for producing abstractions is carried out in a approach known as ALPINE, which generates abstractions for a hierarchical model of the PRODIGY challenge solver. Generating Abstraction Hierarchies officially defines this hierarchical challenge fixing procedure, indicates that below convinced assumptions this system can decrease the dimensions of a seek area from exponential to linear within the answer measurement, and describes the implementation of this system in PRODIGY. The abstractions generated via ALPINE are established in a number of domain names on huge challenge units and are proven to supply shorter suggestions with considerably much less seek than challenge fixing with no utilizing abstraction. Generating Abstraction Hierarchies can be of curiosity to researchers in computer studying, making plans and challenge reformation.
Read or Download Generating Abstraction Hierarchies: An Automated Approach to Reducing Search in Planning PDF
Similar international books
Overseas Federation for info ProcessingThe IFIP sequence publishes cutting-edge ends up in the sciences and applied sciences of data and conversation. The scope of the sequence contains: foundations of desktop technology; software program concept and perform; schooling; computing device purposes in expertise; communique structures; platforms modeling and optimization; details structures; desktops and society; computers expertise; safety and defense in info processing structures; man made intelligence; and human-computer interplay.
Nuclear physics is almost immediately experiencing a thrust in the direction of basic phy sics questions. Low-energy experiments assist in checking out past brand new stan dard types of particle physics. the quest for finite neutrino lots and neutrino oscillations, for proton decay, infrequent and forbidden muon and pion de cays, for an electrical dipole second of the neutron denote a few of the efforts to check brand new theories of grand unification (GUTs, SUSYs, Superstrings, .
- Discourse, Interaction and Communication: Proceedings of the Fourth International Colloquium on Cognitive Science (ICCS-95)
- In Vitro Effects of Mineral Dusts: Third International Workshop
- Advanced Nonlinear Strategies for Vibration Mitigation and System Identification (CISM International Centre for Mechanical Sciences) (Volume 518)
- Fundamentals of International Transfer Pricing in Law and Economics
- Turbellarian Biology: Proceedings of the Sixth International Symposium on the Biology of the Turbellaria, held at Hirosaki, Japan, 7–12 August 1990
- Web Information Systems and Mining: International Conference, WISM 2012, Chengdu, China, October 26-28, 2012. Proceedings
Extra info for Generating Abstraction Hierarchies: An Automated Approach to Reducing Search in Planning
Example text
2. The ratio between the levels is the base of the logarithm. If the number of steps at a given level is n, then the number of steps at the next level is 2n + 1. Thus, the base of the logarithm is 2, and the ratio between the levels is 0(2). 3. The problem is decomposed into subproblems that are all of equal size. These subproblems are effectively all of size one, since each subproblem requires inserting one additional step. 4. Using an admissible search strategy, the hierarchical problem solver produces the shortest solution for the given problem.
Shows the conditions remaining after removing the smallest disk, and level 2 shows the conditions after removing both the smallest and medium-sized disks. 3. Abstractions of an Initial State, Goal, and Operator The abstraction hierarchy for the Tower of Hanoi can be used for hierarchical problem solving. The first step is to map the initial problem into the corresponding abstract problems. 8, where the initial and goal states are mapped into initial and goal states at each level of abstraction.
Since each disk can be moved from one of two places, the branching factor is two. Thus, the size of each subproblem is 21 = 2, so the entire search is bounded by 21, which is 0(1). Consequently, hierarchical problem solving reduces the search space in this domain from O(b') to 0(1). 5 Hierarchical Problem Solving in PRODIGY This section describes an extended version of PRODIGY that performs hierarchical problem solving. The extensions to PRODIGY are straightforward and are based on the formalization of hierarchical problem solving described earlier in this chapter.