Domain-Dependent Heuristics and Tie-Breakers: Topics in Automated Planning
Resumo
Automated planning is an important general problem solving technique in Artificial Intelligence. Given an initial state, a goal and a set of operators, we want to find a sequence of operators leading us to the goal. What makes planning interesting is that it can model different domains into planning tasks and solve them using a single method. In this work, we approach two different topics in planning. First, we study heuristics for the airport ground traffic problem and propose new heuristics that are better than any other known method. In the second part, we study tie-breakers for the A∗ search algorithm. We propose a new tie-breaking method that is proved to be the best possible and also show that our methods solve more instances than previous methods in literature.
Referências
Bonet, B. and Geffner, H. (2001). Planning as heuristic search. Artificial Intelligence, 129(1-2):5–33.
Corrêa, A. B., Pereira, A. G., and Ritt, M. (2016). Improved airport ground traffic control with domain-dependent heuristics. In Brazilian Conference on Intelligent Systems, pages 73–78.
Corrêa, A. B., Pereira, A. G., and Ritt, M. (2018a). Analyzing tie-breaking strategies for the A* algorithm. In International Joint Conference on Artificial Intelligence.
Corrêa, A. B., Pereira, A. G., and Ritt, M. (2018b). Analyzing tie-breaking strategies for the A* algorithm. In Workshop on Heuristics and Search for Domain-independent Planning – International Conference on Automated Planning and Scheduling.
Dechter, R. and Pearl, J. (1985). Generalized best-first search strategies and the optimality of A*. Journal of the ACM, 32(3):505–536.
Gliesch, A. and Ritt, M. (2016). Solving atomix with pattern databases. In Brazilian Conference on Intelligent Systems, pages 61–66.
Hart, P. E., Nilsson, N. J., and Raphael, B. (1968). A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on Systems Science and Cybernetics, 4(2):100–107.
Haslum, P., Botea, A., Helmert, M., Bonet, B., and Koenig, S. (2007). Domain-independent construction of pattern database heuristics for cost-optimal planning. In AAAI Conference on Artificial Intelligene, pages 1007–1012.
Helmert, M. (2006a). The Fast Downward Planning System. Journal of Artificial Intelligence, 26:191–246.
Helmert, M. (2006b). New complexity results for classical planning benchmarks. In International Conference on Automated Planning and Scheduling, pages 52–62.
Helmert, M. and Domshlak, C. (2009). Landmarks, critical paths and abstractions: What’s the difference anyway? In International Conference on Automated Planning and Scheduling, pages 162–169.
Hoffmann, J. and Nebel, B. (2001). The FF planning system: Fast plan generation through heuristic search. Journal of Artificial Intelligence Research, 14:253–302.
Pereira, A. G., Ritt, M., and Buriol, L. S. (2015). Optimal sokoban solving using pattern databases with specific domain knowledge. Artificial Intelligence, 227:52–70.
Pereira, A. G., Ritt, M., and Buriol, L. S. (2016). Pull and PushPull are PSPACE-complete. Theoretical Computer Science, 628:50–61.
