Publicação: Planejamento baseado em busca e aprendizagem
Carregando...
Tipo do documento
Data
Direito de acesso
Área do conhecimento
CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO
Título da Revista
ISSN da Revista
Título de Volume
Orientador
Coorientador
Resumo
Durante décadas, vários sistemas de planejamento vêm sendo propostos a m de encontrar
soluções para os mais diversos problemas do dia-a-dia. Porém, apenas recentemente,
sistemas de planejamento começaram a obter resultados satisfatórios através de métodos
de busca para construir seus planos. Como exemplo de planejador de sucesso, pode-se citar
o sistema Fast Forward que combina a execução de dois métodos de busca, o Enforced
Hill Climbing e o Best First Search. Técnicas introduzidas pelo Fast Forward tem sido
também aplicadas em muitos outros planejadores mais recentes.
Apesar da estratégia do Fast Forward apresentar um desempenho superior quando
comparado a outros métodos, ela também mostra algumas fragilidades. Para alguns
problemas de planejamento, o Enforced Hill Climbing não consegue escapar de máximos/
mínimos locais, o que o leva a car preso em becos sem saída, fazendo com que ele
falhe. Caso isso ocorra, uma busca completa é realizada pelo Best First Search, que pode
falhar por falta de espaço de memória. Note que esses problemas podem afetar qualquer
algoritmo de busca.
Este trabalho descreve o desenvolvimento de um planejador, chamado de SLPlan,
baseado em versões otimizadas dos algoritmos Enforced Hill Climbing e Learning Real-
Time A* que tentam reduzir o impacto dos problemas descritos acima para construir
planos de forma mais eciente.
Além disso, a aplicação de técnicas de planejamento na solução de problemas relevantes
é tema de especial interesse pela comunidade de planejamento. A geração de processos
de negócio (workow) é uma das áreas que podem se beneciar do uso de planejamento.
Nesta dissertação especica-se também como o planejador desenvolvido foi aplicado na
geração automática de modelos de processos de negócio.
Abstract
For decades, several planning systems have been proposed in order to nd solutions to
many of the dierent problems encountered in everyday life. However, only in recent years,
have planning systems started to obtain satisfactory results through the use of search
methods for building plans. As a successful planner, Fast Forward combines the execution
of two search methods, Enforced Hill Climbing and Best First Search. Techniques
introduced by Fast Forward have also been applied in many other recent planners.
Although Fast Forward strategy presents an enhanced performance when compared
to alternative methods, it shows some weaknesses. For some planning problems Enforced
Hill Climbing cannot escape from local maxima/minima, which means it might get stuck
at dead ends, thus leading to a failure. In the event of such occurrences, a complete search
is performed by Best First Search, which may fail due to lack of memory space. Note that
these troubles could aect any search algorithm.
This paper describes the development of a planner, called SLPlan, based on optmized
versions of the algorithms Enforced Hill Climbing and Learning Real-Time A* that aim
to reduce the impact of the troubles cited before in order to build plans more eciently.
Besides, the application of planning techniques in solving relevant problems is of particular
concern for the planning community. The generation of business processes ( work-
ow) is one of the areas that can benet from the use of planning. This dissertation
also species how SLPlan was applied to the automatic generation of business processes
models.
Palavras-chave
Sistemas de planejamento, Fast forward, Enforced hill climbing, Best first search, Learning real-time a*, Planning systems, Inteligência artificial
Citação
ALVES, Raulcézar Maximiano Figueira. Planejamento baseado em busca e aprendizagem. 2014. 122 f. Dissertação (Mestrado em Ciências Exatas e da Terra) - Universidade Federal de Uberlândia, Uberlândia, 2014. DOI https://doi.org/10.14393/ufu.di.2014.30