Plan Library in Plan Recognition
Plan recognition is the activity of inferring an agents intention by observing their actions. This inference relies on matching observed actions with previously defined plans which reside in a Plan Library. So, when doing plan recognition you need a solid plan library to identify users’ intentions. Let’s discuss what a plan library is and how to build one, especially in access control.
In general, plan library is a list of knows plans of a knows domain. Let’s think about egg dishes again as a domain. If we do a plan recognition in egg dishes domain we need to define all possible or likely egg dishes. If you do it for network security and intrusion detection then you need to define their likely plans.
Everything is a goal
In most published plan recognition work plan library is defined as a single rooted reverse tree with end goals being the top nodes. A goal can be reached by some mandatory and optional actions and there may more ways then one to reach a goal. For example adding herbs to your scrambled egg is up to you but you need to scramble it, hence the name. Every goal consists of sub-plans. Sub-plans are also plans and you can see them repeat in some cases employed by different super-plans.
If you want to develop a plan recognition system for egg dishes you need to build a plan library for egg dishes. To be complete as possible you may start with a web search for known egg dishes and study recipes. After some work you may come up with a universal plan library as complete as possible assuming there should be a finite list of egg dishes.
On the other hand there’s no global plan library for an access control environment because plan library of an access control will have routes from gates to gates as plans and every layout will have their own unique routes which makes it impossible to reuse as a universal library. Every layout needs it’s own library.
Before discussing how to build this plan library for access control I would like to express some of the criteria we defined before developing our own. When developing for the security domain you need to access that things change rapidly and operators don’t like updating systems accordingly. That means you need to aim for the least management overhead. So we decided the less meta data the better.
Metadata and data
What kind of meta data do we have? We know names of gates, may it be a number or some declarative name. Data also contains direction, in or out. This much is necessary for the access control system. There may also rights and zones and further details but none of them are mandatory so we decided we cannot rely on them and we should stick to door name and direction as metadata. Second criteria said that library must be personal, meaning plans must belong to specific users as their personal patterns. Later we may match patterns between users to identify unknown plans but that’s another story.
Since we have personal access data building a personalized plan library won’t be a problem. This data also contains door names and direction so we had to figure out how to build patterns of routes. When you look at a layout you will realize there are passages and rooms. Passages let you pass through hence the name. Rooms you enter and exit. We made an assumption that we would regularly use one single door to enter and exit a room. So when there are subsequent scans from same door with different directions as in and out, we may well assume this is a room which a user entered and then exited. So, that’s a room. A room is a goal because this is end of some route.
A room is also an origin because this is where a user starts their journey. So, a room out to room in path is a route. Now we need to find repeating paths in data and their ratio to all path occurrences to define a route’s probability.
A room or a passage
To find rooms we realized we only need to know two steps in a row. What happened before and what will happen after won’t effect this relationship, or we can say that future states do not depend on past states. That reminds us of famous Russian mathematician Андрей Андреевич Марков, or Andrey Markov as we know him. Markov is widely known for his model which should help us defining relation between every step in our data.
Since we are only interested in a single step for each state we have created a Markov chain, or a Markov Model of first order. This gives us every possible next step for any step with probabilities. If these are same door with in and out then we have room. Starting from every room in data and we follow the chain until a further room then we have a route.
A Markov chain produces state transition in a single state machine because there are no differences in states. But we have defined rooms and goals and origins including main entrance and exits and we need routes or specific state models between these steps or states. To get there we have employed a recursive function to generate state transition matrix between rooms.
Although Markov chain gave us probabilities of next steps probability of a route depends of the occurrence of that very route over all instances. When defining all routes it’s just a matter of some division and you will have all routes and their probabilities.
Whenever we have all routes and probabilities for a specific user then we have plan library. Apparently we also met our two criteria we set in the beginning. Every time we process new data we will have an updated library which also gives us the opportunity to develop a continuous learning environment.
Now since we have way to build our plan library and recognition methods we defined in previous posts let’s discuss how we build a plan recognition solution for access control, again in next episode.