×

Phase transitions of EXPSPACE-complete problems: a further step. (English) Zbl 1246.68206

Summary: This paper further explores the phase transitions of the EXPSPACE-complete problems, focusing on the conformant plan modification. By analyzing features of the conformant plan modification, quantitative results are obtained. If the number of actions is not greater than \(\theta_{ub}\), almost all the conformant planning instances cannot be solved with the conformant plan modification. If the number of actions is not lower than \(\theta_{lb}\), almost all the conformant planning instances can be solved with the conformant plan modification. The results of the experiments show that there indeed exists an experimental threshold \(\gamma_c\) of density (ratio of number of actions to number of propositions), which separates the region where almost all conformant planning instances cannot be solved with the conformant plan modification from the region where almost all conformant planning instances can be solved with the conformant plan modification.

MSC:

68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] DOI: 10.1016/j.artint.2007.04.001 · Zbl 1168.68554 · doi:10.1016/j.artint.2007.04.001
[2] DOI: 10.1016/j.tcs.2006.01.001 · Zbl 1088.68163 · doi:10.1016/j.tcs.2006.01.001
[3] DOI: 10.1126/science.264.5163.1297 · Zbl 1226.68097 · doi:10.1126/science.264.5163.1297
[4] DOI: 10.1016/S0004-3702(96)00030-6 · Zbl 0907.68177 · doi:10.1016/S0004-3702(96)00030-6
[5] Xu Ke, Journal of Artificial Intelligence Research 12 pp 93–
[6] DOI: 10.1002/rsa.20015 · Zbl 1077.68118 · doi:10.1002/rsa.20015
[7] DOI: 10.1016/j.dam.2006.09.014 · Zbl 1123.68117 · doi:10.1016/j.dam.2006.09.014
[8] DOI: 10.1142/S012905411000774X · Zbl 1215.68162 · doi:10.1142/S012905411000774X
[9] Helmert M., Journal of Artificial Intelligence Research 26 pp 191– · JFM 01.0389.02
[10] Junping Zhou, Journal of Software 20 pp 290– · doi:10.3724/SP.J.1001.2009.00290
[11] Cormen T. H., Introduction to Algorithms (1990) · Zbl 1158.68538
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.