A Symbolic Exploration of the Joint State Space and the Underlying Argumentation-based Reasoning Processes for Multiagent Planning

Coming up with coherent behaviors for a team of agents in a non-deterministic environment is a complex process. The problem is further complicated by information regarding the environment being defeasible---new information will disqualify the old information---while at the same time this information is distributed, uncertain and possibly inconsistent.;In this dissertation, I propose an approach based on symbolic model checking techniques to implicitly explore the state space of a system of agents to form a coherent set of joint behaviors for the agents with uncertainty captured as non-deterministism in the state space. The exploration process is based on individual agents' defeasible factored information about the dynamic of the state space towards a set of possibly inconsistent goals. This process can be interpreted using an argumentation-based approach. The exploration of the state space and the argumentation-based reasoning processes are carried out by a sequence of logical operations in the logic of Quantified Boolean Formulae (QBFs) and its model representation---Binary Decision Diagrams (BDDs). All the algorithms to carry out these processes can be computed with a polynomial number of QBF operations in terms of the number of inputs and the number of boolean variables in the domain. Although general symbolic solving QBFs and BDDs is PSPACE complete, the practices of QBF solvers and BDD implementations allow us to employ various techniques and application-specific heuristics to solve a number of applications. In summary, the approaches proposed in this dissertation provide a formal system and implementation techniques to integrate non-monotonic reasoning and non-deterministic planning into defeasible multiagent decentralized planning so that coherent behaviors can be formed for a system of agents in a very demanding setting where the information regarding the environment and goals regarding what to do are distributed, incomplete, possibly inconsistent and uncertain.