Utilização de Heurísticas de Planejamento no desdobramento de redes de Petri

Abstract

Resumo: Diversos trabalhos envolvema relação existente entre os problemas de Planejamento Clássico e os problemas de alcançabilidade de redes de Petri, em virtude da proximidade existente entre estes dois formalismos. Uma das técnicas que produz melhores resultados na solução de problemas de alcançabilidade é conhecida como “Desdobramento”. A rede resultante do desdobramento possui omplexidade exponencial em relação ao tamanho inicial da rede de Petri, ainda que produza uma rede menor do que o tamanho do grafo de alcançabilidade de redes de Petri. O objetivo deste trabalho é adaptar as heurísticas de Planejamento H1 e H2, baseadas na regressão de um estado objetivo, para guiar o processo de desdobramento da rede de Petri até que seja atingida uma marcação objetivo, permitindo que a solução possa ser extraída da rede de ocorrências gerada. Esta adaptação foi feita a partir de uma estrutura de dados chamada de vetor de cálculo, que enumera as regressões de todos os subconjuntos de tamanho menor ou igual a m, de acordo com a ordem da heurística, permitindo algumas otimizações no cálculo da heurística. Resultados experimentais foram obtidos a partir de redes de Petri geradas a partir do planejador Petrigraph, que converte problemas de planejamento clássico descritos em forma PDDL em forma de redes de Petri. Estas redes foram submetidas ao desdobramento com auxílio das heurísticas H1 e H2, sendo os resultados comparados com a heurística implementada por Töws e com o planejador Sat Plan. Também foram feitas análises envolvendo o número de expansões realizadas até ser encontrada a solução, o trabalho total realizado pela ferramenta Mole, a complexidade do vetor de cálculo e a profundidade atingida nas redes em que a solução não foi encontrada.