Abstract
In state space search or planning, a pair of variable-value assignments that does not occur in any reachable state is considered a mutually exclusive (mutex) pair. To improve the efficiency of planners, the problem of detecting such pairs has been addressed frequently in the planning literature. No known efficient method for detecting mutex pairs is able to find all such pairs. Hence, the number and type of mutex constraints detected by various algorithms are different from one another.
The purpose of this paper is to study the effects on search performance when errors are made by the mutex detection method that is informing the construction of a pattern database (PDB). PDBs are deployed for creating heuristic functions that are then used to guide search. We consider two mutex detection methods, h 2, which can fail to recognize a mutex pair but never regards a reachable pair as mutex, and the sampling-based method MMM, which makes the opposite type of error. Both methods are very often perfect, i.e. they exactly identify which pairs are mutex and which are reachable. In the cases that they err that we examine in this paper, h 2’s errors cause search to be moderately slower (7% −24%) whereas MMM’s errors have very little effect on search speed or suboptimality, even when its sample size is quite small.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Berend, D., Kontorovich, A.: The missing mass problem. Stat. and Prob. Lett. 82, 1102–1110 (2012)
Blum, A.L., Furst, M.L.: Fast planning through planning graph analysis. Artif. Intell. 90(1), 1636–1642 (1995)
Bonet, B., Geffner, H.: Planning as heuristic search: New results. In: Biundo, S., Fox, M. (eds.) ECP 1999. LNCS (LNAI), vol. 1809, pp. 360–372. Springer, Heidelberg (2000)
Chen, Y., Huang, R., **ng, Z., Zhang, W.: Long-distance mutual exclusion for planning. Artif. Intell. 173(2), 365–391 (2009)
Culberson, J., Schaeffer, J.: Pattern databases. Comput. Intell. 14(3), 318–334 (1998)
Edelkamp, S., Helmert, M.: MIPS: The Model-Checking Integrated Planning System. AI Magazine 22(3), 67–72 (2001)
Fox, M., Long, D.: The automatic inference of state invariants in TIM. J. Artif. Intell. Res. 9, 367–421 (1998)
Gerevini, A., Saetti, A., Serina, I.: Planning through stochastic local search and temporal action graphs in lpg. J. Artif. Int. Res. 20, 239–290 (2003)
Gerevini, A., Schubert, L.K.: Discovering state constraints in DISCOPLAN: Some new results. In: AAAI/IAAI, pp. 761–767 (2000)
Gerevini, A., Schubert, L.: Inferring state constraints for domain-independent planning. In: AAAI/IAAI, pp. 905–912 (1998)
Harris, L.R.: The heuristic search under conditions of error. Artificial Intelligence 5(3), 217–234 (1974)
Haslum, P.: Admissible Heuristics for Automated Planning. Linkö** Studies in Science and Technology: Dissertations. Dept. of Computer and Information Science, Linkö** Univ. (2006)
Haslum, P., Bonet, B., Geffner, H.: New admissible heuristics for domain-independent planning. In: AAAI, pp. 1163–1168 (2005)
Helmert, M.: The Fast Downward planning system. J. Artif. Intell. Res. 26, 191–246 (2006)
Helmert, M., Lasinger, H.: The Scanalyzer domain: Greenhouse logistics as a planning problem. In: ICAPS, pp. 234–237 (2010)
Hernádvölgyi, I., Holte, R.: PSVN: A vector representation for production systems. Technical Report TR-99-04, Dept. of Computer Science, Univ. of Ottawa (1999)
Kautz, H.: SATPLAN04: Planning as satisfiability. In: 4th International Planning Competition Booklet (2004)
Kautz, H., Selman, B.: Pushing the envelope: Planning, propositional logic, and stochastic search, pp. 1194–1201. AAAI Press (1996)
Penberthy, J., Weld, D.: Temporal planning with continuous change. In: AAAI, pp. 1010–1015 (1994)
Rintanen, J.: An iterative algorithm for synthesizing invariants. In: AAAI/IAAI, pp. 806–811 (2000)
Sadeqi, M., Holte, R.C., Zilles, S.: Detecting mutex pairs in state spaces by sampling. In: Cranefield, S., Nayak, A. (eds.) AI 2013. LNCS (LNAI), vol. 8272, pp. 490–501. Springer, Heidelberg (2013)
Sadeqi, M., Holte, R.C., Zilles, S.: Using coarse state space abstractions to detect mutex pairs. In: SARA, pp. 104–111 (2013)
Scholz, U.: Extracting state constraints from PDDL-like planning domains. In: AIPS Workshop on Analyzing and Exploiting Domain Knowledge for Efficient Planning, pp. 43–48 (2000)
Vidal, V., Geffner, H.: Branching and pruning: An optimal temporal pocl planner based on constraint programming. Artif. Intell. 170, 298–335 (2006)
Zilles, S., Holte, R.C.: The computational complexity of avoiding spurious states in state space abstraction. Artif. Intell. 174, 1072–1092 (2010)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Sadeqi, M., Holte, R.C., Zilles, S. (2014). A Comparison of h 2 and MMM for Mutex Pair Detection Applied to Pattern Databases. In: Sokolova, M., van Beek, P. (eds) Advances in Artificial Intelligence. Canadian AI 2014. Lecture Notes in Computer Science(), vol 8436. Springer, Cham. https://doi.org/10.1007/978-3-319-06483-3_20
Download citation
DOI: https://doi.org/10.1007/978-3-319-06483-3_20
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-06482-6
Online ISBN: 978-3-319-06483-3
eBook Packages: Computer ScienceComputer Science (R0)