for Journals by Title or ISSN
for Articles by Keywords
Journal Cover Artificial Intelligence
  [SJR: 2.426]   [H-I: 115]   [136 followers]  Follow
   Hybrid Journal Hybrid journal (It can contain Open Access articles)
   ISSN (Print) 0004-3702
   Published by Elsevier Homepage  [3043 journals]
  • Towards breaking more composition symmetries in partial symmetry breaking
    • Authors: Jimmy H.M. Lee; Zichen Zhu
      Pages: 51 - 82
      Abstract: Publication date: November 2017
      Source:Artificial Intelligence, Volume 252
      Author(s): Jimmy H.M. Lee, Zichen Zhu
      The paper proposes a dynamic method, Recursive Symmetry Breaking During Search (ReSBDS), for efficient partial symmetry breaking. We first demonstrate how Partial Symmetry Breaking During Search (ParSBDS) misses important pruning opportunities when given only a subset of symmetries to break. The investigation pinpoints the culprit and in turn suggests rectification. The main idea is to add extra symmetry breaking constraints during search recursively to prune also symmetric nodes of some pruned subtrees. Thus, ReSBDS can break extra symmetry compositions, but is carefully designed to break only the ones that are easy to identify and inexpensive to break. We present theorems to guarantee the soundness and termination of our approach, and compare our method with popular static and dynamic methods. When the variable (value) heuristic is static, ReSBDS is also complete in eliminating all interchangeable variables (values) given only the generator symmetries. We propose further a light version of ReSBDS method (LReSBDS), which has a slightly weaker pruning power of ReSBDS but with a reduced overhead. We give theoretical characterization on the soundness and termination of LReSBDS, and comparisons on pruning strengths against other symmetry breaking methods including ReSBDS. Extensive experimentations confirm the efficiency of ReSBDS and LReSBDS, when compared against state of the art methods.

      PubDate: 2017-09-26T05:22:05Z
      DOI: 10.1016/j.artint.2017.07.006
      Issue No: Vol. 252 (2017)
  • Forward bounding on pseudo-trees for DCOPs and ADCOPs
    • Authors: Omer Litov; Amnon Meisels
      Pages: 83 - 99
      Abstract: Publication date: November 2017
      Source:Artificial Intelligence, Volume 252
      Author(s): Omer Litov, Amnon Meisels
      Complete search algorithms for solving Distributed constraint optimization problems (DCOPs) can be divided into two groups: algorithms that use a pseudo tree and algorithms that do not use one. The best performing algorithms that do not use a pseudo tree use some form of forward bounding. In order to try and gain from both worlds, a new algorithm, which incorporates a hybrid approach of the two groups is presented. The proposed algorithm – Pseudo-Tree Forward-bounding (PT-FB) – is shown to perform very well. PT-FB is next extended to be able to solve Asymmetric DCOPs (ADCOPs). Here again, its performance is better than its competitors. An extensive experimental evaluation of the performance of each of the proposed algorithms is presented.

      PubDate: 2017-09-26T05:22:05Z
      DOI: 10.1016/j.artint.2017.07.003
      Issue No: Vol. 252 (2017)
  • Deliberation for autonomous robots: A survey
    • Authors: Félix Ingrand; Malik Ghallab
      Pages: 10 - 44
      Abstract: Publication date: June 2017
      Source:Artificial Intelligence, Volume 247
      Author(s): Félix Ingrand, Malik Ghallab
      Autonomous robots facing a diversity of open environments and performing a variety of tasks and interactions need explicit deliberation in order to fulfill their missions. Deliberation is meant to endow a robotic system with extended, more adaptable and robust functionalities, as well as reduce its deployment cost. The ambition of this survey is to present a global overview of deliberation functions in robotics and to discuss the state of the art in this area. The following five deliberation functions are identified and analyzed: planning, acting, monitoring, observing, and learning. The paper introduces a global perspective on these deliberation functions and discusses their main characteristics, design choices and constraints. The reviewed contributions are discussed with respect to this perspective. The survey focuses as much as possible on papers with a clear robotics content and with a concern on integrating several deliberation functions.

      PubDate: 2017-04-26T11:43:34Z
      DOI: 10.1016/j.artint.2014.11.003
      Issue No: Vol. 247 (2017)
  • Artificial cognition for social human–robot interaction: An
    • Authors: Séverin Lemaignan; Mathieu Warnier; E. Akin Sisbot; Aurélie Clodic; Rachid Alami
      Pages: 45 - 69
      Abstract: Publication date: June 2017
      Source:Artificial Intelligence, Volume 247
      Author(s): Séverin Lemaignan, Mathieu Warnier, E. Akin Sisbot, Aurélie Clodic, Rachid Alami
      Human–Robot Interaction challenges Artificial Intelligence in many regards: dynamic, partially unknown environments that were not originally designed for robots; a broad variety of situations with rich semantics to understand and interpret; physical interactions with humans that requires fine, low-latency yet socially acceptable control strategies; natural and multi-modal communication which mandates common-sense knowledge and the representation of possibly divergent mental models. This article is an attempt to characterise these challenges and to exhibit a set of key decisional issues that need to be addressed for a cognitive robot to successfully share space and tasks with a human. We identify first the needed individual and collaborative cognitive skills: geometric reasoning and situation assessment based on perspective-taking and affordance analysis; acquisition and representation of knowledge models for multiple agents (humans and robots, with their specificities); situated, natural and multi-modal dialogue; human-aware task planning; human–robot joint task achievement. The article discusses each of these abilities, presents working implementations, and shows how they combine in a coherent and original deliberative architecture for human–robot interaction. Supported by experimental results, we eventually show how explicit knowledge management, both symbolic and geometric, proves to be instrumental to richer and more natural human–robot interactions by pushing for pervasive, human-level semantics within the robot's deliberative system.

      PubDate: 2017-04-26T11:43:34Z
      DOI: 10.1016/j.artint.2016.07.002
      Issue No: Vol. 247 (2017)
  • Scalable transfer learning in heterogeneous, dynamic environments
    • Authors: Trung Thanh Nguyen; Tomi Silander; Zhuoru Li; Tze-Yun Leong
      Pages: 70 - 94
      Abstract: Publication date: June 2017
      Source:Artificial Intelligence, Volume 247
      Author(s): Trung Thanh Nguyen, Tomi Silander, Zhuoru Li, Tze-Yun Leong
      Reinforcement learning is a plausible theoretical basis for developing self-learning, autonomous agents or robots that can effectively represent the world dynamics and efficiently learn the problem features to perform different tasks in different environments. The computational costs and complexities involved, however, are often prohibitive for real-world applications. This study introduces a scalable methodology to learn and transfer knowledge of the transition (and reward) models for model-based reinforcement learning in a complex world. We propose a variant formulation of Markov decision processes that supports efficient online-learning of the relevant problem features to approximate the world dynamics. We apply the new feature selection and dynamics approximation techniques in heterogeneous transfer learning, where the agent automatically maintains and adapts multiple representations of the world to cope with the different environments it encounters during its lifetime. We prove regret bounds for our approach, and empirically demonstrate its capability to quickly converge to a near optimal policy in both real and simulated environments.

      PubDate: 2017-04-26T11:43:34Z
      DOI: 10.1016/j.artint.2015.09.013
      Issue No: Vol. 247 (2017)
  • Transferring skills to humanoid robots by extracting semantic
           representations from observations of human activities
    • Authors: Karinne Ramirez-Amaro; Michael Beetz; Gordon Cheng
      Pages: 95 - 118
      Abstract: Publication date: June 2017
      Source:Artificial Intelligence, Volume 247
      Author(s): Karinne Ramirez-Amaro, Michael Beetz, Gordon Cheng
      In this study, we present a framework that infers human activities from observations using semantic representations. The proposed framework can be utilized to address the difficult and challenging problem of transferring tasks and skills to humanoid robots. We propose a method that allows robots to obtain and determine a higher-level understanding of a demonstrator's behavior via semantic representations. This abstraction from observations captures the “essence” of the activity, thereby indicating which aspect of the demonstrator's actions should be executed in order to accomplish the required activity. Thus, a meaningful semantic description is obtained in terms of human motions and object properties. In addition, we validated the semantic rules obtained in different conditions, i.e., three different and complex kitchen activities: 1) making a pancake; 2) making a sandwich; and 3) setting the table. We present quantitative and qualitative results, which demonstrate that without any further training, our system can deal with time restrictions, different execution styles of the same task by several participants, and different labeling strategies. This means, the rules obtained from one scenario are still valid even for new situations, which demonstrates that the inferred representations do not depend on the task performed. The results show that our system correctly recognized human behaviors in real-time in around 87.44% of cases, which was even better than a random participant recognizing the behaviors of another human (about 76.68%). In particular, the semantic rules acquired can be used to effectively improve the dynamic growth of the ontology-based knowledge representation. Hence, this method can be used flexibly across different demonstrations and constraints to infer and achieve a similar goal to that observed. Furthermore, the inference capability introduced in this study was integrated into a joint space control loop for a humanoid robot, an iCub, for achieving similar goals to the human demonstrator online.

      PubDate: 2017-04-26T11:43:34Z
      DOI: 10.1016/j.artint.2015.08.009
      Issue No: Vol. 247 (2017)
  • Robot task planning and explanation in open and uncertain worlds
    • Authors: Marc Hanheide; Moritz Göbelbecker; Graham S. Horn; Andrzej Pronobis; Kristoffer Sjöö; Alper Aydemir; Patric Jensfelt; Charles Gretton; Richard Dearden; Miroslav Janicek; Hendrik Zender; Geert-Jan Kruijff; Nick Hawes; Jeremy L. Wyatt
      Pages: 119 - 150
      Abstract: Publication date: June 2017
      Source:Artificial Intelligence, Volume 247
      Author(s): Marc Hanheide, Moritz Göbelbecker, Graham S. Horn, Andrzej Pronobis, Kristoffer Sjöö, Alper Aydemir, Patric Jensfelt, Charles Gretton, Richard Dearden, Miroslav Janicek, Hendrik Zender, Geert-Jan Kruijff, Nick Hawes, Jeremy L. Wyatt
      A long-standing goal of AI is to enable robots to plan in the face of uncertain and incomplete information, and to handle task failure intelligently. This paper shows how to achieve this. There are two central ideas. The first idea is to organize the robot's knowledge into three layers: instance knowledge at the bottom, commonsense knowledge above that, and diagnostic knowledge on top. Knowledge in a layer above can be used to modify knowledge in the layer(s) below. The second idea is that the robot should represent not just how its actions change the world, but also what it knows or believes. There are two types of knowledge effects the robot's actions can have: epistemic effects (I believe X because I saw it) and assumptions (I'll assume X to be true). By combining the knowledge layers with the models of knowledge effects, we can simultaneously solve several problems in robotics: (i) task planning and execution under uncertainty; (ii) task planning and execution in open worlds; (iii) explaining task failure; (iv) verifying those explanations. The paper describes how the ideas are implemented in a three-layer architecture on a mobile robot platform. The robot implementation was evaluated in five different experiments on object search, mapping, and room categorization.

      PubDate: 2017-04-26T11:43:34Z
      DOI: 10.1016/j.artint.2015.08.008
      Issue No: Vol. 247 (2017)
  • Representations for robot knowledge in the KnowRob framework
    • Authors: Moritz Tenorth; Michael Beetz
      Pages: 151 - 169
      Abstract: Publication date: June 2017
      Source:Artificial Intelligence, Volume 247
      Author(s): Moritz Tenorth, Michael Beetz
      In order to robustly perform tasks based on abstract instructions, robots need sophisticated knowledge processing methods. These methods have to supply the difference between the (often shallow and symbolic) information in the instructions and the (detailed, grounded and often real-valued) information needed for execution. For filling these information gaps, a robot first has to identify them in the instructions, reason about suitable information sources, and combine pieces of information from different sources and of different structure into a coherent knowledge base. To this end we propose the KnowRob knowledge processing system for robots. In this article, we discuss why the requirements of a robot knowledge processing system differ from what is commonly investigated in AI research, and propose to re-consider a KR system as a semantically annotated view on information and algorithms that are often already available as part of the robot's control system. We then introduce representational structures and a common vocabulary for representing knowledge about robot actions, events, objects, environments, and the robot's hardware as well as inference procedures that operate on this common representation. The KnowRob system has been released as open-source software and is being used on several robots performing complex object manipulation tasks. We evaluate it through prototypical queries that demonstrate the expressive power and its impact on the robot's performance.

      PubDate: 2017-04-26T11:43:34Z
      DOI: 10.1016/j.artint.2015.05.010
      Issue No: Vol. 247 (2017)
  • Intrinsically motivated model learning for developing curious robots
    • Authors: Todd Hester; Peter Stone
      Pages: 170 - 186
      Abstract: Publication date: June 2017
      Source:Artificial Intelligence, Volume 247
      Author(s): Todd Hester, Peter Stone
      Reinforcement Learning (RL) agents are typically deployed to learn a specific, concrete task based on a pre-defined reward function. However, in some cases an agent may be able to gain experience in the domain prior to being given a task. In such cases, intrinsic motivation can be used to enable the agent to learn a useful model of the environment that is likely to help it learn its eventual tasks more efficiently. This paradigm fits robots particularly well, as they need to learn about their own dynamics and affordances which can be applied to many different tasks. This article presents the texplore with Variance-And-Novelty-Intrinsic-Rewards algorithm (texplore-vanir), an intrinsically motivated model-based RL algorithm. The algorithm learns models of the transition dynamics of a domain using random forests. It calculates two different intrinsic motivations from this model: one to explore where the model is uncertain, and one to acquire novel experiences that the model has not yet been trained on. This article presents experiments demonstrating that the combination of these two intrinsic rewards enables the algorithm to learn an accurate model of a domain with no external rewards and that the learned model can be used afterward to perform tasks in the domain. While learning the model, the agent explores the domain in a developing and curious way, progressively learning more complex skills. In addition, the experiments show that combining the agent's intrinsic rewards with external task rewards enables the agent to learn faster than using external rewards alone. We also present results demonstrating the applicability of this approach to learning on robots.

      PubDate: 2017-04-26T11:43:34Z
      DOI: 10.1016/j.artint.2015.05.002
      Issue No: Vol. 247 (2017)
  • Efficient interactive decision-making framework for robotic applications
    • Authors: Alejandro Agostini; Carme Torras; Florentin Wörgötter
      Pages: 187 - 212
      Abstract: Publication date: June 2017
      Source:Artificial Intelligence, Volume 247
      Author(s): Alejandro Agostini, Carme Torras, Florentin Wörgötter
      The inclusion of robots in our society is imminent, such as service robots. Robots are now capable of reliably manipulating objects in our daily lives but only when combined with artificial intelligence (AI) techniques for planning and decision-making, which allow a machine to determine how a task can be completed successfully. To perform decision making, AI planning methods use a set of planning operators to code the state changes in the environment produced by a robotic action. Given a specific goal, the planner then searches for the best sequence of planning operators, i.e., the best plan that leads through the state space to satisfy the goal. In principle, planning operators can be hand-coded, but this is impractical for applications that involve many possible state transitions. An alternative is to learn them automatically from experience, which is most efficient when there is a human teacher. In this study, we propose a simple and efficient decision-making framework for this purpose. The robot executes its plan in a step-wise manner and any planning impasse produced by missing operators is resolved online by asking a human teacher for the next action to execute. Based on the observed state transitions, this approach rapidly generates the missing operators by evaluating the relevance of several cause–effect alternatives in parallel using a probability estimate, which compensates for the high uncertainty that is inherent when learning from a small number of samples. We evaluated the validity of our approach in simulated and real environments, where it was benchmarked against previous methods. Humans learn in the same incremental manner, so we consider that our approach may be a better alternative to existing learning paradigms, which require offline learning, a significant amount of previous knowledge, or a large number of samples.

      PubDate: 2017-04-26T11:43:34Z
      DOI: 10.1016/j.artint.2015.04.004
      Issue No: Vol. 247 (2017)
  • Robotic manipulation of multiple objects as a POMDP
    • Authors: Joni Pajarinen; Ville Kyrki
      Pages: 213 - 228
      Abstract: Publication date: June 2017
      Source:Artificial Intelligence, Volume 247
      Author(s): Joni Pajarinen, Ville Kyrki
      This paper investigates manipulation of multiple unknown objects in a crowded environment. Because of incomplete knowledge due to unknown objects and occlusions in visual observations, object observations are imperfect and action success is uncertain, making planning challenging. We model the problem as a partially observable Markov decision process (POMDP), which allows a general reward based optimization objective and takes uncertainty in temporal evolution and partial observations into account. In addition to occlusion dependent observation and action success probabilities, our POMDP model also automatically adapts object specific action success probabilities. To cope with the changing system dynamics and performance constraints, we present a new online POMDP method based on particle filtering that produces compact policies. The approach is validated both in simulation and in physical experiments in a scenario of moving dirty dishes into a dishwasher. The results indicate that: 1) a greedy heuristic manipulation approach is not sufficient, multi-object manipulation requires multi-step POMDP planning, and 2) on-line planning is beneficial since it allows the adaptation of the system dynamics model based on actual experience.

      PubDate: 2017-04-26T11:43:34Z
      DOI: 10.1016/j.artint.2015.04.001
      Issue No: Vol. 247 (2017)
  • Geometric backtracking for combined task and motion planning in robotic
    • Authors: Julien Bidot; Lars Karlsson; Fabien Lagriffoul; Alessandro Saffiotti
      Pages: 229 - 265
      Abstract: Publication date: June 2017
      Source:Artificial Intelligence, Volume 247
      Author(s): Julien Bidot, Lars Karlsson, Fabien Lagriffoul, Alessandro Saffiotti
      Planners for real robotic systems should not only reason about abstract actions, but also about aspects related to physical execution such as kinematics and geometry. We present an approach to hybrid task and motion planning, in which state-based forward-chaining task planning is tightly coupled with motion planning and other forms of geometric reasoning. Our approach is centered around the problem of geometric backtracking that arises in hybrid task and motion planning: in order to satisfy the geometric preconditions of the current action, a planner may need to reconsider geometric choices, such as grasps and poses, that were made for previous actions. Geometric backtracking is a necessary condition for completeness, but it may lead to a dramatic computational explosion due to the large size of the space of geometric states. We explore two avenues to deal with this issue: the use of heuristics based on different geometric conditions to guide the search, and the use of geometric constraints to prune the search space. We empirically evaluate these different approaches, and demonstrate that they improve the performance of hybrid task and motion planning. We demonstrate our hybrid planning approach in two domains: a real, humanoid robotic platform, the DLR Justin robot, performing object manipulation tasks; and a simulated autonomous forklift operating in a warehouse.

      PubDate: 2017-04-26T11:43:34Z
      DOI: 10.1016/j.artint.2015.03.005
      Issue No: Vol. 247 (2017)
  • Taking Account of the Actions of Others in Value-based Reasoning
    • Authors: Katie Atkinson; Trevor Bench-Capon
      Abstract: Publication date: Available online 28 September 2017
      Source:Artificial Intelligence
      Author(s): Katie Atkinson, Trevor Bench-Capon
      Practical reasoning, reasoning about what actions should be chosen, is highly dependent both on the individual values of the agent concerned and on what others choose to do. Hitherto, computational models of value-based argumentation for practical reasoning have required assumptions to be made about the beliefs and preferences of other agents. Here we present a new method for taking the actions of others into account that does not require these assumptions: the only beliefs and preferences considered are those of the agent engaged in the reasoning. Our new formalism draws on utility-based approaches and expresses the reasoning in the form of arguments and objections, to enable full integration with value-based practical reasoning. We illustrate our approach by showing how value-based reasoning is modelled in two scenarios used in experimental economics, the Ultimatum Game and the Prisoner's Dilemma, and we present an evaluation of our approach in terms of these experiments. The evaluation demonstrates that our model is able to reproduce computationally the results of ethnographic experiments, serving as an encouraging validation exercise.

      PubDate: 2017-10-04T05:01:40Z
      DOI: 10.1016/j.artint.2017.09.002
  • Resolving distributed knowledge
    • Authors: Thomas
      Abstract: Publication date: November 2017
      Source:Artificial Intelligence, Volume 252
      Author(s): Thomas Ågotnes, Yì N. Wáng
      In epistemic logic, a key formal theory for reasoning about knowledge in AI and other fields, different notions of group knowledge describe different ways in which knowledge can be associated with a group of agents. Distributed knowledge can be seen as the sum of the knowledge in a group; it is sometimes referred to as the potential knowledge of a group, or the joint knowledge they could obtain if they had unlimited means of communication. In epistemic logic, a formula of the form D G φ is intended to express the fact that group G has distributed knowledge of φ, that the total information in the group can be used to infer φ. In this paper we show that this is not the same as φ necessarily being true after the members of the group actually share all their information with each other – perhaps contrary to intuitive ideas about what distributed knowledge is. We furthermore introduce a new operator R G , such that R G φ means that φ is true after G have shared all their information with each other – after G's distributed knowledge has been resolved. The R G operators are called resolution operators. We study logics with different combinations of resolution operators and operators for common and distributed knowledge. Of particular interest is the relationship between distributed and common knowledge. The main results are characterizations of expressive power, and sound and complete axiomatizations. We also study the relationship to public announcement logic.

      PubDate: 2017-09-26T05:22:05Z
  • Intelligent agent supporting human-multi-robot Team collaboration
    • Authors: Ariel Rosenfeld; Noa Agmon; Oleg Maksimov; Sarit Kraus
      Abstract: Publication date: Available online 31 August 2017
      Source:Artificial Intelligence
      Author(s): Ariel Rosenfeld, Noa Agmon, Oleg Maksimov, Sarit Kraus
      The number of multi-robot systems deployed in field applications has risen dramatically over the years. Nevertheless, supervising and operating multiple robots simultaneously is a difficult task for a single operator to execute. In this article we propose a novel approach for utilizing automated advising agents in assisting an operator to better manage a team of multiple robots in complex environments. We introduce an advice provision methodology and exemplify its implementation using automated advising agents in two real-world human-multi-robot team collaboration tasks: the Search And Rescue (SAR) and the warehouse operation tasks. Our intelligent advising agents were evaluated through extensive field trials, with over 150 human operators using both simulated and physical mobile robots, and showed a significant improvement in the team's performance.

      PubDate: 2017-09-02T00:31:24Z
      DOI: 10.1016/j.artint.2017.08.005
  • Distributed first order logic
    • Authors: Chiara Ghidini; Luciano Serafini
      Abstract: Publication date: Available online 30 August 2017
      Source:Artificial Intelligence
      Author(s): Chiara Ghidini, Luciano Serafini
      Distributed First Order Logic (DFOL) has been introduced more than ten years ago with the purpose of formalising distributed knowledge-based systems, where knowledge about heterogeneous domains is scattered into a set of interconnected modules. DFOL formalises the knowledge contained in each module by means of first-order theories, and the interconnections between modules by means of special inference rules called bridge rules. Despite their restricted form in the original DFOL formulation, bridge rules have influenced several works in the areas of heterogeneous knowledge integration, modular knowledge representation, and schema/ontology matching. This, in turn, has fostered extensions and modifications of the original DFOL that have never been systematically described and published. This paper tackles the lack of a comprehensive description of DFOL by providing a systematic account of a completely revised and extended version of the logic, together with a sound and complete axiomatisation of a general form of bridge rules based on Natural Deduction. The resulting DFOL framework is then proposed as a clear formal tool for the representation of and reasoning about distributed knowledge and bridge rules.

      PubDate: 2017-09-02T00:31:24Z
      DOI: 10.1016/j.artint.2017.08.008
  • The MADLA Planner: Multi-Agent Planning by Combination of Distributed and
           Local Heuristic Search
    • Authors: Michal Štolba; Antonín Komenda
      Abstract: Publication date: Available online 30 August 2017
      Source:Artificial Intelligence
      Author(s): Michal Štolba, Antonín Komenda
      Real world applications often require cooperation of multiple independent entities. Classical planning is a well established technique solving various challenging problems such as logistic planning, factory process planning, military mission planning and high-level planning for robots. Multi-agent planning aims at solving similar problems in the presence of multiple independent entities (agents). Even though such entities might want to cooperate in order to fulfill a common goal, they may want to keep their internal information and processes private. In such case, we talk about privacy-preserving multi-agent planning. So far, multi-agent planners based on heuristic search used either a local heuristic estimating the particular agent's local subproblem or a distributed heuristic estimating the global problem as a whole. In this paper, we present the Multi-Agent Distributed and Local Asynchronous (MADLA) Planner, running a novel variant of a distributed state-space forward-chaining multi-heuristic search which combines the use of a local and a distributed heuristic in order to combine their benefits. In particular, the planner uses two variants of the well known Fast-Forward heuristic. We provide proofs of soundness and completeness of the search algorithm and show how much and what type of privacy it preserves. We also provide an improved privacy-preserving distribution scheme for the Fast-Forward heuristic. We experimentally compare the newly proposed multi-heuristic scheme and the two used heuristics separately. The results show that the proposed solution outperforms classical (single-heuristic) distributed search with either one of the heuristics used separately. In the detailed experimental analysis, we show limits of the planner and of the used heuristics based on particular properties of the benchmark domains. In a comprehensive set of multi-agent planning domains and problems, we show that the MADLA Planner outperforms all contemporary state-of-the-art privacy-preserving multi-agent planners using a compatible planning model.

      PubDate: 2017-09-02T00:31:24Z
      DOI: 10.1016/j.artint.2017.08.007
  • Three-valued semantics for hybrid MKNF knowledge bases revisited
    • Authors: Fangfang Liu; Jia-Huai You
      Abstract: Publication date: Available online 24 August 2017
      Source:Artificial Intelligence
      Author(s): Fangfang Liu, Jia-Huai You
      Knorr et al. (2011) formulated a three-valued formalism for the logic of Minimal Knowledge and Negation as Failure (MKNF), and proposed a well-founded semantics for hybrid MKNF knowledge bases. The main results state that if a hybrid MKNF knowledge base has a three-valued MKNF model, its well-founded MKNF model exists, which is unique and can be computed by an alternating fixpoint construction. However, we show that these claims are erroneous. The goal of this paper is two-fold. First, we provide insight into why these claims fail to hold. This leads to a classification of hybrid MKNF knowledge bases into a hierarchy of four classes, of which the smallest one is what works for the well-founded semantics proposed by Knorr et al. After that, we characterize three-valued MKNF models into what we call stable partitions, which are similar to partial stable models in logic programming. The intuitive notion of stable partitions allows us to discover a new proof-theoretic method to determine whether a three-valued MKNF model exists for a given hybrid MKNF knowledge base. We can guess partial partitions and verify their stability by computing alternating fixpoints and by performing a consistency check. This algorithm can be applied to compute all three-valued MKNF models, as well as all two-valued ones originally formulated by Motik and Rosati for query answering. As a result, our work provides a uniform characterization of well-founded, two-valued, and all three-valued MKNF models, in terms of stable partitions and the alternating fixpoint construction.

      PubDate: 2017-09-02T00:31:24Z
      DOI: 10.1016/j.artint.2017.08.003
  • Iterative voting and acyclic games
    • Authors: Reshef Meir; Maria Polukarov; Jeffrey S. Rosenschein; Nicholas R. Jennings
      Abstract: Publication date: Available online 24 August 2017
      Source:Artificial Intelligence
      Author(s): Reshef Meir, Maria Polukarov, Jeffrey S. Rosenschein, Nicholas R. Jennings
      Multi-agent decision problems, in which independent agents have to agree on a joint plan of action or allocation of resources, are central to artificial intelligence. In such situations, agents' individual preferences over available alternatives may vary, and they may try to reconcile these differences by voting. We consider scenarios where voters cannot coordinate their actions, but are allowed to change their vote after observing the current outcome, as is often the case both in offline committees and in online voting. Specifically, we are interested in identifying conditions under which such iterative voting processes are guaranteed to converge to a Nash equilibrium state—that is, under which this process is acyclic. We classify convergence results based on the underlying assumptions about the agent scheduler (the order in which the agents take their actions) and the action scheduler (the actions available to the agents at each step). By so doing, we position iterative voting models within the general framework of acyclic games and game forms. In more detail, our main technical results provide a complete picture of conditions for acyclicity in several variations of Plurality voting. In particular, we show that (a) under the traditional lexicographic tie-breaking, the game converges from any state and for any order of agents, under a weak restriction on voters' actions; and that (b) Plurality with randomized tie-breaking is not guaranteed to converge under arbitrary agent schedulers, but there is always some path of better replies from any initial state of the game to a Nash equilibrium. We thus show a first separation between order-free acyclicity and weak acyclicity of game forms, thereby settling an open question from [Kukushkin 2011]. In addition, we refute another conjecture of Kukushkin regarding strongly acyclic voting rules, by proving the existence of strongly acyclic separable game forms.

      PubDate: 2017-09-02T00:31:24Z
      DOI: 10.1016/j.artint.2017.08.002
  • Common Sense, The Turing Test, and The Quest for Real AI, Hector Levesque.
           The MIT Press (2017), 142
    • Authors: David Israel (Emeritus)
      Abstract: Publication date: Available online 23 August 2017
      Source:Artificial Intelligence
      Author(s): David Israel (Emeritus)

      PubDate: 2017-09-02T00:31:24Z
      DOI: 10.1016/j.artint.2017.08.004
  • MM: A bidirectional search algorithm that is guaranteed to meet in the
    • Authors: Robert C. Holte; Ariel Felner; Guni Sharon; Nathan R. Sturtevant; Jingwei Chen
      Abstract: Publication date: Available online 22 August 2017
      Source:Artificial Intelligence
      Author(s): Robert C. Holte, Ariel Felner, Guni Sharon, Nathan R. Sturtevant, Jingwei Chen
      Bidirectional search algorithms interleave two separate searches, a normal search forward from the start state, and a search backward from the goal. It is well known that adding a heuristic to unidirectional search dramatically reduces the search effort. By contrast, despite decades of research, bidirectional heuristic search has not yet had a major impact. Additionally, no comprehensive theory was ever devised to understand the nature of bidirectional heuristic search. In this paper we aim to close this gap. We first present MM, a novel bidirectional heuristic search algorithm. Unlike previous bidirectional heuristic search algorithms, MM's forward and backward searches are guaranteed to “meet in the middle”, i.e. never expand a node beyond the solution midpoint. Based on this unique attribute we present a novel framework for comparing MM, A*, and their brute-force variants. We do this by dividing the entire state space into disjoint regions based on their distance from the start and goal. This allows us to perform a comparison of these algorithms on a per region basis and identify conditions favoring each algorithm. Finally, we present experimental results that support our theoretical analysis.

      PubDate: 2017-09-02T00:31:24Z
      DOI: 10.1016/j.artint.2017.05.004
  • Generalized possibilistic logic: Foundations and applications to
           qualitative reasoning about uncertainty
    • Authors: Didier Dubois; Henri Prade; Steven Schockaert
      Abstract: Publication date: Available online 9 August 2017
      Source:Artificial Intelligence
      Author(s): Didier Dubois, Henri Prade, Steven Schockaert
      This paper introduces generalized possibilistic logic (GPL), a logic for epistemic reasoning based on possibility theory. Formulas in GPL correspond to propositional combinations of assertions such as “it is certain to degree λ that the propositional formula α is true”. As its name suggests, the logic generalizes possibilistic logic (PL), which at the syntactic level only allows conjunctions of the aforementioned type of assertions. At the semantic level, PL can only encode sets of epistemic states encompassed by a single least informed one, whereas GPL can encode any set of epistemic states. This feature makes GPL particularly suitable for reasoning about what an agent knows about the beliefs of another agent, e.g., allowing the former to draw conclusions about what the other agent does not know. We introduce an axiomatization for GPL and show its soundness and completeness w.r.t. possibilistic semantics. Subsequently, we highlight the usefulness of GPL as a powerful unifying framework for various knowledge representation formalisms. Among others, we show how comparative uncertainty and ignorance can be modelled in GPL. We also exhibit a close connection between GPL and various existing formalisms, including possibilistic logic with partially ordered formulas, a logic of conditional assertions in the style of Kraus, Lehmann and Magidor, answer set programming and a fragment of the logic of minimal belief and negation as failure. Finally, we analyse the computational complexity of reasoning in GPL, identifying decision problems at the first, second, third and fourth level of the polynomial hierarchy.

      PubDate: 2017-09-02T00:31:24Z
      DOI: 10.1016/j.artint.2017.08.001
  • Minimal sets on propositional formulae. Problems and reductions
    • Authors: Joao Marques-Silva; Mikoláš Janota; Carlos Mencía
      Abstract: Publication date: Available online 2 August 2017
      Source:Artificial Intelligence
      Author(s): Joao Marques-Silva, Mikoláš Janota, Carlos Mencía
      Boolean Satisfiability (SAT) is arguably the archetypical NP-complete decision problem. Progress in SAT solving algorithms has motivated an ever increasing number of practical applications in recent years. However, many practical uses of SAT involve solving function as opposed to decision problems. Concrete examples include computing minimal unsatisfiable subsets, minimal correction subsets, prime implicates and implicants, minimal models, backbone literals, and autarkies, among several others. In most cases, solving a function problem requires a number of adaptive or non-adaptive calls to a SAT solver. Given the computational complexity of SAT, it is therefore important to develop algorithms that either require the smallest possible number of calls to the SAT solver, or that involve simpler instances. This paper addresses a number of representative function problems defined on Boolean formulae, and shows that all these function problems can be reduced to a generic problem of computing a minimal set subject to a monotone predicate. This problem is referred to as the Minimal Set over Monotone Predicate (MSMP) problem. This work provides new ways for solving well-known function problems, including prime implicates, minimal correction subsets, backbone literals, independent variables and autarkies, among several others. Moreover, this work also motivates the development of more efficient algorithms for the MSMP problem. Finally the paper outlines a number of areas of future research related with extensions of the MSMP problem.

      PubDate: 2017-08-02T23:35:09Z
      DOI: 10.1016/j.artint.2017.07.005
  • Belief revision and projection in the epistemic situation calculus
    • Authors: Christoph Schwering; Gerhard Lakemeyer; Maurice Pagnucco
      Abstract: Publication date: Available online 31 July 2017
      Source:Artificial Intelligence
      Author(s): Christoph Schwering, Gerhard Lakemeyer, Maurice Pagnucco
      This article considers defeasible beliefs in dynamic settings. In particular, we examine the belief projection problem: what is believed after performing an action and/or receiving new information' The approach is based on an epistemic variant of Reiter's situation calculus, where actions not only have physical effects but may also provide new information to the agent. The preferential belief structure is initially determined using conditional statements. New information is then incorporated using two popular belief revision schemes, namely natural and lexicographic revision. The projection problem is solved twofold in this formalism: by goal regression and by knowledge base progression.

      PubDate: 2017-08-02T23:35:09Z
      DOI: 10.1016/j.artint.2017.07.004
  • Automatically Improving Constraint Models in Savile Row
    • Authors: Peter Nightingale; Özgür Akgün; Ian P. Gent; Christopher Jefferson; Ian Miguel; Patrick Spracklen
      Abstract: Publication date: Available online 13 July 2017
      Source:Artificial Intelligence
      Author(s): Peter Nightingale, Özgür Akgün, Ian P. Gent, Christopher Jefferson, Ian Miguel, Patrick Spracklen
      When solving a combinatorial problem using Constraint Programming (CP) or Satisfiability (SAT), modelling and formulation are vital and difficult tasks. Even an expert human may explore many alternatives in modelling a single problem. We make a number of contributions in the automated modelling and reformulation of constraint models. We study a range of automated reformulation techniques, finding combinations of techniques which perform particularly well together. We introduce and describe in detail a new algorithm, X-CSE, to perform Associative-Commutative Common Subexpression Elimination (AC-CSE) in constraint problems, significantly improving existing CSE techniques for associative and commutative operators such as +. We demonstrate that these reformulation techniques can be integrated in a single automated constraint modelling tool, called Savile Row, whose architecture we describe. We use Savile Row as an experimental testbed to evaluate each reformulation on a set of 50 problem classes, with 596 instances in total. Our recommended reformulations are well worthwhile even including overheads, especially on harder instances where solver time dominates. With a SAT solver we observed a geometric mean of 2.15 times speedup compared to a straightforward tailored model without recommended reformulations. Using a CP solver, we obtained a geometric mean of 5.96 times speedup for instances taking over 10 seconds to solve.

      PubDate: 2017-07-23T12:45:36Z
      DOI: 10.1016/j.artint.2017.07.001
  • Latent tree models for hierarchical topic detection
    • Authors: Peixian Chen; Nevin L. Zhang; Tengfei Liu; Leonard K.M. Poon; Zhourong Chen; Farhan Khawar
      Abstract: Publication date: Available online 29 June 2017
      Source:Artificial Intelligence
      Author(s): Peixian Chen, Nevin L. Zhang, Tengfei Liu, Leonard K.M. Poon, Zhourong Chen, Farhan Khawar
      We present a novel method for hierarchical topic detection where topics are obtained by clustering documents in multiple ways. Specifically, we model document collections using a class of graphical models called hierarchical latent tree models (HLTMs). The variables at the bottom level of an HLTM are observed binary variables that represent the presence/absence of words in a document. The variables at other levels are binary latent variables that represent word co-occurrence patterns or co-occurrences of such patterns. Each latent variable gives a soft partition of the documents, and document clusters in the partitions are interpreted as topics. Latent variables at high levels of the hierarchy capture long-range word co-occurrence patterns and hence give thematically more general topics, while those at low levels of the hierarchy capture short-range word co-occurrence patterns and give thematically more specific topics. In comparison with LDA-based methods, a key advantage of the new method is that it represents co-occurrence patterns explicitly using model structures. Extensive empirical results show that the new method significantly outperforms the LDA-based methods in term of model quality and meaningfulness of topics and topic hierarchies.

      PubDate: 2017-07-02T13:12:00Z
      DOI: 10.1016/j.artint.2017.06.004
  • Impossibility in Belief Merging
    • Authors: Amílcar Mata Díaz; Ramón Pino Pérez
      Abstract: Publication date: Available online 29 June 2017
      Source:Artificial Intelligence
      Author(s): Amílcar Mata Díaz, Ramón Pino Pérez
      With the aim of studying social properties of belief merging and having a better understanding of impossibility, we extend in three ways the framework of logic-based merging introduced by Konieczny and Pino Pérez. First, at the level of representation of the information, we pass from belief bases to complex epistemic states. Second, the profiles are represented as functions of finite societies to the set of epistemic states (a sort of vectors) and not as multisets of epistemic states. Third, we extend the set of rational postulates in order to consider the epistemic versions of the classical postulates of social choice theory: standard domain, Pareto property, independence of irrelevant alternatives and absence of dictator. These epistemic versions of social postulates are given, essentially, in terms of the finite propositional logic. We state some representation theorems for these operators. These extensions and representation theorems allow us to establish an epistemic and very general version of Arrow's impossibility theorem. One of the interesting features of our result, is that it holds for different representations of epistemic states; for instance conditionals, ordinal conditional functions and, of course, total preorders.

      PubDate: 2017-07-02T13:12:00Z
      DOI: 10.1016/j.artint.2017.06.003
  • Understanding the Complexity of Axiom Pinpointing in Lightweight
           Description Logics
    • Authors: Rafael Peñaloza; Barış Sertkaya
      Abstract: Publication date: Available online 17 June 2017
      Source:Artificial Intelligence
      Author(s): Rafael Peñaloza, Barış Sertkaya
      Lightweight description logics are knowledge representation formalisms characterised by the low complexity of their standard reasoning tasks. They have been successfully employed for constructing large ontologies that model domain knowledge in several different practical applications. In order to maintain these ontologies, it is often necessary to detect the axioms that cause a given consequence. This task is commonly known as axiom pinpointing. In this paper, we provide a thorough analysis of the complexity of several decision, counting, and enumeration problems associated to axiom pinpointing in lightweight description logics.

      PubDate: 2017-06-22T03:33:40Z
      DOI: 10.1016/j.artint.2017.06.002
  • A Progression Semantics for First-Order Logic Programs
    • Authors: Yi Zhou; Yan Zhang
      Abstract: Publication date: Available online 9 June 2017
      Source:Artificial Intelligence
      Author(s): Yi Zhou, Yan Zhang
      In this paper, we propose a progression semantics for first-order normal logic programs, and show that it is equivalent to the well-known stable model (answer set) semantics. The progressional definition sheds new insights into Answer Set Programming (ASP), for instance, its relationships to Datalog, First-Order Logic (FOL) and Satisfiability Modulo Theories (SMT). As an example, we extend the notion of boundedness in Datalog for ASP, and show that it coincides with the notions of recursion-freeness and loop-freeness under program equivalence. In addition, we prove that boundedness precisely captures first-order definability for normal logic programs on arbitrary structures. Finally, we show that the progressional definition suggests an alternative translation from ASP to SMT, which yields a new way of implementing first-order ASP.

      PubDate: 2017-06-12T01:05:42Z
      DOI: 10.1016/j.artint.2017.06.001
  • Discovering visual concept structure with sparse and incomplete tags
    • Authors: Jingya Wang; Xiatian Zhu; Shaogang Gong
      Abstract: Publication date: Available online 31 May 2017
      Source:Artificial Intelligence
      Author(s): Jingya Wang, Xiatian Zhu, Shaogang Gong
      Discovering automatically the semantic structure of tagged visual data (e.g. web videos and images) is important for visual data analysis and interpretation, enabling the machine intelligence for effectively processing the fast-growing amount of multi-media data. However, this is non-trivial due to the need for jointly learning underlying correlations between heterogeneous visual and tag data. The task is made more challenging by inherently sparse and incomplete tags. In this work, we develop a method for modelling the inherent visual data concept structures based on a novel Hierarchical-Multi-Label Random Forest model capable of correlating structured visual and tag information so as to more accurately interpret the visual semantics, e.g. disclosing meaningful visual groups with similar high-level concepts, and recovering missing tags for individual visual data samples. Specifically, our model exploits hierarchically structured tags of different semantic abstractness and multiple tag statistical correlations in addition to modelling visual and tag interactions. As a result, our model is able to discover more accurate semantic correlation between textual tags and visual features, and finally providing favourable visual semantics interpretation even with highly sparse and incomplete tags. We demonstrate the advantages of our proposed approach in two fundamental applications, visual data clustering and missing tag completion, on benchmarking video (i.e. TRECVID MED 2011) and image (i.e. NUS-WIDE) datasets.

      PubDate: 2017-06-02T09:00:03Z
      DOI: 10.1016/j.artint.2017.05.002
  • Low-rank decomposition meets kernel learning: A generalized Nyström
    • Authors: Liang Lan; Kai Zhang; Hancheng Ge; Wei Cheng; Jun Liu; Andreas Rauber; Xiao-Li Li; Jun Wang; Hongyuan Zha
      Abstract: Publication date: Available online 15 May 2017
      Source:Artificial Intelligence
      Author(s): Liang Lan, Kai Zhang, Hancheng Ge, Wei Cheng, Jun Liu, Andreas Rauber, Xiao-Li Li, Jun Wang, Hongyuan Zha
      Low-rank matrix decomposition and kernel learning are two useful techniques in building advanced learning systems. Low-rank decomposition can greatly reduce the computational cost of manipulating large kernel matrices. However, existing approaches are mostly unsupervised and do not incorporate side information such as class labels, making the decomposition less effective for a specific learning task. On the other hand, kernel learning techniques aim at constructing kernel matrices whose structure is well aligned with the learning target, which improves the generalization performance of kernel methods. However, most kernel learning approaches are computationally very expensive. To obtain the advantages of both techniques and address their limitations, in this paper we propose a novel kernel low-rank decomposition formulation called the generalized Nyström method. Our approach inherits the linear time and space complexity via matrix decomposition, while at the same time fully exploits (partial) label information in computing task-dependent decomposition. In addition, the resultant low-rank factors can generalize to arbitrary new samples, rendering great flexibility in inductive learning scenarios. We further extend the algorithm to a multiple kernel learning setup. The experimental results on semi-supervised classification demonstrate the usefulness of the proposed method.

      PubDate: 2017-05-18T08:47:00Z
      DOI: 10.1016/j.artint.2017.05.001
  • Strategy-proof School Choice Mechanisms with Minimum Quotas and Initial
    • Authors: Naoto Hamada; Chia-Ling Hsu; Ryoji Kurata; Takamasa Suzuki; Suguru Ueda; Makoto Yokoo
      Abstract: Publication date: Available online 28 April 2017
      Source:Artificial Intelligence
      Author(s): Naoto Hamada, Chia-Ling Hsu, Ryoji Kurata, Takamasa Suzuki, Suguru Ueda, Makoto Yokoo
      We consider a school choice program where minimum quotas are imposed for each school, i.e., a school must be assigned at least a certain number of students to operate. We require that the obtained matching must respect the initial endowments, i.e., each student must be assigned to a school that is at least as good as her initial endowment school. Although minimum quotas are relevant in school choice programs and strategy-proofness is important to many policymakers, few existing mechanisms simultaneously achieve both. One difficulty is that no strategy-proof mechanism exists that is both efficient and fair under the presence of minimum quotas. Furthermore, existing mechanisms require that all students consider all schools acceptable to obtain a feasible matching that respects minimum quotas. This assumption is unrealistic in a school choice program. We consider the environment where a student considers her initial endowment school acceptable and the initial endowments satisfy all the minimum quotas. We develop two strategy-proof mechanisms. One mechanism, which we call the Top Trading Cycles among Representatives with Supplementary Seats (TTCR-SS), is based on the Top Trading Cycles (TTC) mechanism and is significantly extended to handle the supplementary seats of schools while respecting minimum quotas. TTCR-SS is Pareto efficient. The other mechanism, which we call Priority List-based Deferred Acceptance with Minimum Quotas (PLDA-MQ), is based on the Deferred Acceptance (DA) mechanism. PLDA-MQ is fair, satisfies a concept called Priority List-based (PL-) stability, and obtains the student-optimal matching within all PL-stable matchings. Our simulation results show that our new mechanisms are significantly better than simple extensions of the existing mechanisms.

      PubDate: 2017-05-02T21:41:18Z
      DOI: 10.1016/j.artint.2017.04.006
  • Constrained coalition formation on valuation structures: Formal framework,
           applications, and islands of tractability
    • Authors: Gianluigi Greco; Antonella Guzzo
      Abstract: Publication date: Available online 21 April 2017
      Source:Artificial Intelligence
      Author(s): Gianluigi Greco, Antonella Guzzo
      Coalition structure generation is the problem of partitioning the agents of a given environment into disjoint and exhaustive coalitions so that the whole available worth is maximized. While this problem has been classically studied in settings where all coalitions are allowed to form, it has been recently reconsidered in the literature moving from the observation that environments often forbid the formation of certain coalitions. By following this latter perspective, a model for coalition structure generation is proposed where constraints of two different kinds can be expressed simultaneously. Indeed, the model is based on the concept of valuation structure, which consists of a set of pivotal agents that are pairwise incompatible, plus an interaction graph prescribing that a coalition C can form only if the subgraph induced over the nodes/agents in C is connected. It is shown that valuation structures can be used to model a number of relevant problems arising in real-world application domains. Then, the complexity of coalition structure generation over valuation structures is studied, by assuming that the functions associating each coalition with its worth are given as input according to some compact encoding—rather than explicitly listing all exponentially-many associations. In particular, islands of tractability are identified based on the topological properties of the underlying interaction graphs and on suitable algebraic properties of the given worth functions. Finally, stability issues over valuation structures are studied too, by considering the core as the prototypical solution concept.

      PubDate: 2017-04-26T11:43:34Z
      DOI: 10.1016/j.artint.2017.04.005
  • Thick Set Inversion
    • Authors: B. Desrochers; L. Jaulin
      Abstract: Publication date: Available online 20 April 2017
      Source:Artificial Intelligence
      Author(s): B. Desrochers, L. Jaulin
      This paper deals with the set inversion problem X = f − 1 ( Y ) in the case where the function f : R n → R m and the set Y are both uncertain. The uncertainty is treated under the form of intervals. More precisely, for all x, f ( x ) is inside the box [ f ] ( x ) and the uncertain set Y is bracketed between an inner set Y ⊂ and an outer set Y ⊃ . The introduction of new tools such as thick intervals and thick boxes will allow us to propose an efficient algorithm that handles the uncertainty of sets in an elegant and efficient manner. Some elementary test-cases that cannot be handled easily and properly by existing methods show the efficiency of the approach.

      PubDate: 2017-04-26T11:43:34Z
      DOI: 10.1016/j.artint.2017.04.004
  • From model checking to equilibrium checking: Reactive modules for rational
    • Authors: Julian Gutierrez; Paul Harrenstein; Michael Wooldridge
      Abstract: Publication date: Available online 12 April 2017
      Source:Artificial Intelligence
      Author(s): Julian Gutierrez, Paul Harrenstein, Michael Wooldridge
      Model checking is the best-known and most successful approach to formally verifying that systems satisfy specifications, expressed as temporal logic formulae. In this article, we develop the theory of equilibrium checking, a related but distinct problem. Equilibrium checking is relevant for multi-agent systems in which system components (agents) are assumed to be acting rationally in pursuit of delegated goals, and is concerned with understanding what temporal properties hold of such systems under the assumption that agents select strategies in equilibrium. The formal framework we use to study this problem assumes agents are modelled using Reactive Modules, a system modelling language that is used in a range of practical model checking systems. Each agent (or player) in a Reactive Modules game is specified as a nondeterministic guarded command program, and each player's goal is specified with a temporal logic formula that the player desires to see satisfied. A strategy for a player in a Reactive Modules game defines how that player selects enabled guarded commands for execution over successive rounds of the game. For this general setting, we investigate games in which players have goals specified in Linear Temporal Logic (in which case it is assumed that players choose deterministic strategies) and in Computation Tree Logic (in which case players select nondeterministic strategies). For each of these cases, after formally defining the game setting, we characterise the complexity of a range of problems relating to Nash equilibria (e.g., the computation or the verification of existence of a Nash equilibrium or checking whether a given temporal formula is satisfied on some Nash equilibrium). We then go on to show how the model we present can be used to encode, for example, games in which the choices available to players are specified using STRIPS planning operators.

      PubDate: 2017-04-19T11:34:46Z
      DOI: 10.1016/j.artint.2017.04.003
  • On the Logical Properties of the Nonmonotonic Description Logic DLN
    • Authors: P.A. Bonatti; L. Sauro
      Abstract: Publication date: Available online 7 April 2017
      Source:Artificial Intelligence
      Author(s): P.A. Bonatti, L. Sauro
      DL N is a recent nonmonotonic description logic, designed for satisfying independently proposed knowledge engineering requirements, and for removing some recurrent drawbacks of traditional nonmonotonic semantics. In this paper we study the logical properties of DL N and illustrate some of the relationships between the KLM postulates and the characteristic features of DL N , including its novel way of dealing with unresolved conflicts between defeasible axioms. Moreover, we fix a problem affecting the original semantics of DL N and accordingly adapt the reduction from DL N inferences to classical inferences. Along the paper, we use various versions of the KLM postulates to deepen the comparison with related work, and illustrate the different tradeoffs between opposite requirements adopted by each approach.

      PubDate: 2017-04-12T13:56:02Z
      DOI: 10.1016/j.artint.2017.04.001
  • On the Complexity of the Partner Units Decision Problem
    • Authors: Erich Christian Teppan
      Abstract: Publication date: Available online 6 April 2017
      Source:Artificial Intelligence
      Author(s): Erich Christian Teppan
      The partner units problem is an acknowledged hard benchmark problem for the logic programming community with various industrial application fields like CCTV surveillance or railway safety systems. Whereas many complexity results exist for the optimization version of the problem, complexity for the decision variant, which from a practical point of view is more important, is widely unknown. In this article we show that the partner units decision problem is NP-complete in general and also for various subproblems of industrial importance.

      PubDate: 2017-04-12T13:56:02Z
      DOI: 10.1016/j.artint.2017.04.002
  • Commonsense reasoning about containers using radically incomplete
    • Authors: Ernest Davis; Gary Marcus; Noah Frazier-Logue
      Abstract: Publication date: Available online 4 April 2017
      Source:Artificial Intelligence
      Author(s): Ernest Davis, Gary Marcus, Noah Frazier-Logue
      In physical reasoning, humans are often able to carry out useful reasoning based on radically incomplete information. One physical domain that is ubiquitous both in everyday interactions and in many kinds of scientific applications, where reasoning from incomplete information is very common, is the interaction of containers and their contents. We have developed a preliminary knowledge base for qualitative reasoning about containers, expressed in a sorted first-order language of time, geometry, objects, histories, and actions. We have demonstrated that the knowledge suffices to justify a number of commonsense physical inferences, based on very incomplete knowledge.

      PubDate: 2017-04-05T13:11:40Z
      DOI: 10.1016/j.artint.2017.03.004
  • Towards a Science of Integrated AI and Robotics
    • Authors: Kanna Rajan; Alessandro Saffiotti
      Abstract: Publication date: Available online 31 March 2017
      Source:Artificial Intelligence
      Author(s): Kanna Rajan, Alessandro Saffiotti
      The early promise of the impact of machine intelligence did not involve the partitioning of the nascent field of Artificial Intelligence. The founders of AI envisioned the notion of embedded intelligence as being conjoined between perception, reasoning and actuation. Yet over the years the fields of AI and Robotics drifted apart. Practitioners of AI focused on problems and algorithms abstracted from the real world. Roboticists, generally with a background in mechanical and electrical engineering, concentrated on sensori-motor functions. That divergence is slowly being bridged with the maturity of both fields and with the growing interest in autonomous systems. This special issue brings together the state of the art and practice of the emergent field of integrated AI and Robotics, and highlights the key areas along which this current evolution of machine intelligence is heading.

      PubDate: 2017-04-05T13:11:40Z
      DOI: 10.1016/j.artint.2017.03.003
  • How many diagnoses do we need?
    • Authors: Roni Stern; Meir Kalech; Shelly Rogov; Alexander Feldman
      Abstract: Publication date: Available online 8 March 2017
      Source:Artificial Intelligence
      Author(s): Roni Stern, Meir Kalech, Shelly Rogov, Alexander Feldman
      A known limitation of many diagnosis algorithms is that the number of diagnoses they return can be very large. This is both time consuming and not very helpful from the perspective of a human operator: presenting hundreds of diagnoses to a human operator (charged with repairing the system) is meaningless. In various settings, including decision support for a human operator and automated troubleshooting processes, it is sufficient to be able to answer a basic diagnostic question: is a given component faulty? We propose a way to aggregate an arbitrarily large set of diagnoses to return an estimate of the likelihood of a given component to be faulty. The resulting mapping of components to their likelihood of being faulty is called the system's health state. We propose two metrics for evaluating the accuracy of a health state and show that an accurate health state can be found without finding all diagnoses. An empirical study explores the question of how many diagnoses are needed to obtain an accurate enough health state, and an online stopping criteria is proposed.

      PubDate: 2017-03-10T01:41:18Z
      DOI: 10.1016/j.artint.2017.03.002
  • Efficiency and complexity of price competition among single-product
    • Authors: Ioannis Caragiannis; Xenophon Chatzigeorgiou; Panagiotis Kanellopoulos; George A. Krimpas; Nikos Protopapas; Alexandros A. Voudouris
      Abstract: Publication date: Available online 8 March 2017
      Source:Artificial Intelligence
      Author(s): Ioannis Caragiannis, Xenophon Chatzigeorgiou, Panagiotis Kanellopoulos, George A. Krimpas, Nikos Protopapas, Alexandros A. Voudouris
      Motivated by recent progress on pricing in the AI literature, we study marketplaces that contain multiple vendors offering identical or similar products and unit-demand buyers with different valuations on these vendors. The objective of each vendor is to set the price of its product to a fixed value so that its profit is maximized. The profit depends on the vendor's price itself and the total volume of buyers that find the particular price more attractive than the price of the vendor's competitors. We model the behaviour of buyers and vendors as a two-stage full-information game and study a series of questions related to the existence, efficiency (price of anarchy) and computational complexity of equilibria in this game. To overcome situations where equilibria do not exist or exist but are highly inefficient, we consider the scenario where some of the vendors are subsidized in order to keep prices low and buyers highly satisfied.

      PubDate: 2017-03-10T01:41:18Z
      DOI: 10.1016/j.artint.2017.03.001
  • Characterizing causal action theories and their implementations in answer
           set programming
    • Authors: Haodi Zhang; Fangzhen Lin
      Abstract: Publication date: Available online 2 March 2017
      Source:Artificial Intelligence
      Author(s): Haodi Zhang, Fangzhen Lin
      We consider a simple language for writing causal action theories, and postulate several properties for the state transition models of these theories. We then consider some possible embeddings of these causal action theories in some other action formalisms, and their implementations in logic programs with answer set semantics. In particular, we propose to consider what we call permissible translations from these causal action theories to logic programs. We identify two sets of properties, and prove that for each set, there is only one permissible translation, under strong equivalence, that can satisfy all properties in the set. We also show that these two sets of conditions are minimal in that removing any condition from each of them will result in multiple permissible mappings. Furthermore, as it turns out, for one set, the unique permissible translation is essentially the same as Balduccini and Gelfond's translation from Gelfond and Lifschitz's action language B to logic programs. For the other, it is essentially the same as Lifschitz and Turner's translation from the action language C to logic programs. This work provides a new perspective on understanding, evaluating and comparing action languages by using sets of properties instead of examples. The results in this paper provide a characterization of two representative action languages B and C in terms of permissible mappings from our causal action theories to logic programs. It will be interesting to see if other action languages can be similarly characterized, and whether new action formalisms can be defined using different sets of properties.

      PubDate: 2017-03-04T14:40:36Z
      DOI: 10.1016/j.artint.2017.02.008
School of Mathematical and Computer Sciences
Heriot-Watt University
Edinburgh, EH14 4AS, UK
Tel: +00 44 (0)131 4513762
Fax: +00 44 (0)131 4513327
Home (Search)
Subjects A-Z
Publishers A-Z
Your IP address:
About JournalTOCs
News (blog, publications)
JournalTOCs on Twitter   JournalTOCs on Facebook

JournalTOCs © 2009-2016