One of the claims of Automated Planning is the advantage of representing planning tasks in a high-level language where there is a correspondence between the real environment and the problem being modelled. However, under certain circumstances some representations can be inefficient because they contain objects with irrelevant identities. Instead of forcing the designer to envision efficient alternatives, we propose an automatic compilation that recognises such problems and translates them into an alternative representation. In this representation, objects with irrelevant names are aggregated and their properties are encoded as counters. This class of problems is of special interest in environments where objects are created by domain actions and the names assigned to these new objects are not relevant for solving the task. The experimental results show that our compilation can reduce the size of the instantiation and the branching factor, resulting in an important improvement of the scalability of planners.
C.Backstrom and B.Nebel, Complexity results for SAS+ planning, Computational Intelligence11(4) (1995), 625–655.
2.
B.Bonet, P.Haslum, S.Hickmott and S.Thiébaux, Planning via Petri net unfolding: Generalisation and improvements, in: Proceedings of the International Conference on Automated Planning and Scheduling (ICAPS), 2007.
3.
A.Botea, M.Enzenberger, M.Müller and J.Schaeffer, Macro-ff: Improving AI planning with automatically learned macro-operators, Journal of Artificial Intelligence Research (JAIR)24 (2005), 581–621.
4.
T.Bylander, The computational complexity of propositional strips planning, Artificial Intelligence (AI)69(1,2) (1994), 165–204.
5.
L.Chrpa and T.L.McCluskey, On exploiting structures of classical planning problems: Generalizing entanglements, in: Proceedings of the ECAI, Frontiers in Artificial Intelligence and Applications, Vol. 242, IOS Press, 2012, pp. 240–245.
6.
R.Dechter, Constraint Processing, Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 2003.
7.
C.Domshlak, M.Katz and A.Shleyfman, Enhanced symmetry breaking in cost-optimal planning as forward search, in: Proceedings of the International Conference on Automated Planning and Scheduling (ICAPS), L.McCluskey, B.Williams, J.R.Silva and B.Bonet, eds, 2012.
8.
M.Fox and D.Long, The automatic inference of state invariants in tim, Journal of Artificial Intelligence Research (JAIR)9 (1998), 317–371.
9.
M.Fox and D.Long, The detection and exploitation of symmetry in planning problems, in: Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), 1999.
10.
M.Fox and D.Long, Extending the exploitation of symmetries in planning, in: Proceedings of the Artificial Intelligence Planning Systems Conference (AIPS), M.Ghallab, J.Hertzberg and P.Traverso, eds, AAAI, 2002, pp. 83–91.
11.
S.Gay, F.Fages, T.Martinez, S.Soliman and C.Solnon, On the subgraph epimorphism problem, Discrete Applied Mathematics162 (2014), 214–228.
12.
H.Geffner, Functional strips: A more flexible language for planning and problem solving, in: Logic-Based Artificial Intelligence, Kluwer, 2000.
13.
P.Haslum, Reducing accidental complexity in planning problems, in: Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), M.Veloso, ed., 2007, pp. 1898–1903.
14.
P.Haslum, M.Helmert and A.Jonsson, Safe, strong, and tractable relevance analysis for planning, in: Proceedings of the 23rd International Conference on Automated Planning and Scheduling (ICAPS), 2013.
15.
P.Haslum and U.Scholz, Domain knowledge in planning: Representation and use, in: Proceedings of the ICAPS 2003 Workshop on PDDL, 2003.
16.
M.Helmert, A planning heuristic based on causal graph analysis, in: Proceedings of the 14th International Conference on Automated Planning and Scheduling (ICAPS), 2004, pp. 161–170.
17.
M.Helmert, The Fast Downward planning system, Journal of Artificial Intelligence Research (JAIR)26 (2006), 191–246.
18.
M.Helmert, Changes in PDDL 3.1, unpublished summary from the IPC-2008 website, 2008, available at: http://ipc.informatik.uni-freiburg.de/PddlExtension.
M.Helmert, P.Haslum, J.Hoffmann and R.Nissim, Merge-and-shrink abstraction: A method for generating lower bounds in factored state spaces, Journal of the ACM61(3) (2014), 16.
21.
S.Hickmott, J.Rintanen, S.Thiébaux and L.White, Planning via Petri net unfolding, in: Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), 2007.
22.
J.Hoffmann, The metric-ff planning system: Translating “ignoring delete lists” to numeric state variables, Journal of Artificial Intelligence Research (JAIR)20 (2003), 291–341.
23.
J.Hoffmann and B.Nebel, The ff planning system: Fast plan generation through heuristic search, Journal of Artificial Intelligence Research (JAIR)14 (2001), 253–302.
24.
T.H.Jones and I.-Y.Song, Binary equivalents of ternary relationships in entity-relationship modeling: A logical decomposition approach, Journal of Database Management (JDM)11(2) (2000), 12–19.
25.
E.Keyder and H.Geffner, Soft goals can be compiled away, Journal of Artificial Intelligence Research (JAIR)36 (2009), 547–556.
26.
J.Koehler and J.Hoffmann, Handling of inertia in planning systems, in: ECAI-2000 Workshop on New Trends in Planning, Scheduling and Design, 2000.
D.Long, M.Fox and M.Hamdi, Reformulation in planning, in: Proceedings of the 5th International Symposium on Abstraction, Reformulation, and Approximation (SARA), Lecture Notes in Artificial Intelligence, Vol. 2371, Springer, 2002, pp. 18–32.
29.
B.Nebel, Y.Dimopoulos and J.Koehler, Ignoring irrelevant facts and operators in plan generation, in: Proceedings of the European Conference on Planning (ECP), 1997, pp. 338–350.
30.
N.Pochter, A.Zohar and J.Rosenschein, Exploiting problem symmetries in state-based planners, in: Proceedings of the AAAI Conference on Artificial Intelligence, 2011.
31.
S.Richter, M.Helmert and M.Westphal, Landmarks revisited, in: Proceedings of the 23rd AAAI Conference on Artificial Intelligence, 2008, pp. 975–982.
32.
S.Richter and M.Westphal, The lama planner: Guiding cost-based anytime planning with landmarks, Journal of Artificial Intelligence Research (JAIR)39 (2010), 127–177.
33.
P.J.Riddle, R.C.Holte and M.W.Barley, Does representation matter in the planning competition? in: Proceedings of the Symposium on Abstraction, Reformulation and Approximation (SARA), M.R.Genesereth and P.Z.Revesz, eds, AAAI, 2011.
34.
K.Talamadupula, J.Benton, S.Kambhampati, P.Schermerhorn and M.Scheutz, Planning for human–robot teaming in open worlds, ACM Transactions on Intelligent Systems and Technology (TIST)1(2) (2010), 14.
35.
N.Vikas, Computational complexity of compactions, Simon Fraser University, 1997.
