The generation of route descriptions is a fundamental task of navigation systems. A particular problem in this context is to identify routes that can easily be described and processed by users. In this work, we present a framework for representing route networks with the qualitative information necessary to evaluate and optimize route descriptions with regard to ambiguities in them. We identify different agent models that differ in how agents are assumed to process route descriptions while navigating through route networks. Further, we analyze the computational complexity of matching route descriptions and paths in route networks in dependency of the agent model. Finally we empirically evaluate the influence of the agent model on the optimization and the processing of route instructions.

The Game Description Language is a high-level, rule-based formalisms for communicating the rules of arbitrary  games to general game-playing systems, whose challenging task is to learn to play previously unknown games without human intervention. Originally designed for deterministic games with complete information about the game state, the language was recently extended to include randomness and imperfect information. However, determining the extent to which this enhancement allows to describe truly arbitrary games was left as an open problem. We provide a positive answer to this question by relating the extended Game Description Language to the universal, mathematical concept of extensive-form games, proving that indeed just any such game can be described faithfully.

The paper introduces a logical framework for negotiation among dishonest agents. The framework relies on the use of abductive logic programming as a knowledge representation language for agents to deal with incomplete information and preferences. The paper shows how intentionally false or inaccurate information of agents could be encoded in the agents' knowledge bases. Such disinformation can be effectively used in the process of negotiation to have desired outcomes by agents. The negotiation processes are formulated under the answer set semantics of abductive logic programming and enable the exploration of various strategies that agents can employ in their negotiation

Let us explain our motivations for studying the logic of fuzzy belief and common belief. It is not so unusual that one We formalize reasoning about fuzzy belief and believes something to some degree, or the degree of one's fuzzy common belief, especially incomparable beliefs, belief may be neither 0 nor 1. The notion of fuzzy belief is in multi-agent systems by using a logical system appropriate in such a case. Moreover, the notion of fuzzy based on Fitting's many-valued modal logic, common belief can be appropriate even in a case where any where incomparable beliefs mean beliefs whose degrees agent of a group does not have a fuzzy belief. To see this, are not totally ordered. Completeness and consider the following question. Is there anything that all the decidability results for the logic of fuzzy belief people in the world believe? Strictly speaking, there may be and common belief are established while implicitly no such thing as a common belief among all the people in the exploiting the duality-theoretic perspective on Fitting's world. Even if so, there may be something that most of the logic that builds upon the author's previous people in the world believe.

Proving that one language is more succinct than another becomes harder when the underlying semantics is stronger. We propose to use Formula-Size Games (as put forward by Adler and Immerman, 2003), games that are played on two sets of models, and that directly link the length of play with the size of the formula. Using those games, we prove three succinctness results for m-dimensional modal logic: (1) In system K m , a notion of `everybody knows' makes the resulting language exponentially more succinct for m > 1, (2) In S5, the same language becomes more succinct for m > 3 and (3) Public Announcement Logic is exponentially more succinct than S5m, if m > 3. The latter settles an open problem raised by Lutz, 2006.

We define an extension of stit logic that encompasses subjective probabilities representing beliefs about simultaneous choice exertion of other agents. The formalism enables us to express the notion of "attempt" as a choice exertion that maximizes the chance of success with respect to an action effect. The notion of attempt (or effort) is central in philosophical and legal discussions on responsibility and liability.

We present a formal investigation of artifact-based systems, a relatively novel framework in service oriented computing, aimed at laying the foundations for verifying these systems through model checking. We present an infinite-state, computationally grounded semantics for these systems that allows us to reason about temporal-epistemic specifications. We present abstraction techniques for the semantics that guarantee transfer of satisfaction from the abstract system to the concrete one.

Problems that require multiple agents to follow non-interfering paths from their current states to their respective goal states are called cooperative pathfinding problems. We present the first {complete algorithm for finding these paths that is sufficiently fast for real-time applications. Furthermore, our algorithm offers a trade-off between running time and solution quality. We then refine our algorithm into an anytime algorithm that first quickly finds a solution, and then uses any remaining time to incrementally improve that solution until it is optimal or the algorithm is terminated. We compare our algorithms to those in the literature and show that in addition to completeness, our algorithms offer improved solution quality as well as competitive running time.

We address the problem of optimal path finding for multiple agents where agents must not collide and their total travel cost should be minimized. Previous work used traditional single-agent search variants of the A* algorithm. We present a novel formalization for this problem which includes a search tree called the increasing cost tree (ICT) and a corresponding search algorithm that finds optimal solutions. We analyze this new formalization and compare it to the previous state-of-the-art A*-based approach. Experimental results on various domains show the benefits and drawbacks of this approach. A speedup of up to 3 orders of magnitude was obtained in a number of cases.

ADOPT and BnB-ADOPT are two optimal DCOP search algorithms that are similar except for their search strategies: the former uses best-first search and the latter uses depth-first branch-and-bound search. In this paper, we present a new algorithm, called ADOPT( k ), that generalizes them. Its behavior depends on the k parameter. It behaves like ADOPT when k = 1, like BnB-ADOPT when k = ∞ and like a hybrid of ADOPT and BnB-ADOPT when 1 < k < ∞. We prove that ADOPT( k ) is a correct and complete algorithm and experimentally show that ADOPT( k ) outperforms ADOPT and BnB-ADOPT on several benchmarks across several metrics.