Now showing 1 - 3 of 3
ItemNo Preview Available'Knowing Whether' in Proper Epistemic Knowledge BasesMiller, T ; Felli, P ; Muise, C ; Pearce, AR ; Sonenberg, L (AAAI Press, 2016)Proper epistemic knowledge bases (PEKBs) are syntactic knowledge bases that use multi-agent epistemic logic to represent nested multi-agent knowledge and belief. PEKBs have certain syntactic restrictions that lead to desirable computational properties; primarily, a PEKB is a conjunction of modal literals, and therefore contains no disjunction. Sound entailment can be checked in polynomial time, and is complete for a large set of arbitrary formulae in logics Kn and KDn. In this paper, we extend PEKBs to deal with a restricted form of disjunction: 'knowing whether.' An agent i knows whether Q iff agent i knows Q or knows not Q; that is, Q or not(Q). In our experience, the ability to represent that an agent knows whether something holds is useful in many multi-agent domains. We represent knowing whether with a modal operator, and present sound polynomial-time entailment algorithms on PEKBs with the knowing whether operator in Kn and KDn, but which are complete for a smaller class of queries than standard PEKBs.
ItemNo Preview AvailablePlanning for a Single Agent in a Multi-Agent Environment Using FONDMuise, C ; Felli, P ; Miller, T ; Pearce, AR ; Sonenberg, L ; Kambhampati, S (AAAI Press, 2016)Single-agent planning in a multi-agent environment is challenging because the actions of other agents can affect our ability to achieve a goal. From a given agent's perspective, actions of others can be viewed as non-deterministic outcomes of that agent's actions. While simple conceptually, this interpretation of planning in a multi-agent environment as non-deterministic planning remains challenging, not only due to the non-determinism resulting from others' actions, but because it is not clear how to compactly model the possible actions of others in the environment. In this paper, we cast the problem of planning in a multiagent environment as one of Fully-Observable Non-Deterministic (FOND) planning. We extend a non-deterministic planner to plan in a multi-agent setting, allowing non-deterministic planning technology to solve a new class of planning problems. To improve the efficiency in domains too large for solving optimally, we propose a technique to use the goals and possible actions of other agents to focus the search on a set of plausible actions. We evaluate our approach on existing and new multiagent benchmarks, demonstrating that modelling the other agents' goals improves the quality of the resulting solutions.