Executive Summary : | Automated planning is a widely studied area of research in Artificial Intelligence (AI) with a wide variety of applications in robotics, control of autonomous agents, healthcare and information retrieval. Classical planning, often used in robotics, analyses the actions of a single agent interacting with a possibly non-deterministic environment to achieve reachability goals. Given the widespread use of autonomous agents, many real world applications now involve interactions between multiple such agents. The role of these autonomous agents vary based on the application domain and mostly involve interaction with humans at the higher level. For instance, in health care, where agents are deployed to assist elderly and in tutoring systems for students, the agents have cooperative objectives. In defense applications when deployed in conflict zones, agents might be under the control of multiple entities and their goals would involve both cooperative and conflicting objectives. In all of these instances, the agents work in a distributed setting and an important consequence is that they have imperfect information about the global state of the system. Imperfect information in turn implies that the knowledge and belief states of the agents would be different. In many practical multi-agent applications achieving goals would involve reasoning about agents' epistemic states. In this project we propose a framework to reason about such distributed multi-agent systems. Unlike in existing work where agents' information partitions are defined at the global level, we explicitly model knowledge acquisition through communication actions. We analyse various communication primitives and study the verification and plan synthesis problem where agents' goals can involve a combination of specifications that make assertions about the temporal evolution of the system as well as the associated epistemic states. We carry out a thorough algorithmic analysis of the planning problem in this framework and also aim to develop tools and heuristics which work well on practical instances. The execution of this project involves combining tools and techniques from various areas of mathematical science and computer science, including theoretical computer science (distributed protocols, knowledge representation/reasoning, mathematical logic, automata theory), mathematical economics (game theory) and formal methods. |