Authors:Ofri Keidar; Noa Agmon Pages: 121 - 164 Abstract: This work deals with the problem of navigation while avoiding detection by a mobile adversary, featuring adversarial modeling. In this problem, an evading agent is placed on a graph, where one or more nodes are defined as safehouses. The agent’s goal is to find a path from its current location to a safehouse, while minimizing the probability of meeting a mobile adversarial agent at a node along its path (i.e., being captured). We examine several models of this problem, where each one has different assumptions on what the agents know about their opponent, all using a framework for computing node utility, introduced herein. Using risk attitudes for computing the utility values, their impact on the constructed strategies is analyzed both theoretically and empirically. Furthermore, we allow the agents to use information gained along their movement, in order to efficiently update their motion strategies on-the-fly. Theoretical and empirical analysis shows the importance of using this information and these on-the-fly strategy updates. PubDate: 2018-06-01 DOI: 10.1007/s10472-018-9591-0 Issue No:Vol. 83, No. 2 (2018)

Authors:Imen Zghidi; Brahim Hnich; Abdelwaheb Rebai Pages: 165 - 181 Abstract: In this paper, we propose a novel notion of statistical consistency for single-stage Stochastic Constraint Satisfaction Problems (SCSPs) in which some of the random variables’ support set is infinite. The essence of this novel notion of local consistency is to be able to make an inference in the presence of infinite scenarios in an uncertain environment. This inference would be based on a restricted finite subset of scenarios with a certain confidence level and a threshold tolerance error. The confidence level is the probability that characterizes the extend to which our inference — based on a subset of scenarios — is correct. The threshold tolerance error is the error range that we can tolerate while making such an inference. We propose a novel statistical consistency enforcing algorithm that is based on sound statistical inference; and experimentally show how to prune inconsistent values in the presence of an infinite set of scenarios. PubDate: 2018-06-01 DOI: 10.1007/s10472-018-9572-3 Issue No:Vol. 83, No. 2 (2018)

Authors:Wafa Jguirim; Wady Naanaa; Martin C. Cooper Pages: 1 - 20 Abstract: Finding a solution to a constraint satisfaction problem (CSP) is known to be an NP-hard task. Considerable effort has been spent on identifying tractable classes of CSP, in other words, classes of constraint satisfaction problems for which there are polynomial time recognition and resolution algorithms. In this article, we present a relational tractable class of binary CSP. Our key contribution is a new ternary operation that we name mjx. We first characterize mjx-closed relations which leads to an optimal algorithm to recognize such relations. To reduce space and time complexity, we define a new storage technique for these relations which reduces the complexity of establishing a form of strong directional path consistency, the consistency level that solves all instances of the proposed class (and, indeed, of all relational classes closed under a majority polymorphism). PubDate: 2018-05-01 DOI: 10.1007/s10472-017-9566-6 Issue No:Vol. 83, No. 1 (2018)

Authors:Tobias Ahlbrecht; Jürgen Dix; Niklas Fiekas Abstract: We present the twelfth edition of the Multi-Agent Programming Contest (https://multiagentcontest.org), an annual, community-serving competition that attracts groups from all over the world. Our contest facilitates comparison of multi-agent systems and provides a concrete problem that is interesting in itself and well-suited to be tackled in educational environments. This time, seven teams competed using strictly agent-based as well as traditional programming approaches. PubDate: 2018-07-10 DOI: 10.1007/s10472-018-9594-x

Authors:Ioannis Kokkinis Abstract: Let L be some extension of classical propositional logic. The non-iterated probabilistic logic over L is the logic PL that is defined by adding non-nested probabilistic operators in the language of L. For example, in PL we can express a statement like “the probability of truthfulness of A is at least 0.3” where A is a formula of L. The iterated probabilistic logic over L is the logic PPL, where the probabilistic operators may be iterated (nested). For example, in PPL we can express a statement like “this coin is counterfeit with probability 0.6”. In this paper we investigate the influence of probabilistic operators in the complexity of satisfiability in PL and PPL. We obtain complexity bounds, for the aforementioned satisfiability problem, which are parameterized in the complexity of satisfiability of conjunctions of positive and negative formulas that have neither a probabilistic nor a classical operator as a top-connective. As an application of our results we obtain tight complexity bounds for the satisfiability problem in PL and PPL when L is classical propositional logic or justification logic. PubDate: 2018-07-06 DOI: 10.1007/s10472-018-9593-y

Authors:Zuoquan Lin; Chen Chen Abstract: In nonmonotonic reasoning there are the problems of inconsistency and incoherence in general, and in default reasoning there may be only one trivial extension or no extension in special. We propose the restricted semantics of four-valued logic for default reasoning to resolve the problems of inconsistency and incoherence and in the meantime retain classical extensions in the presence of consistency and coherency. The restricted semantics can maintain both the expressiveness and reasoning ability of default logic. We provide a transformation approach to compute the restricted extensions by reducing them into classical ones. PubDate: 2018-06-18 DOI: 10.1007/s10472-018-9592-z

Authors:Jonathan Pieper Abstract: This paper describes the team BusyBeaver, that participated in and won the Multi-Agent Programming Contest 2017. Its strategy is based on dividing agents into three static groups modeling the work chain of buying, assembling and delivering items. The team is coordinated by a centralized agent doing most of the high-level planning, usually using greedy algorithms and specialized heuristics. There is a heavy focus on proactively buying and assembling some items, in order to quickly complete upcoming jobs. PubDate: 2018-06-09 DOI: 10.1007/s10472-018-9589-7

Authors:Z. Kovács; T. Recio; C. Sólyom-Gecse Abstract: We present an algorithm to help converting expressions having non-negative quantities (like distances) in Euclidean geometry theorems to be usable in a complex algebraic geometry prover. The algorithm helps in refining the output of an existing prover, therefore it supports immediate deployment in high level prover systems. We prove that the algorithm may take doubly exponential time to produce the output in polynomial form, but in many cases it is still computable and useful. PubDate: 2018-06-04 DOI: 10.1007/s10472-018-9590-1

Authors:Evangelos I. Sarmas Abstract: This paper presents the workings of the Flisvos-2017 multi-agent system that participated in the Multi-Agent Programming Contest MAPC 2017 of Clausthal TU. PubDate: 2018-06-02 DOI: 10.1007/s10472-018-9587-9

Authors:Jørgen Villadsen; Oliver Fleckenstein; Helge Hatteland; John Bruntse Larsen Abstract: This paper presents the overall strategy utilized by Jason-DTU to achieve a shared second place in the annual Multi-Agent Programming Contest. It provides an overview of the implementation details considering perception, task handling, agent logic and more. The paper analyzes the team’s results in each match, and is summarized by evaluating strengths and weaknesses of the proposed multi-agent system. PubDate: 2018-06-01 DOI: 10.1007/s10472-018-9588-8

Authors:Christopher-Eyk Hrabia; Patrick Marvin Lehmann; Nabil Battjbuer; Axel Hessler; Sahin Albayrak Abstract: In the Multi-Agent Programming Contest 2017 the TUBDAI team of the Technische Universität Berlin is using the complex multi-agent scenario to evaluate the application of two frameworks from the field (multi-)robot systems. In particular the task-level decision-making and planning framework ROS Hybrid Behaviour Planner (RHBP) is used to implement the execution and decision-making for single agents. The RHBP framework builds on top of the framework Robot Operating System (ROS) that is used to implement the communication and scenario specific coordination strategy of the agents. The united team for the official contest is formed by volunteering students from a project course and their supervisors. PubDate: 2018-05-07 DOI: 10.1007/s10472-018-9586-x

Authors:Imen Zghidi; Brahim Hnich; Abdelwaheb Rebai Abstract: The original version of this article unfortunately contained a mistake. The name “Abdelwahad Rebaii” should be corrected to “Abdelwaheb Rebai”. PubDate: 2018-05-05 DOI: 10.1007/s10472-018-9583-0

Authors:Lorenz Demey; Hans Smessaert Abstract: Aristotelian diagrams are used extensively in contemporary research in artificial intelligence. The present paper investigates the geometric and cognitive differences between two types of Aristotelian diagrams for the Boolean algebra \(\mathbb {B}_{4}\) . Within the class of 3D visualizations, the main geometric distinction is that between the cube-based diagrams (such as the rhombic dodecahedron) and the tetrahedron-based diagrams. Geometric properties such as collinearity, central symmetry and distance are examined from a cognitive perspective, focusing on diagram design principles such as congruence/isomorphism and apprehension. The cognitive effectiveness of the different visualizations is compared for the representation of implication versus opposition relations, and for subdiagram embeddings. PubDate: 2018-05-02 DOI: 10.1007/s10472-018-9585-y

Authors:Rafael C. Cardoso; Tabajara Krausburg; Túlio Baségio; Débora C. Engelmann; Jomi F. Hübner; Rafael H. Bordini Abstract: The Multi-Agent Programming Contest in 2017 expanded upon the Agents in the City scenario used in the 2016 edition of the contest. In the Agents in the City contest, two teams compete to accomplish logistic tasks in simulations using realistic city maps from OpenStreetMap. The new version of the scenario shifted emphasis to include jobs that require assembled items, new types of facilities, and larger teams, resulting in a significantly more complex scenario than before. In this paper, we describe the strategies used by our team, highlighting our adaptations and any new additions from our participation in the previous year. One such new addition, is that now we have fully explored the use of all three programming dimensions (agent, environment, and organization) found in JaCaMo, the multi-agent system development platform that we used to implement our team. We also provide some discussion and analysis on what we believe were some of our most influential matches. PubDate: 2018-04-30 DOI: 10.1007/s10472-018-9584-z

Authors:Daniel Berend; Amnon Meisels; Or Peri Abstract: Distributed Constraint Optimization Problems (DCOPs) are widely used in Multi-Agent Systems for coordination and scheduling. The present paper proposes a heuristic algorithm that uses probabilistic assessment of the optimal solution in order to quickly find a solution that is not far from the optimal one. The heuristic assessment uses two passes by the agents to produce a high-quality solution. Extensive performance evaluation demonstrates that the solution of the proposed probabilistic assessment algorithm is indeed very close to the optimum, on smaller problems where this could be measured. In larger set-ups, the quality of the solution is demonstrated relatively to standard incomplete search algorithms. PubDate: 2018-04-26 DOI: 10.1007/s10472-018-9582-1

Authors:Philipp Czerner; Jonathan Pieper Abstract: In this paper we describe our participation in the 2017 edition of the Multi-Agent Programming Contest as team ‘lampe’. Our strategy was implemented in C++; it uses a centralised organisation of agents and evaluates different strategies based on an internal simulation of the future game state. Strategies are generated using handwritten heuristics in a randomised fashion, also relying on the internal simulation. PubDate: 2018-04-10 DOI: 10.1007/s10472-018-9581-2

Authors:Régis Riveret; Pietro Baroni; Yang Gao; Guido Governatori; Antonino Rotolo; Giovanni Sartor Abstract: The combination of argumentation and probability paves the way to new accounts of qualitative and quantitative uncertainty, thereby offering new theoretical and applicative opportunities. Due to a variety of interests, probabilistic argumentation is approached in the literature with different frameworks, pertaining to structured and abstract argumentation, and with respect to diverse types of uncertainty, in particular the uncertainty on the credibility of the premises, the uncertainty about which arguments to consider, and the uncertainty on the acceptance status of arguments or statements. Towards a general framework for probabilistic argumentation, we investigate a labelling-oriented framework encompassing a basic setting for rule-based argumentation and its (semi-) abstract account, along with diverse types of uncertainty. Our framework provides a systematic treatment of various kinds of uncertainty and of their relationships and allows us to back or question assertions from the literature. PubDate: 2018-03-20 DOI: 10.1007/s10472-018-9574-1

Authors:Jan Triska; Vilem Vychodil Abstract: We deal with dependencies in object-attribute data which is recorded at separate points in time. The data is formalized by finitely many tables encoding the relationship between objects and attributes and each table can be seen as single formal context observed at separate point in time. Given such data, we are interested in concise ways of characterizing all if-then dependencies between attributes that hold in the data and are preserved in all time points. In order to formalize the dependencies, we use particular if-then rules called attribute implications annotated by time points which can be seen as particular formulas of linear temporal logic. We introduce non-redundant bases of dependencies from data as non-redundant sets entailing exactly all dependencies that hold in the data. In addition, we investigate minimality of bases as stronger form of non-redundancy. For given data, we present description of minimal bases using the notion of pseudo-intents generalized in the temporal setting. The present paper is a continuation of our previous paper on entailment of attribute implications annotated by time points. PubDate: 2018-03-06 DOI: 10.1007/s10472-018-9576-z