Epistemic Planning

Have you seen the battle of the wits in The Princess Bride? In it, the criminial Vizzini is given a choice between two glasses of wine: one poisoned, one not. Vizzini spends the scene trying to outsmart the hero by using what he knows the hero knows that he knows that the hero knows that he knows that the hero knows... You get the idea. While Vizzini may not have been able to succeed in saving his life with epistemic logic, we can use it to help agents infer the belief states of others and act accordingly.

Vizzini: But it's so simple. All I have to do is divine from what I know of you: are you the sort of man who would put the poison into his own goblet or his enemy's? Now, a clever man would put the poison into his own goblet, because he would know that only a great fool would reach for what he was given. I am not a great fool, so I can clearly not choose the wine in front of you. But you must have known I was not a great fool, you would have counted on it, so I can clearly not choose the wine in front of me.

Dread Pirate Roberts: You've made your decision then?

Vizzini: Not remotely. Because iocane comes from Australia, as everyone knows, and Australia is entirely peopled with criminals, and criminals are used to having people not trust them, as you are not trusted by me, so I can clearly not choose the wine in front of you.

Dread Pirate Roberts: Truly, you have a dizzying intellect.

Vizzini: WAIT TILL I GET GOING! Where was I?

Dread Pirate Roberts: Australia.

Vizzini: Yes, Australia. And you must have suspected I would have known the powder's origin, so I can clearly not choose the wine in front of me.

...

For this lecture, we want to introduce the problem of epistemic planning with concrete examples paired with a detailed walkthrough of how current approaches attempt to model and solve this problem. We will cover the two main approaches: formulae-based epistemic planning and dynamic epistemic logic (DEL). Formulae-based approaches are simpler for users who already know classical (i.e. STRIPS) planning but only can be applied to a limited set of problems. We’ll cover the restricted perspectival multi-agent epistemic planning (RP-MEP) method in detail as an exemplar of this family of methods [1]. Second, we’ll cover a DEL-based method which has the capability to effectively and naturally express epistemic planning problems and solve complex epistemic scenarios by encoding the problem as a Kripke model and finding a plan with the epistemic forwards planner (EFP). Ultimately, our lecture will depict how approaches to solve epistemic planning can serve as a powerful tool in multi-agent scenarios where proactive assessment of actions based on an agent’s belief about other agents is highly important.

[1] Planning Over Multi-Agent Epistemic States: A Classical Planning Approach (Amended Version). Muise, C.; Belle, V.; Felli, P.; McIlraith, S. A.; Miller, T.; Pearce, A. R.; and Sonenberg, L. In Workshop on Distributed and Multi-Agent Planning (DMAP'15), 2015.