Foundations of a logic of knowledge, action, and communication

Candidate: Morgenstern,Leora

Abstract

Most Artificial Intelligence planners work on the assumption that they have complete knowledge of their problem domain and situation, so that planning an action consists of searching for an action sequence that achieves some desired goal. In actual planning situations, agents rarely know enough to map out a detailed plan of action when they start out. Instead, they initially draw up a sketchy plan and fill in details as they proceed. This thesis presents a formalism that is expressive enough to describe this flexible planning process. We address ourselves to two central issues: (1) How can an agent determine that he knows enough to do an action? (Knowledge Preconditions Problem) (2) If the agent does not know enough, how can he plan to get the action done? (Ignorant Agent Problem) We demonstrate that modal logic is too weak to serve as the basis for such a theory, and choose instead to work within a first order logic augmented with quotation. We then discuss the Knower Paradoxes that arise from such syntactic treatments of knowledge, and propose a solution to these paradoxes based on Kripke's solution to the Liar Paradox. Next, we present a theory of action and planning that is powerful enough to describe partial plans and joint-effort plans. We then explain what knowledge an agent must have in order to successfully perform an action and how an ignorant agent can construct and execute complex plans in order to overcome his ignorance. A central observation underlying our solution to the Ignorant Agent Problem is that ignorant agents tend to use communicative acts, such as asking for information, and delegating, to plan around their ignorance. During the final part of this thesis, we therefore develop a theory of communication as an integrated part of our theory of action and planning. We show that this theory of communication is more expressive than standard Austinian-type speech act theories. The thesis includes comparisons of our theory with other syntactic and modal theories such as Konolige's and Moore's. We demonstrate that our theory is powerful enough to solve classes of problems that these theories cannot handle.