×

Calculating criticalities. (English) Zbl 0906.68138

Summary: We present a novel method for building Abstrips style abstraction hierarchies in planning. The aim of this method is to minimize search by limiting backtracking both between abstraction levels and within an abstraction level. Previous approaches for building Abstrips style abstractions have determined the criticality of operator preconditions by reasoning about plans directly. Here, we adopt a simpler and faster approach where we use numerical simulation of the planning process. We develop a simple but powerful theory to demonstrate the theoretical advantages of our approach. We use this theory to identify some simple properties lacking in previous approaches but possessed by our method. We demonstrate the empirical advantages of our approach by a set of four benchmark experiments using the Abtweak system. We compare the quality of the abstraction hierarchies generated with those built by the Alpine and Highpoint algorithms.

MSC:

68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)

Keywords:

planning
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bacchus, F.; Yang, Q., Downward refinement and the efficiency of hierarchical problem solving, Artif. Intell., 71, 43-100 (1994) · Zbl 0938.68829
[2] Bäckström, C.; Jonsson, P., Planning with abstractions hierarchies can be exponentially less efficient, (Proceedings IJCAI-95. Proceedings IJCAI-95, Montreal, Que. (1995)), 1599-1604
[3] Bundy, A.; Giunchiglia, F.; Sebastiani, R.; Walsh, T., Computing abstraction hierarchies by numerical simulation, (Proceedings AAAI-96. Proceedings AAAI-96, Portland, OR (1996))
[4] Chapman, D., Planning for conjunctive goals, Artif. Intell., 32, 333-377 (1987) · Zbl 0642.68171
[5] Giunchiglia, F., Using abstrips abstractions—where do we stand?, (IRST-Technical Report (1996), IRST: IRST Trento)
[6] Giunchiglia, F.; Walsh, T., Using abstraction, (Proceedings 8th Conference of the Society for the Study of Artificial Intelligence and Simulation of Behaviour. Proceedings 8th Conference of the Society for the Study of Artificial Intelligence and Simulation of Behaviour, Leeds (1991))
[7] also: IRST-Technical Report 9010-08, IRST, Trento; also: IRST-Technical Report 9010-08, IRST, Trento
[8] also: DAI Research Paper 515, University of Edinburgh, Edinburgh.; also: DAI Research Paper 515, University of Edinburgh, Edinburgh.
[9] Giunchiglia, F.; Walsh, T., A theory of abstraction, Artif. Intell., 56, 323-390 (1992) · Zbl 0762.68054
[10] also: IRST-Technical Report 9001-14, IRST, Trento.; also: IRST-Technical Report 9001-14, IRST, Trento.
[11] Green, C., Application of theorem proving to problem solving, (Proceedings IJCAI-69. Proceedings IJCAI-69, Washington, DC (1969)), 219-239
[12] Knoblock, C. A., Abstracting the Tower of Hanoi, (Working Notes of AAAI-90 Workshop on Automatic Generation of Approximations and Abstractions (1990)), 13-23
[13] Knoblock, C. A., Automatically generating abstractions for planning, Artif. Intell., 68, 243-302 (1994) · Zbl 0942.68712
[14] Peot, M. A.; Smith, D. A., Threat-removal strategies for partial-order planning, (Proceedings AAAI-93. Proceedings AAAI-93, Washington, DC (1993))
[15] Sacerdoti, E. D., Planning in a hierarchy of abstraction spaces, (Proceedings IJCAI-73. Proceedings IJCAI-73, Stanford, CA (1973)) · Zbl 0288.68052
[16] Smith, D. E.; Peot, M. A., A critical look at Knoblock’s hierarchy mechanism, (Proceedings 1st International Conference on Artificial Intelligence Planning Systems (1992)), 307-308
[17] Yang, Q.; Tenenberg, J.; Woods, S., On the implementation and evaluation of Abtweak, Comput. Intell., 12 (1996)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.