Publicado em: 19/04/2018
Artigo é aceito no IJCAI 2018
O artigo do aluno Augusto Corrêa, com orientação dos Profs. André Grahl e Marcus Ritt, é aceito na conferência mais importante na área de inteligência artificial.
O artigo “Analyzing Tie-Breaking Strategies for the A* Algorithm” do aluno Augusto Corrêa, que acabou de terminar a graduação no INF e atualmente é mestrando na Universidade da Basileia, com orientação dos professores do PPGC André Grahl e Marcus Ritt, foi aceito na IJCAI 2018 (International Joint Conference on Artificial Intelligence).
A IJCAI é a conferência mais importante na área de inteligência artificial e este ano está na sua 27ª edição. Ao todo, o evento teve 3480 artigos submetidos e uma taxa de aceitação em 20%, o que dá enorme satisfação à comunidade acadêmica do Instituto de Informática e encoraja outros alunos e seguirem nesse campo de pesquisa.
Confira abaixo mais detalhes do artigo de Augusto Corrêa.
Título: “Analyzing Tie-Breaking Strategies for the A* Algorithm”
Resumo: For a given state space and admissible heuristic function h there is alwaysa tie-breaking strategy for which A* expands the minimum number of states [Dechter and Pearl, 1985]. We say that these strategies have optimal expansion. Although such a strategy always exists it may depend on the instance, and we currently do not know a tiebreaker that always guarantees optimal expansion. In this paper, we study tie-breaking strategies for A*. We analyze common strategies from the literature and prove that they do not have optimal expansion. We propose a novel tie-breaking strategy using cost adaptation and an optimal strategy based on this new idea. We experimentally analyze the performance of A* using several tie-breaking strategies on domains from the IPC and zero-cost domains. Our best strategy solves 152 instances more than the standard method in the literature and 19 more than the previous state-of-the-art strategy. Our analysis improves the understanding of how to develop effective tie-breaking strategies and our results also improve the state-of-the-art of tie-breaking strategies for A*.