Journal Cover
Artificial Intelligence
Journal Prestige (SJR): 0.88
Citation Impact (citeScore): 4
Number of Followers: 218  
 
  Hybrid Journal Hybrid journal (It can contain Open Access articles)
ISSN (Print) 0004-3702
Published by Elsevier Homepage  [3184 journals]
  • Approximate verification of strategic abilities under imperfect
           information
    • Abstract: Publication date: Available online 11 September 2019Source: Artificial IntelligenceAuthor(s): Wojciech Jamroga, Michał Knapik, Damian Kurpiewski, Łukasz Mikulski Model checking of strategic ability under imperfect information is known to be hard. The complexity results range from NP-completeness to undecidability, depending on the precise setup of the problem. No less importantly, the usual fixpoint equivalences do not hold for imperfect information strategies, which seriously hampers incremental synthesis of winning strategies. In this paper, we propose translations of ATLir formulae that provide lower and upper bounds for their truth values, and are cheaper to verify than the original specifications. Most interestingly, the lower approximation is provided by a fixpoint expression that uses a nonstandard variant of the next-step ability operator. We show the correctness of the translations, establish their computational complexity, and validate the approach by experiments with several benchmarks, including a scalable scenario of Bridge play. We also demonstrate that the approximations leave much room for optimizations; in particular, optimizing the data structures can produce a significant speedup. Finally, we show that our fixpoint approximations of ATLir formulae can be combined with under- and overapproximations of models in the vein of may/must abstractions, providing very promising experimental results.
       
  • Natural Strategic Ability
    • Abstract: Publication date: Available online 4 September 2019Source: Artificial IntelligenceAuthor(s): Wojciech Jamroga, Vadim Malvone, Aniello Murano In game theory, as well as in the semantics of game logics, a strategy can be represented by any function from states of the game to the agent's actions. That makes sense from the mathematical point of view, but not necessarily in the context of human behavior. This is because humans are quite bad at executing complex plans, and rather unlikely to come up with such plans in the first place. A similar concern applies to artificial agents with limited memory and/or computational power. In this paper, we adopt the view of bounded rationality, and look at “simple” strategies in specification of agents' abilities. We formally define what “simple” means, and propose a variant of alternating-time temporal logic that takes only such strategies into account. We also study the model checking problem for the resulting semantics of ability.After that, we turn to the broader issue of natural strategic abilities in concurrent games with LTL-definable winning conditions, and study a number of decision problems based on surely winning and Nash equilibrium. We show that, by adopting the view of bounded rationality based on natural strategies, we significantly decrease the complexity of rational verification for multi-agent systems.
       
  • Exploiting Reverse Target-Side Contexts for Neural Machine Translation via
           Asynchronous Bidirectional Decoding
    • Abstract: Publication date: Available online 4 September 2019Source: Artificial IntelligenceAuthor(s): Jinsong Su, Xiangwen Zhang, Qian Lin, Yue Qin, Junfeng Yao, Yang Liu Based on a unified encoder-decoder framework with attentional mechanism, neural machine translation (NMT) models have attracted much attention and become the mainstream in the community of machine translation. Generally, the NMT decoders produce translation in a left-to-right way. As a result, only left-to-right target-side contexts from the generated translations are exploited, while the right-to-left target-side contexts are completely unexploited for translation. In this paper, we extend the conventional attentional encoder-decoder NMT framework by introducing a backward decoder, in order to explore asynchronous bidirectional decoding for NMT. In the first step after encoding, our backward decoder learns to generate the target-side hidden states in a right-to-left manner. Next, in each timestep of translation prediction, our forward decoder concurrently considers both the source-side and the reverse target-side hidden states via two attention models. Compared with previous models, the innovation in this architecture enables our model to fully exploit contexts from both source side and target side, which improve translation quality altogether. We conducted experiments on NIST Chinese-English, WMT English-German and Finnish-English translation tasks to investigate the effectiveness of our model. Experimental results show that (1) our improved RNN-based NMT model achieves significant improvements over the conventional RNNSearch by 1.44/-3.02, 1.11/-1.01, and 1.23/-1.27 average BLEU and TER points, respectively; and (2) our enhanced Transformer outperforms the standard Transformer by 1.56/-1.49, 1.76/-2.49, and 1.29/-1.33 average BLEU and TER points, respectively. We released our code at https://github.com/DeepLearnXMU/ABD-NMT.
       
  • Democratic Fair Allocation of Indivisible Goods
    • Abstract: Publication date: Available online 3 September 2019Source: Artificial IntelligenceAuthor(s): Erel Segal-Halevi, Warut Suksompong We study the problem of fairly allocating indivisible goods to groups of agents. Agents in the same group share the same set of goods even though they may have different preferences. Previous work has focused on unanimous fairness, in which all agents in each group must agree that their group's share is fair. Under this strict requirement, fair allocations exist only for small groups. We introduce the concept of democratic fairness, which aims to satisfy a certain fraction of the agents in each group. This concept is better suited to large groups such as cities or countries. We present protocols for democratic fair allocation among two or more arbitrarily large groups of agents with monotonic, additive, or binary valuations. For two groups with arbitrary monotonic valuations, we give an efficient protocol that guarantees envy-freeness up to one good for at least 1/2 of the agents in each group, and prove that the 1/2 fraction is optimal. We also present other protocols that make weaker fairness guarantees to more agents in each group, or to more groups. Our protocols combine techniques from different fields, including combinatorial game theory, cake cutting, and voting.
       
  • Optimal cruiser-drone traffic enforcement under energy limitation
    • Abstract: Publication date: Available online 2 September 2019Source: Artificial IntelligenceAuthor(s): Ariel Rosenfeld, Oleg Maksimov Drones can assist in mitigating traffic accidents by deterring reckless drivers, leveraging their flexible mobility. In the real-world, drones are fundamentally limited by their battery/fuel capacity and have to be replenished during long operations. In this article, we propose a novel approach where police cruisers act as mobile replenishment providers in addition to their traffic enforcement duties. We propose a binary integer linear program for determining the optimal rendezvous cruiser-drone enforcement policy, which guarantees that all drones are replenished on time and minimizes the likelihood of accidents. In an extensive empirical evaluation, we first show that human drivers are expected to react to traffic enforcement drones similar to how they react to police cruisers, using a first-of-its-kind human study in realistic simulated driving. Then, we show that our proposed approach significantly outperforms the common practice of constructing stationary replenishment installations using both synthetic and real-world road networks. Finally, we propose and evaluate a novel optimization speedup method for mitigating the increased runtime of our proposed approach.
       
  • Coevolutionary systems and PageRank
    • Abstract: Publication date: Available online 30 August 2019Source: Artificial IntelligenceAuthor(s): S.Y. Chong, P. Tiňo, J. He Coevolutionary systems have been used successfully in various problem domains involving situations of strategic decision-making. Central to these systems is a mechanism whereby finite populations of agents compete for reproduction and adapt in response to their interaction outcomes. In competitive settings, agents choose which solutions to implement and outcomes from their behavioral interactions express preferences between the solutions. Recently, we have introduced a framework that provides both qualitative and quantitative characterizations of competitive coevolutionary systems. Its two main features are: (1) A directed graph (digraph) representation that fully captures the underlying structure arising from pairwise preferences over solutions. (2) Coevolutionary processes are modelled as random walks on the digraph. However, one needs to obtain prior, qualitative knowledge of the underlying structures of these coevolutionary digraphs to perform quantitative characterizations on coevolutionary systems and interpret the results. Here, we study a deep connection between coevolutionary systems and PageRank to address this issue. We develop a principled approach to measure and rank the performance (importance) of solutions (vertices) in a given coevolutionary digraph. In PageRank formalism, B transfers part of its authority to A if A dominates B (there is an arc from B to A in the digraph). In this manner, PageRank authority indicates the importance of a vertex. PageRank authorities with suitable normalization have a natural interpretation of long-term visitation probabilities over the digraph by the coevolutionary random walk. We derive closed-form expressions to calculate PageRank authorities for any coevolutionary digraph. We can precisely quantify changes to the authorities due to modifications in restart probability for any coevolutionary system. Our empirical studies demonstrate how PageRank authorities characterize coevolutionary digraphs with different underlying structures.
       
  • Determining Inference Semantics for Disjunctive Logic Programs
    • Abstract: Publication date: Available online 23 August 2019Source: Artificial IntelligenceAuthor(s): Yi-Dong Shen, Thomas Eiter In a seminal paper, Gelfond and Lifschitz (New Generation Computing 9, 365–385, 1991) introduced simple disjunctive logic programs, where in rule heads the disjunction operator “ ” is used to express incomplete information, and defined the answer set semantics (called GL-semantics for short) based on a program transformation (called GL-reduct) and the minimal model requirement. Our observations reveal that the requirement of the GL-semantics, i.e., an answer set should be a minimal model of rules of the GL-reduct, may sometimes be too strong a condition and exclude some answer sets that would be reasonably acceptable. To address this, we present an alternative, more permissive answer set semantics, called the determining inference (DI) semantics. Specifically, we introduce a head selection function to formalize the operator and define answer sets as follows: (i) Given an interpretation I and a selection function sel, we transform a disjunctive program Π into a normal program ΠselI, called a disjunctive program reduct; (ii) given a base answer set semantics X for normal programs, we define I to be a candidate answer set of Π w.r.t. X if I is an answer set of ΠselI under X; and (iii) we define I to be an answer set of Π w.r.t. X if I is a minimal candidate answer set. The DI-semantics is general and applicable to extend any answer set semantics X for normal programs to disjunctive programs. By replacing X with the GLnlp-semantics defined by Gelfond and Lifschitz (1988), we induce a DI-semantics for simple disjunctive programs, and by replacing X with the well-justified semantics defined by Shen et al. (2014), we further induce a DI-semantics for general disjunctive programs. We also establish a novel characterization of the GL-semantics in terms of a disjunctive program reduct, which reveals the essential difference of the DI-semantics from the GL-semantics and leads us to giving a satisfactory solution to the open problem presented by Hitzler and Seda (1999) about characterizing split normal derivatives of a simple disjunctive program Π such that answer sets of the normal derivatives are answer sets of Π under the GL-semantics. Finally we give computational complexity results; in particular we show that in the propositional case deciding whether a simple disjunctive program Π has some DI-answer set is NP-complete. This is in contrast to the GL-semantics and equivalent formulations such as the FLP-semantics (Faber et al., 2011), where deciding whether Π has some answer set is Σ2p-complete, while brave and cautious reasoning are Σ2p- and Π2p-complete, respectively, for both GL- and DI-answer sets. For general disjunctive programs with compound formulas as building blocks, the complexity of brave and cautious reasoning increases under DI-semantics by one level of the polynomial hierarchy, which thus offers higher problem solving capacity.
       
  • Pareto Optimal Allocation under Uncertain Preferences: Uncertainty Models,
           Algorithms, and Complexity
    • Abstract: Publication date: Available online 9 August 2019Source: Artificial IntelligenceAuthor(s): Haris Aziz, Péter Biró, Ronald de Haan, Baharak Rastegari The assignment problem is one of the most well-studied settings in multi-agent resource allocation. Agents express preferences over indivisible items and then the items are allocated based on these preferences. Pareto optimality is regarded as a desirable property for the chosen allocation, requiring that no other allocation exists in which no agent is worse off and at least one agent is better of. We consider the assignment problem with the additional feature that agents' preferences involve uncertainty. The setting with uncertainty leads to a number of interesting questions including the following ones. How to compute an assignment with the highest probability of being Pareto optimal' What is the complexity of computing the probability that a given assignment is Pareto optimal' Does there exist an assignment that is Pareto optimal with probability one' We consider these problems under five natural uncertainty models. For all of the models, we present a number of algorithmic and complexity results highlighting the differences and similarities in the complexity of the models. We also present some general characterization and algorithmic results that apply to large classes of uncertainty models.
       
  • A Set of New Multi- and Many-objective Test Problems for Continuous
           Optimization and a Comprehensive Experimental Evaluation
    • Abstract: Publication date: Available online 9 August 2019Source: Artificial IntelligenceAuthor(s): Yuren Zhou, Xiaoyu He, Yi Xiang, Shaowei Cai Multi- and many-objective optimization problems have wide applications in the real world, and they have received growing attention from the evolutionary computation community. To promote the algorithm development in this area, numerous studies have been devoted to designing multi- and many-objective test problems. Most of these studies focus on handling complicated Pareto fronts (PFs), and the impact of the Pareto sets (PSs) has not been well-studied, although complicated PSs are prevalent in the real world. This paper presents a set of scalable test problems according to a new principle, which considers the geometrical properties of both PF and PS. A position function with a spherical form is proposed to introduce non-linear variable dependences to the PS, so as to simulate the variable dependencies in the real-world problems. According to the proposed principle, the first m (i.e., the number of objectives) decision variables are used to form the surface of a unit hypersphere, while the rest variables are designed to optimize a certain distance function. A set of test problems are generated by the proposed principle, which are then used to investigate six representative algorithms. The experimental results indicate that the proposed test problems pose considerable difficulties to existing algorithms, calling for the need for designing new algorithms capable of handling complicated PF and PS simultaneously.
       
  • Distributed monitoring of election winners
    • Abstract: Publication date: Available online 5 August 2019Source: Artificial IntelligenceAuthor(s): Arnold Filtser, Nimrod Talmon We consider distributed elections, where there is a center and k sites. In such distributed elections, each voter has preferences over some set of candidates, and each voter is assigned to exactly one site such that each site is aware only of the voters assigned to it. The center is able to directly communicate with all sites. We are interested in designing communication-efficient protocols, allowing the center to maintain a candidate which, with arbitrarily high probability, is guaranteed to be a winner, or at least close to being a winner. We consider various single-winner voting rules, such as variants of Approval voting and scoring rules, tournament-based voting rules, and several round-based voting rules. For the voting rules we consider, we show that, using communication which is logarithmic in the number of voters, it is possible for the center to maintain such approximate winners; that is, upon a query at any time the center can immediately return a candidate which is guaranteed to be an approximate winner with high probability. We complement our protocols with lower bounds. Our results are theoretical in nature and relate to various scenarios, such as aggregating customer preferences in online shopping websites or supermarket chains and collecting votes from different polling stations of political elections.
       
  • Knowing-how under uncertainty
    • Abstract: Publication date: Available online 28 June 2019Source: Artificial IntelligenceAuthor(s): Pavel Naumov, Jia Tao Logical systems containing knowledge and know-how modalities have been investigated in several recent works. Independently, epistemic modal logics in which every knowledge modality is labeled with a degree of uncertainty have been proposed. This article combines these two research lines by introducing a bimodal logic containing knowledge and know-how modalities, both labeled with a degree of uncertainty. The main technical results are soundness, completeness, and incompleteness of the proposed logical system with respect to two classes of semantics.
       
 
 
JournalTOCs
School of Mathematical and Computer Sciences
Heriot-Watt University
Edinburgh, EH14 4AS, UK
Email: journaltocs@hw.ac.uk
Tel: +00 44 (0)131 4513762
Fax: +00 44 (0)131 4513327
 
Home (Search)
Subjects A-Z
Publishers A-Z
Customise
APIs
Your IP address: 100.26.182.28
 
About JournalTOCs
API
Help
News (blog, publications)
JournalTOCs on Twitter   JournalTOCs on Facebook

JournalTOCs © 2009-