Abstract
Most real-world Planning problems are multi-objective, trying to minimize both the makespan of the solution plan, and some cost of the actions involved in the plan. But most, if not all existing approaches are based on single-objective planners, and use an aggregation of the objectives to remain in the single-objective context. Divide-and-Evolve is an evolutionary planner that won the temporal deterministic satisficing track at the last International Planning Competitions (IPC). Like all Evolutionary Algorithms (EA), it can easily be turned into a Pareto-based Multi-Objective EA. It is however important to validate the resulting algorithm by comparing it with the aggregation approach: this is the goal of this paper. The comparative experiments on a recently proposed benchmark set that are reported here demonstrate the usefulness of going Pareto-based in AI Planning.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Ghallab, M., Nau, D., Traverso, P.: Automated Planning, Theory and Practice. Morgan Kaufmann (2004)
Kambhampati, S.: 1001 ways to skin a planning graph for heuristic fun and profit. Invited talk at ICAPS 2003 (2003)
Do, M., Kambhampati, S.: SAPA: A Multi-Objective Metric Temporal Planner. J. Artif. Intell. Res. (JAIR) 20, 155–194 (2003)
Refanidis, I., Vlahavas, I.: Multiobjective Heuristic State-Space Planning. Artificial Intelligence 145(1), 1–32 (2003)
Gerevini, A., Saetti, A., Serina, I.: An Approach to Efficient Planning with Numerical Fluents and Multi-Criteria Plan Quality. Artificial Intelligence 172(8-9), 899–944 (2008)
Gerevini, A., Long, D.: Preferences and Soft Constraints in PDDL3. In: ICAPS Workshop on Planning with Preferences and Soft Constraints, pp. 46–53 (2006)
Chen, Y., Wah, B., Hsu, C.: Temporal Planning using Subgoal Partitioning and Resolution in SGPlan. J. of Artificial Intelligence Research 26(1), 323–369 (2006)
Edelkamp, S., Kissmann, P.: Optimal Symbolic Planning with Action Costs and Preferences. In: Proc. 21st IJCAI, pp. 1690–1695 (2009)
Deb, K.: Multi-Objective Optimization Using Evolutionary Algorithms. John Wiley (2001)
Brie, A.H., Morignot, P.: Genetic Planning Using Variable Length Chromosomes. In: Biundo, S., Myers, K.L., Rajan, K. (eds.) 15th Intl Conf. on Automated Planning and Scheduling, pp. 320–329. AAAI Press (2005)
Schoenauer, M., Savéant, P., Vidal, V.: Divide-and-Evolve: A New Memetic Scheme for Domain-Independent Temporal Planning. In: Gottlieb, J., Raidl, G.R. (eds.) EvoCOP 2006. LNCS, vol. 3906, pp. 247–260. Springer, Heidelberg (2006)
Vidal, V., Geffner, H.: Branching and Pruning: An Optimal Temporal POCL Planner based on Constraint Programming. In: Proc. AAAI 2004, pp. 570–577 (2004)
Vidal, V.: A Lookahead Strategy for Heuristic Search Planning. In: Proceedings of the 14th ICAPS, pp. 150–159. AAAI Press (2004)
Bibai, J., Savéant, P., Schoenauer, M., Vidal, V.: On the Benefit of Sub-optimality within the Divide-and-Evolve Scheme. In: Cowling, P., Merz, P. (eds.) EvoCOP 2010. LNCS, vol. 6022, pp. 23–34. Springer, Heidelberg (2010)
Bibaï, J., Savéant, P., Schoenauer, M., Vidal, V.: An Evolutionary Metaheuristic Based on State Decomposition for Domain-Independent Satisficing Planning. In: Brafman, R., et al. (eds.) Proc. 20th ICAPS, pp. 18–25. AAAI Press (2010)
Khouadjia, M.R., Schoenauer, M., Vidal, V., Dréo, J., Savéant, P.: Multi-objective AI Planning: Evaluating DaE YAHSP on a Tunable Benchmark. In: Purshouse, R.C., Fleming, P.J., Fonseca, C.M., Greco, S., Shaw, J. (eds.) EMO 2013. LNCS, vol. 7811, pp. 36–50. Springer, Heidelberg (2013)
Hutter, F., Hoos, H.H., Leyton-Brown, K., Stützle, T.: ParamILS: an automatic algorithm configuration framework. J. Artif. Intell. Res. (JAIR) 36, 267–306 (2009)
Haslum, P., Geffner, H.: Admissible Heuristics for Optimal Planning. In: Proc. AIPS 2000, pp. 70–82 (2000)
Zitzler, E., Künzli, S.: Indicator-Based Selection in Multiobjective Search. In: Yao, X., Burke, E.K., Lozano, J.A., Smith, J., Merelo-Guervós, J.J., Bullinaria, J.A., Rowe, J.E., Tiňo, P., Kabán, A., Schwefel, H.-P. (eds.) PPSN VIII. LNCS, vol. 3242, pp. 832–842. Springer, Heidelberg (2004)
Jin, Y., Okabe, T., Sendhoff, B.: Adapting Weighted Aggregation for Multiobjective Evolution Strategies. In: Zitzler, E., Deb, K., Thiele, L., Coello Coello, C.A., Corne, D.W. (eds.) EMO 2001. LNCS, vol. 1993, pp. 96–110. Springer, Heidelberg (2001)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Khouadjia, M.R., Schoenauer, M., Vidal, V., Dréo, J., Savéant, P. (2013). Multi-objective AI Planning: Comparing Aggregation and Pareto Approaches. In: Middendorf, M., Blum, C. (eds) Evolutionary Computation in Combinatorial Optimization. EvoCOP 2013. Lecture Notes in Computer Science, vol 7832. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-37198-1_18
Download citation
DOI: https://doi.org/10.1007/978-3-642-37198-1_18
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-37197-4
Online ISBN: 978-3-642-37198-1
eBook Packages: Computer ScienceComputer Science (R0)