×

zbMATH — the first resource for mathematics

Experimental evaluation of pheromone models in ACOPlan. (English) Zbl 1253.68294
Summary: In this paper the system ACOPlan for planning with non uniform action cost is introduced and analyzed. ACOPlan is a planner based on the ant colony optimization framework, in which a colony of planning ants searches for near optimal solution plans with respect to an overall plan cost metric. This approach is motivated by the strong similarity between the process used by artificial ants to build solutions and the methods used by state-based planners to search solution plans. Planning ants perform a stochastic and heuristic based search by interacting through a pheromone model. The proposed heuristic and pheromone models are presented and compared through systematic experiments on benchmark planning domains. Experiments are also provided to compare the quality of ACOPlan solution plans with respect to state of the art satisficing planners. The analysis of the results confirm the good performance of the action-action pheromone model and points out the promising performance of the novel fuzzy-level-action pheromone model. The analysis also suggests general principles for designing performant pheromone models for planning and further extensions of ACOPlan to other optimization models.
MSC:
68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
68T05 Learning and adaptive systems in artificial intelligence
68W20 Randomized algorithms
68W25 Approximation algorithms
Software:
Walksat; SAPA; Graphplan; LPG
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Bacchus, F., Kabanza, F.: Using temporal logics to express search control knowledge for planning. Artif. Intell. 116, 123–191 (2000) · Zbl 0939.68827
[2] Baioletti, M., Milani, A., Poggioni, V., Rossi, F.: An ACO approach to planning. In: Proceedings of the 9th European Conference on Evolutionary Computation in Combinatorial Optimisation, EVOCOP 2009 (2009)
[3] Baioletti, M., Milani, A., Poggioni, V., Rossi, F.: Ant search strategies for planning optimization. In: Proceedings of the International Conference on Planning and Scheduling, ICAPS 2009 (2009)
[4] Baioletti, M., Milani, A., Poggioni, V., Rossi, F.: Optimal planning with ACO. In: Proceedings of AI*IA 2009. LNCS, vol. 5883, pp. 212–221 (2009)
[5] Baioletti, M., Milani, A., Poggioni, V., Rossi, F.: PlACO: Planning with Ants. In: Proceedings of The 22nd International FLAIRS Conference. AAAI (2009)
[6] Blum, A., Furst, M.: Fast planning through planning graph analysis. Artif. Intell. 90, 281–300 (1997) · Zbl 1017.68533
[7] Blum, C.: Ant colony optimization: introduction and recent trends. Physics of Life Reviews 2(4), 353–373 (2005)
[8] Bonet, B., Geffner, H.: Planning as heuristic search. Artif. Intell. 129(1–2), 5–33 (2001) · Zbl 0971.68146
[9] Bylander, T.: The computational complexity of propositional strips planning. Artif. Intell. 69 (1–2), 165–204 (1994) · Zbl 0821.68065
[10] Cialdea, M., Limongelli, C., Poggioni, V., Orlandini, A.: Linear temporal logic as an executable semantics for planning languages. J. Logic, Lang. Inf. 16, 63–89 (2007) · Zbl 1159.68562
[11] Conover, W.: Practical Nonparametric Statistics. John Wiley & Sons (1999)
[12] Do, M.B., Kambhampati, S.: Sapa: a multi-objective metric temporal planner. J. Artif. Intell. Res. (JAIR) 20, 155–194 (2003) · Zbl 1036.68091
[13] Dorigo, M., Stuetzle, T.: Ant Colony Optimization. MIT Press, Cambridge, MA, USA (2004) · Zbl 1092.90066
[14] Edelkamp, S., Kissmann, P.: Gamer: bridging planning and general game playing with symbolic search. In: Proceedings of IPC-6 Competition (2008)
[15] Garcia, M.P., Oscar Montiel, O.C., Sepulveda, R., Melin, P.: Path planning for autonomous mobile robot navigation with ant colony optimization and fuzzy cost function evaluation. Appl. Soft Comput. 9, 1102–1110 (2008) · Zbl 05739179
[16] Gerevini, A., Serina, I.: LPG: a planner based on local search for planning graphs. In: Proceedings of the 6th International Conference on Artificial Intelligence Planning and Scheduling (AIPS’02). AAAI Press, Toulouse, France (2002) · Zbl 1038.90551
[17] Helmert, M.: The fast downward planning system. J. Artif. Intell. Res. (JAIR). 26, 191–246 (2006) · Zbl 1182.68245
[18] Helmert, M., Do, M., Refanidis, I.: International Planning Competition IPC-2008. The Deterministic Part. http://ipc.icaps-conference.org/ (2008)
[19] Hoffmann, J., Nebel, B.: The FF planning system: fast plan generation through heuristic search. J. Artif. Intell. Res. (JAIR) 14, 253–302 (2001) · Zbl 0970.68044
[20] Kautz, H., McAllester, D., Selman, B.: Encoding plans in propositional logic. In: Proceedings of KR-96, Cambridge, Massachusetts, USA (1996)
[21] Kautz, H., Selman, B.: Unifying sat-based and graph-based planning. In: Proceedings of IJCAI-99, Stockholm (1999)
[22] Keyder, E., Geffner, H.: Heuristics for planning with action costs revisited. In: Proceedings of ECAI 2008, pp. 588–592 (2008)
[23] Menkes van den Briel, T.V., Kambhampati, S.: Loosely coupled formulations for automated planning: an integer programming perspective. J. Artif. Intell. Res. (JAIR) 31, 217–257 (2007) · Zbl 1175.90058
[24] Nau, D., Ghallab, M., Traverso, P.: Automated Planning: Theory and Practice. Morgan Kaufmann (2004) · Zbl 1074.68613
[25] Richter, S., Westphal, M.: The lama planner using landmark counting in heuristic search. In: Proc. of IPC-6 Competition (2008)
[26] Rossi, F.: An aco approach to planning. Ph.D. thesis, Mathematics and Computer Science Dept., University of Perugia, Italy (2009)
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.