Home /Introduction to Plan Recognition

Introduction to Plan Recognition

As discussed in our previous blog post we needed a way to find out users’ suspicious behavior from access control actions, eg. scanning their cards to open a door or enter a room and we also need to separate random out-of-pattern behavior from a malicious plan – which is not that easy.

Our approach to this problem in a nutshell is observing user action to spot out-of-pattern behavior and score them to put in a severity row before alerting operators. If we would have an intelligent scoring algorithm it would help us separate random anomalies from malicious plans.

This approach is in fact a well known approach in a specific artificial intelligence domain called the “Plan Recognition”. Let’s talk a little bit about it.

AI seems to be a very recent topic. It’s very popular nowadays mostly because of some (very valuable) hardware improvements but it’s quiet a seasoned research topic. Until these recent days researches shed sweat to move inch by inch on this tough road of AI.

As one of the specialized sub topics of machine learning, Plan Recognition collected some attention and many published work for the last fifty years but it was Henry Kautz and James Allen from University of Rochester who set solid foundations of Plan Recognition with their paper titled as “Generalized Plan Recognition” in 1986. Most of the work published later follow their approach.

Plan recognition is the act of inferring an agents plans by observing their actions. To those who are not familiar with the method may think observing an agents actions may reveal all their plans. How can you tell where a person would go by just observing they left house with a luggage, yet alone their intentions?

In fact you can’t. Plan recognition is not a generalized solution to foretell any intent, it rather reasons observed actions “by constructing a plan that contains those actions”. In general, plan recognition relies on a list of prescribed plans bound to domain. If your domain is egg dishes then plans would cover omelette, scrambled, poached etc – eventually list of possible egg dishes must end somewhere. Even in more complex scenarios list of top level goals are finite and describable.

So, we can define plan recognition as matching an agent’s observed actions to prescribed plans. If it doesn’t then we have an out-of-plan case which is in fact what we were looking for when we started using in access control, an anomaly that doesn’t fit to user’s habits or patterns (doesn’t it sound cooler?).

Well it sounds easy, doesn’t it? In fact it would be, if everything would go as planned. Just like in every aspect of life plan recognition has it’s own issues as well.

There’s this order issue for example. Plan says break the eggs, scramble and pour in pan. This is a somewhat set order, meaning you can’t scramble before you break the eggs. But when it comes to mushrooms omelette the order of putting ingredients to pan may vary without changing the main goal, cooking an omelette. That means any well defined plan recognition algorithm must be able to handle ordinal requirements.

There are further issues in plan recognition. Multiple plans an agent may follow, abandon plans, or missing evidence are some of them. Some of the algorithm are quite well developed for some of these issues. We also had to consider these special cases when we developed our own algorithm for access control.

For example we need to deal with intervened plans. A user sets on the road for a destination. You observe actions and evidence hints to some probable goals but user changes her course just because she got a call from a colleague to stop by while on the way. This last action is not part of her usual pattern, she’s out of pattern but she may soon return.

When and if she returns we need to anticipate that she’s moving on with her previous plan. She may also never return to this plan, then this would be an abandon plan. Why is this important? If we think she abandons a plan then we need to find out the next plan she will take. If she returns to her previous plan, we must see that this is not a new plan which starts in the middle (kind-a odd, isn’t it) but an intervened one.

Sorry if it gets messy, if we hadn’t these issues.  Eventually we managed to develop an algorithm that deals with all these anomalies but before that we need to discuss the plan library in upcoming episode.

 

About the author

kozsu