Landmark-based approaches for plan recognition tasks

Abstract

Técnicas de planejamento automático são eficientes no reconhecimento de objetivos e planos a partir da execução de ações e evidências incompletas. Para muitas aplicações é importante reconhecer objetivos e planos não somente acuradamente, mas também de maneira rápida e precisa. Assim, para lidar com esse desafio, desenvolvemos uma abordagem a qual utiliza uma heurística baseada em técnicas de planejamento automático, guiando-se por pontos-de-referência, que filtra possíveis objetivos e planos a partir de observações. Em planejamento automático, pontos-de-referência são propriedades (ou ações), em que todo o plano precisa alcançar (ou executar), em alguma determinada parte da execução do plano a fim de atingir um objetivo estipulado. Neste trabalho, formalizamos a tarefa de reconhecimento de objetivos e planos sem a utilização de biblioteca de planos, ou seja, utilizamos uma definição de domínio para planejamento automático. Sendo assim, estabelecemos o problema e o comportamento do agente a ser observado (ações e objetivos) utilizando uma linguagem de planejamento automático. A partir disso, mostramos a aplicabilidade da nossa abordagem baseada em técnicas de planejamento de três formas: (1) desenvolvendo uma heurística baseada em pontos-de-referencia para reconhecer objetivos e planos; (2) refinando uma abordagem existente para reconhecimento de planos; e for fim, (3) desenvolvendo uma abordagem para reconhecer abandono de planos.A abordagem para reconhecimento de abandono de planos desenvolvida tem como objetivo analisar uma seqüência de observações (ações), afim de detectar quais não contribuem para alcançar o objetivo o qual está sendo monitorado. Para fins de avaliação e experimentação, utilizou-se vários domínios de planejamento automático, e com isso, foi possível mostrar que nossa abordagem para reconhecimento de planos comporta-se acuradamente e rapidamente quando comparada com o estado-da-arte. Ainda, demonstramos que a nossa abordagem para detectar abandono de planos comporta-se com precisão e com baixo custo computacional, detectando precisamente ações que não contribuem para alcançar um determinado objetivo monitorado.

Recognition of goals and plans using incomplete evidence from action execution can be done efficiently by using automated planning techniques. In many applications it is important to recognize goals and plans not only accurately, but also quickly. In order to address this challenge, we develop recognition approaches based on planning techniques that rely on planning landmarks to filter candidate goals and plans from observations. In automated planning, landmarks are properties or actions that cannot be avoided to achieve a goal. We address the task of recognizing goals and plans without pre-defined static plan libraries, and instead we use a planning domain definition to represent the problem and the expected agent behavior. In this work, we show the applicability of planning techniques for recognition tasks in three settings: first, we use planning landmarks to develop a heuristic-based plan recognition approach; second, we refine an existing planningbased plan recognition approach; and finally, we use planning techniques to develop an approach for detecting plan abandonment. The plan abandonment detection approach we develop aims to analyze a sequence of observations and a monitored goal to determine if an observed agent is still pursuing, or has no intention to complete such monitored goal. These recognition approaches are evaluated in experiments over several planning domains. We show that our plan recognition approach yields not only accuracy comparable to other state-of-the-art techniques, but also substantially lower recognition time over such techniques. Furthermore, our plan abandonment detection approach yields high accuracy at low computational cost to detect which actions do not contribute for achieving a particular monitored goal.