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

Abstract

Resumo: Diversos trabalhos envolvem a 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 complexidade 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 H¹ e H², 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 H¹ e H², 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.

Abstract: Many works involve the relation between the problems of Classical Planning and reachability in Petri nets, due the proximity existing between these two formalisms. One of the techniques that produce better results in the reachability solution is known as "unfolding". The resulting net from the unfolding process has size exponentially bigger than the size of the initial net, though this net is smaller than the size of the reachability graph. This work aims to adapt the planning heuristics H¹ and H², based on the regression from a goal state, to guide the construction of the unfolding until the goal mark can be reached, allowing that the solution can be extracted from the occurrence net generated. The adaptation was done through a data structure called vector calculus, which enumerates all the subsets with size smaller or equals to m, according the heuristic order, allowing some optimizations in the heuristic calculus. Experimental results were obtained from Petri nets generated from the planner Petrigraph, which converts classic planning problems from the format PDDL to Petri Nets. These nets were submited to unfolding using the heuristics H¹ and H², and the results were compared with the heuristic implemented by Tows and with the planner SatPlan. Besides, analysis were made involving the number of expansions done until the solution be found, the work realized by the tool Mole, the complexity from the vector calculus and the depth reached by the nets where the solution was not found.