text:
18},
issue_date = {May 2018},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {62},
number = {1},
issn = {1076-9757},
url = {https://doi.org/10.1613/jair.1.11227},
doi = {10.1613/jair.1.11227},
abstract = {Finite State Controllers (FSCs) are an effective way to compactly represent sequential plans. By imposing appropriate conditions on transitions, FSCs can also represent generalized plans (plans that solve a range of planning problems from a given domain). In this paper we introduce the concept of hierarchical FSCs for planning by allowing controllers to call other controllers. This call mechanism allows hierarchical FSCs to represent generalized plans more compactly than individual FSCs, to compute controllers in a modular fashion or even more, to compute recursive controllers. The paper introduces a classical planning compilation for computing hierarchical FSCs that solve challenging generalized planning tasks. The compilation takes as input a finite set of classical planning problems from a given domain. The output of the compilation is a single classical planning problem whose solution induces: (1) a hierarchical FSC and (2), the corresponding validation of that controller on the input classical planning problems.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {755–797},
numpages = {43}
}

@article{10.1613/jair.1.11222,
author = {Grace, Katja and Salvatier, John and Dafoe, Allan and Zhang, Baobao and Evans, Owain},
title = {Viewpoint: When Will AI Exceed Human Performance? Evidence from AI Experts},
year = {2018},
issue_date = {May 2018},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {62},
number = {1},
issn = {1076-9757},
url = {https://doi.org/10.1613/jair.1.11222},
doi = {10.1613/jair.1.11222},
abstract = {Advances in artificial intelligence (AI) will transform modern life by reshaping transportation, health, science, finance, and the military. To adapt public policy, we need to better anticipate these advances. Here we report the results from a large survey of machine learning researchers on their beliefs about progress in AI. Researchers predict AI will outperform humans in many activities in the next ten years, such as translating languages (by 2024), writing high-school essays (by 2026), driving a truck (by 2027), working in retail (by 2031), writing a bestselling book (by 2049), and working as a surgeon (by 2053). Researchers believe there is a 50% chance of AI outperforming humans in all tasks in 45 years and of automating all human jobs in 120 years, with Asian respondents expecting these dates much sooner than North Americans. These results will inform discussion amongst researchers and policymakers about anticipating and managing trends in AI.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {729–754},
numpages = {26}
}

@article{10.1613/jair.1.11221,
author = {Eiter, Thomas and Kaminski, Tobias and Redl, Christoph and Weinzierl, Antonius},
title = {Exploiting Partial Assignments for Efficient Evaluation of Answer Set Programs with External Source Access},
year = {2018},
issue_date = {May 2018},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {62},
number = {1},
issn = {1076-9757},
url = {https://doi.org/10.1613/jair.1.11221},
doi = {10.1613/jair.1.11221},
abstract = {Answer Set Programming (ASP) is a well-known declarative problem solving approach based on nonmonotonic logic programs, which has been successfully applied to a wide range of applications in artificial intelligence and beyond. To address the needs of modern applications, HEX-programs were introduced as an extension of ASP with external atoms for accessing information outside programs via an API style bi-directional interface mechanism. To evaluate such programs, conflict-driving learning algorithms for SAT and ASP solving have been extended in order to capture the semantics of external atoms. However, a drawback of the state-of-the-art approach is that external atoms are only evaluated under complete assignments (i.e., input to the external source) while in practice, their values often can be determined already based on partial assignments alone (i.e., from incomplete input to the external source). This prevents early backtracking in case of conflicts, and hinders more efficient evaluation of HEX-programs. We thus extend the notion of external atoms to allow for three-valued evaluation under partial assignments, while the two-valued semantics of the overall HEX-formalism remains unchanged. This paves the way for three enhancements: first, to evaluate external sources at any point during model search, which can trigger learning knowledge about the source behavior and/or early backtracking in the spirit of theory propagation in SAT modulo theories (SMT). Second, to optimize the knowledge learned in terms of so-called nogoods, which roughly speaking are impossible input-output configurations. Shrinking nogoods to their relevant input part leads to more effective search space pruning. And third, to make a necessary minimality check of candidate answer sets more efficient by exploiting early external evaluation calls. As this check usually accounts for a large share of the total runtime, optimization is here particularly important. We further present an experimental evaluation of an implementation of a novel HEX-algorithm that incorporates these enhancements using a benchmark suite. Our results demonstrate a clear efficiency gain over the state-of-the-art HEX-solver for the benchmarks, and provide insights regarding the most effective combinations of solver configurations.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {665–727},
numpages = {63}
}

@article{10.1613/jair.1.11219,
author = {Fern\'{a}ndez-Gonz\'{a}lez, Enrique and Williams, Brian and Karpas, Erez},
title = {ScottyActivity: Mixed Discrete-Continuous Planning with Convex Optimization},
year = {2018},
issue_date = {May 2018},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {62},
number = {1},
issn = {1076-9757},
url = {https://doi.org/10.1613/jair.1.11219},
doi = {10.1613/jair.1.11219},
abstract = {The state of the art practice in robotics planning is to script behaviors manually, where each behavior is typically generated using trajectory optimization. However, in order for robots to be able to act robustly and adapt to novel situations, they need to plan these activity sequences autonomously. Since the conditions and effects of these behaviors are tightly coupled through time, state and control variables, many problems require that the tasks of activity planning and trajectory optimization are considered together. There are two key issues underlying effective hybrid activity and trajectory planning: the sufficiently accurate modeling of robot dynamics and the capability of planning over long horizons. Hybrid activity and trajectory planners that employ mixed integer programming within a discrete time formulation are able to accurately model complex dynamics for robot vehicles, but are often restricted to relatively short horizons. On the other hand, current hybrid activity planners that employ continuous time formulations can handle longer horizons but they only allow actions to have continuous effects with constant rate of change, and restrict the allowed state constraints to linear inequalities. This is insufficient for many robotic applications and it greatly limits the expressivity of the problems that these approaches can solve. In this work we present the ScottyActivity planner, that is able to generate practical hybrid activity and motion plans over long horizons by employing recent methods in convex optimization combined with methods for planning with relaxed plan graphs and heuristic forward search. Unlike other continuous time planners, ScottyActivity can solve a broad class of robotic planning problems by supporting convex quadratic constraints on state variables and control variables that are jointly constrained and that affect multiple state variables simultaneously. In order to support planning over long horizons, ScottyActivity does not resort to time, state or control variable discretization. While straightforward formulations of consistency checks are not convex and do not scale, we present an efficient convex formulation, in the form of a Second Order Cone Program (SOCP), that is very fast to solve. We also introduce several new realistic domains that demonstrate the capabilities and scalability of our approach, and their simplified linear versions, that we use to compare with other state of the art planners. This work demonstrates the power of integrating advanced convex optimization techniques with discrete search methods and paves the way for extensions dealing with non-convex disjoint constraints, such as obstacle avoidance.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {579–664},
numpages = {86}
}

@article{10.1613/jair.1.11217,
author = {Seipp, Jendrik and Helmert, Malte},
title = {Counterexample-Guided Cartesian Abstraction Refinement for Classical Planning},
year = {2018},
issue_date = {May 2018},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {62},
number = {1},
issn = {1076-9757},
url = {https://doi.org/10.1613/jair.1.11217},
doi = {10.1613/jair.1.11217},
abstract = {Counterexample-guided abstraction refinement (CEGAR) is a method for incrementally computing abstractions of transition systems. We propose a CEGAR algorithm for computing abstraction heuristics for optimal classical planning. Starting from a coarse abstraction of the planning task, we iteratively compute an optimal abstract solution, check if and why it fails for the concrete planning task and refine the abstraction so that the same failure cannot occur in future iterations. A key ingredient of our approach is a novel class of abstractions for classical planning tasks that admits efficient and very fine-grained refinement. Since a single abstraction usually cannot capture enough details of the planning task, we also introduce two methods for producing diverse sets of heuristics within this framework, one based on goal atoms, the other based on landmarks. In order to sum their heuristic estimates admissibly we introduce a new cost partitioning algorithm called saturated cost partitioning. We show that the resulting heuristics outperform other state-of-the-art abstraction heuristics in many benchmark domains.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {535–577},
numpages = {43}
}

@article{10.1613/jair.1.11216,
author = {Walraven, Erwin and Spaan, Matthijs T. J.},
title = {Column Generation Algorithms for Constrained POMDPs},
year = {2018},
issue_date = {May 2018},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {62},
number = {1},
issn = {1076-9757},
url = {https://doi.org/10.1613/jair.1.11216},
doi = {10.1613/jair.1.11216},
abstract = {In several real-world domains it is required to plan ahead while there are finite resources available for executing the plan. The limited availability of resources imposes constraints on the plans that can be executed, which need to be taken into account while computing a plan. A Constrained Partially Observable Markov Decision Process (Constrained POMDP) can be used to model resource-constrained planning problems which include uncertainty and partial observability. Constrained POMDPs provide a framework for computing policies which maximize expected reward, while respecting constraints on a secondary objective such as cost or resource consumption. Column generation for linear programming can be used to obtain Constrained POMDP solutions. This method incrementally adds columns to a linear program, in which each column corresponds to a POMDP policy obtained by solving an unconstrained subproblem. Column generation requires solving a potentially large number of POMDPs, as well as exact evaluation of the resulting policies, which is computationally difficult. We propose a method to solve subproblems in a two-stage fashion using approximation algorithms. First, we use a tailored point-based POMDP algorithm to obtain an approximate subproblem solution. Next, we convert this approximate solution into a policy graph, which we can evaluate efficiently. The resulting algorithm is a new approximate method for Constrained POMDPs in single-agent settings, but also in settings in which multiple independent agents share a global constraint. Experiments based on several domains show that our method outperforms the current state of the art.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {489–533},
numpages = {45}
}

@article{10.1613/jair.1.11215,
author = {Fotakis, Dimitris and Krysta, Piotr and Ventre, Carmine},
title = {The Power of Verification for Greedy Mechanism Design},
year = {2018},
issue_date = {May 2018},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {62},
number = {1},
issn = {1076-9757},
url = {https://doi.org/10.1613/jair.1.11215},
doi = {10.1613/jair.1.11215},
abstract = {Greedy algorithms are known to provide, in polynomial time, near optimal approximation guarantees for Combinatorial Auctions (CAs) with multidimensional bidders. It is known that truthful greedy-like mechanisms for CAs with multi-minded bidders do not achieve good approximation guarantees.In this work, we seek a deeper understanding of greedy mechanism design and investigate under which general assumptions, we can have efficient and truthful greedy mechanisms for CAs. Towards this goal, we use the framework of priority algorithms and weak and strong verification, where the bidders are not allowed to overbid on their winning set or on any subset of this set, respectively. We provide a complete characterization of the power of weak verification showing that it is sufficient and necessary for any greedy fixed priority algorithm to become truthful with the use of money or not, depending on the ordering of the bids. Moreover, we show that strong verification is sufficient and necessary to obtain a 2-approximate truthful mechanism with money, based on a known greedy algorithm, for the problem of submodular CAs in finite bidding domains. Our proof is based on an interesting structural analysis of the strongly connected components of the declaration graph.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {459–488},
numpages = {30}
}

@article{10.1613/jair.1.11214,
author = {Alechina, Natasha and Halpern, Joseph Y. and Kash, Ian A. and Logan, Brian},
title = {Incentive-Compatible Mechanisms for Norm Monitoring in Open Multi-Agent Systems},
year = {2018},
issue_date = {May 2018},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {62},
number = {1},
issn = {1076-9757},
url = {https://doi.org/10.1613/jair.1.11214},
doi = {10.1613/jair.1.11214},
abstract = {We consider the problem of detecting norm violations in open multi-agent systems (MAS). We show how, using ideas from scrip systems, we can design mechanisms where the agents comprising the MAS are incentivised to monitor the actions of other agents for norm violations. The cost of providing the incentives is not borne by the MAS and does not come from fines charged for norm violations (fines may be impossible to levy in a system where agents are free to leave and rejoin again under a different identity). Instead, monitoring incentives come from (scrip) fees for accessing the services provided by the MAS. In some cases, perfect monitoring (and hence enforcement) can be achieved: no norms will be violated in equilibrium. In other cases, we show that, while it is impossible to achieve perfect enforcement, we can get arbitrarily close; we can make the probability of a norm violation in equilibrium arbitrarily small. We show using simulations that our theoretical results, which apply to systems with a large number of agents, hold for multi-agent systems with as few as 1000 agents--the system rapidly converges to the steady-state distribution of scrip tokens necessary to ensure monitoring and then remains close to the steady state.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {433–458},
numpages = {26}
}

@article{10.1613/jair.1.11213,
author = {Haslum, Patrik and Ivankovic, Franc and Ram\'{\i}rez, Miquel and Gordon, Dan and Thi\'{e}baux, Sylvie and Shivashankar, Vikas and Nau, Dana S.},
title = {Extending Classical Planning with State Constraints: Heuristics and Search for Optimal Planning},
year = {2018},
issue_date = {May 2018},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {62},
number = {1},
issn = {1076-9757},
url = {https://doi.org/10.1613/jair.1.11213},
doi = {10.1613/jair.1.11213},
abstract = {We present a principled way of extending a classical AI planning formalism with systems of state constraints, which relate - sometimes determine - the values of variables in each state traversed by the plan. This extension occupies an attractive middle ground between expressivity and complexity. It enables modelling a new range of problems, as well as formulating more efficient models of classical planning problems. An example of the former is planning-based control of networked physical systems - power networks, for example - in which a local, discrete control action can have global effects on continuous quantities, such as altering flows across the entire network. At the same time, our extension remains decidable as long as the satisfiability of sets of state constraints is decidable, including in the presence of numeric state variables, and we demonstrate that effective techniques for cost-optimal planning known in the classical setting - in particular, relaxation-based admissible heuristics - can be adapted to the extended formalism. In this paper, we apply our approach to constraints in the form of linear or non-linear equations over numeric state variables, but the approach is independent of the type of state constraints, as long as there exists a procedure that decides their consistency. The planner and the constraint solver interact through a well-defined, narrow interface, in which the solver requires no specialisation to the planning context. Furthermore, we present an admissible search algorithm - a variant of A* - that is able to make use of additional information provided by the search heuristic, in the form of preferred actions. Although preferred actions have been widely used in satisficing planning, we are not aware of any previous use of them in optimal planning.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {373–431},
numpages = {59}
}

@article{10.1613/jair.1.11212,
author = {Botea, Adi and Bonusi, Davide and Surynek, Pavel},
title = {Solving Multi-Agent Path Finding on Strongly Biconnected Digraphs},
year = {2018},
issue_date = {May 2018},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {62},
number = {1},
issn = {1076-9757},
url = {https://doi.org/10.1613/jair.1.11212},
doi = {10.1613/jair.1.11212},
abstract = {Much of the literature on suboptimal, polynomial-time algorithms for multi-agent path finding focuses on undirected graphs, where motion is permitted in both directions along a graph edge. Despite this, traveling on directed graphs is relevant in navigation domains, such as path finding in games, and asymmetric communication networks.We consider multi-agent path finding on strongly biconnected directed graphs. We show that all instances with at least two unoccupied positions have a solution, except for a particular, degenerate subclass where the graph has a cyclic shape. We present diBOX, an algorithm for multi-agent path finding on strongly biconnected directed graphs. diBOX runs in polynomial time, computes suboptimal solutions and is complete for instances on strongly biconnected digraphs with at least two unoccupied positions. We theoretically analyze properties of the algorithm and properties of strongly biconnected directed graphs that are relevant to our approach. We perform a detailed empirical analysis of diBOX, showing a good scalability. To our knowledge, our work is the first study of multi-agent path finding focused on directed graphs.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {273–314},
numpages = {42}
}

@article{10.1613/jair.1.11211,
author = {Bil\`{o}, Vittorio and Fanelli, Angelo and Flammini, Michele and Monaco, Gianpiero and Moscardelli, Luca},
title = {Nash Stable Outcomes in Fractional Hedonic Games: Existence, Efficiency and Computation},
year = {2018},
issue_date = {May 2018},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {62},
number = {1},
issn = {1076-9757},
url = {https://doi.org/10.1613/jair.1.11211},
doi = {10.1613/jair.1.11211},
abstract = {We consider fractional hedonic games, a subclass of coalition formation games that can be succinctly modeled by means of a graph in which nodes represent agents and edge weights the degree of preference of the corresponding endpoints. The happiness or utility of an agent for being in a coalition is the average value she ascribes to its members. We adopt Nash stable outcomes as the target solution concept; that is we focus on states in which no agent can improve her utility by unilaterally changing her own group. We provide existence, efficiency and complexity results for games played on both general and specific graph topologies. As to the efficiency results, we mainly study the quality of the best Nash stable outcome and refer to the ratio between the social welfare of an optimal coalition structure and the one of such an equilibrium as to the price of stability. In this respect, we remark that a best Nash stable outcome has a natural meaning of stability, since it is the optimal solution among the ones which can be accepted by selfish agents. We provide upper and lower bounds on the price of stability for different topologies, both in case of weighted and unweighted edges. Beside the results for general graphs, we give refined bounds for various specific cases, such as triangle-free, bipartite graphs and tree graphs. For these families, we also show how to efficiently compute Nash stable outcomes with provable good social welfare.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {315–371},
numpages = {57}
}

@article{10.1613/jair.1.11210,
author = {Halaweh, Mohanad},
title = {Viewpoint: Artificial Intelligence Government (Gov. 3.0): The UAE Leading Model},
year = {2018},
issue_date = {May 2018},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {62},
number = {1},
issn = {1076-9757},
url = {https://doi.org/10.1613/jair.1.11210},
doi = {10.1613/jair.1.11210},
abstract = {The United Arab Emirates (UAE) is the first country in the world to appoint a State Minister for Artificial Intelligence (AI). The UAE is embracing AI in society at the governmental level, which is leading to a new generations of digital government (which we are labeling Gov. 3.0). This paper argues that the decision to embrace AI will lead to positive impacts on society, including businesses, organizations and individuals, as well as on the AI industry itself. This paper discusses the societal impacts of AI at a macro (country-wide) level.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {269–272},
numpages = {4}
}

@article{10.1613/jair.1.11209,
author = {Hatem, Matthew and Burns, Ethan and Ruml, Wheeler},
title = {Solving Large Problems with Heuristic Search: General-Purpose Parallel External-Memory Search},
year = {2018},
issue_date = {May 2018},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {62},
number = {1},
issn = {1076-9757},
url = {https://doi.org/10.1613/jair.1.11209},
doi = {10.1613/jair.1.11209},
abstract = {Classic best-first heuristic search algorithms, like A*, record every unique state they encounter in RAM, making them infeasible for solving large problems. In this paper, we demonstrate how best-first search can be scaled to solve much larger problems by exploiting disk storage and parallel processing and, in some cases, slightly relaxing the strict best-first node expansion order. Some previous disk-based search algorithms abandon best-first search order in an attempt to increase efficiency. We present two case studies showing that A*, when augmented with Delayed Duplicate Detection, can actually be more efficient than these non-best-first search orders. First, we present a straightforward external variant of A*, called PEDAL, that slightly relaxes best-first order in order to be I/O efficient in both theory and practice, even on problems featuring real-valued node costs. Because it is easy to parallelize, PEDAL can be faster than in-memory IDA* even on domains with few duplicate states, such as the sliding-tile puzzle. Second, we present a variant of PEDAL, called PE2A*, that uses partial expansion to handle problems that have large branching factors. When tested on the problem of Multiple Sequence Alignment, PE2A* is the first algorithm capable of solving the entire Reference Set 1 of the standard BAliBASE benchmark using a biologically accurate cost function. This work shows that classic best-first algorithms like A* can be applied to large real-world problems. We also provide a detailed implementation guide with source code both for generic parallel disk-based best-first search and for Multiple Sequence Alignment with a biologically accurate cost function. Given its effectiveness as a general-purpose problem-solving method, we hope that this makes parallel and disk-based search accessible to a wider audience.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {233–268},
numpages = {36}
}

@article{10.1613/jair.1.11208,
author = {Baier, Hendrik and Winands, Mark H. M.},
title = {MCTS-Minimax Hybrids with State Evaluations},
year = {2018},
issue_date = {May 2018},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {62},
number = {1},
issn = {1076-9757},
url = {https://doi.org/10.1613/jair.1.11208},
doi = {10.1613/jair.1.11208},
abstract = {Monte-Carlo Tree Search (MCTS) has been found to show weaker play than minimax-based search in some tactical game domains. This is partly due to its highly selective search and averaging value backups, which make it susceptible to traps. In order to combine the strategic strength of MCTS and the tactical strength of minimax, MCTS-minimax hybrids have been introduced, embedding shallow minimax searches into the MCTS framework. Their results have been promising even without making use of domain knowledge such as heuristic evaluation functions. This article continues this line of research for the case where evaluation functions are available. Three different approaches are considered, employing minimax with an evaluation function in the rollout phase of MCTS, as a replacement for the rollout phase, and as a node prior to bias move selection. The latter two approaches are newly proposed. Furthermore, all three hybrids are enhanced with the help of move ordering and k-best pruning for minimax. Results show that the use of enhanced minimax for computing node priors results in the strongest MCTS-minimax hybrid investigated in the three test domains of Othello, Breakthrough, and Catch the Lion. This hybrid, called MCTS-IP-M-k, also outperforms enhanced minimax as a standalone player in Breakthrough, demonstrating that at least in this domain, MCTS and minimax can be combined to an algorithm stronger than its parts. Using enhanced minimax for computing node priors is therefore a promising new technique for integrating domain knowledge into an MCTS framework.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {193–231},
numpages = {39}
}

@article{10.1613/jair.1.11206,
author = {Criado, Natalia},
title = {Resource-Bounded Norm Monitoring in Multi-Agent Systems},
year = {2018},
issue_date = {May 2018},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {62},
number = {1},
issn = {1076-9757},
url = {https://doi.org/10.1613/jair.1.11206},
doi = {10.1613/jair.1.11206},
abstract = {Norms allow system designers to specify the desired behaviour of a sociotechnical system. In this way, norms regulate what the social and technical agents in a sociotechnical system should (not) do. In this context, a vitally important question is the development of mechanisms for monitoring whether these agents comply with norms. Proposals on norm monitoring often assume that monitoring has no costs and/or that monitors have unlimited resources to observe the environment and the actions performed by agents. In this paper, we challenge this assumption and propose the first practical resource-bounded norm monitor. Our monitor is capable of selecting the resources to be deployed and use them to check norm compliance with incomplete information about the actions performed and the state of the world. We formally demonstrate the correctness and soundness of our norm monitor and study its complexity. We also demonstrate in randomised simulations and benchmark experiments that our monitor can select monitored resources effectively and efficiently, detecting more norm violations and fulfilments than other tractable optimization approaches and obtaining slightly worse results than intractable optimal approaches.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {153–192},
numpages = {40}
}

@article{10.1613/jair.1.11205,
author = {Bistaffa, Filippo and Farinelli, Alessandro},
title = {A COP Model for Graph-Constrained Coalition Formation},
year = {2018},
issue_date = {May 2018},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {62},
number = {1},
issn = {1076-9757},
url = {https://doi.org/10.1613/jair.1.11205},
doi = {10.1613/jair.1.11205},
abstract = {We consider Graph-Constrained Coalition Formation (GCCF), a widely studied subproblem of coalition formation in which the set of valid coalitions is restricted by a graph. We propose COP-GCCF, a novel approach that models GCCF as a COP, and we solve such COP with a highly-parallel approach based on Bucket Elimination executed on the GPU, which is able to exploit the high constraint tightness of COP-GCCF. Results show that our approach outperforms state of the art algorithms (i.e., DyCE and IDPG) by at least one order of magnitude on realistic graphs, i.e., a crawl of the Twitter social graph, both in terms of runtime and memory.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {133–153},
numpages = {21}
}

@article{10.1613/jair.1.11204,
author = {Apt, Krzysztof R. and Wojtczak, Dominik},
title = {Verification of Distributed Epistemic Gossip Protocols},
year = {2018},
issue_date = {May 2018},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {62},
number = {1},
issn = {1076-9757},
url = {https://doi.org/10.1613/jair.1.11204},
doi = {10.1613/jair.1.11204},
abstract = {Gossip protocols aim at arriving, by means of point-to-point or group communications, at a situation in which all the agents know each other secrets. Distributed epistemic gossip protocols use as guards formulas from a simple epistemic logic and as statements calls between the agents. They are natural examples of knowledge based programs.We prove here that these protocols are implementable, that their partial correctness is decidable and that termination and two forms of fair termination of these protocols are decidable, as well. To establish these results we show that the definition of semantics and of truth of the underlying logic are decidable.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {101–132},
numpages = {32}
}

@article{10.1613/jair.1.11203,
author = {\v{S}ourek, Gustav and Aschenbrenner, Vojt\v{e}ch and \v{Z}elezn\'{y}, Filip and Schockaert, Steven and Ku\v{z}elka, Ond\v{r}ej},
title = {Lifted Relational Neural Networks: Efficient Learning of Latent Relational Structures},
year = {2018},
issue_date = {May 2018},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {62},
number = {1},
issn = {1076-9757},
url = {https://doi.org/10.1613/jair.1.11203},
doi = {10.1613/jair.1.11203},
abstract = {We propose a method to combine the interpretability and expressive power of first-order logic with the effectiveness of neural network learning. In particular, we introduce a lifted framework in which first-order rules are used to describe the structure of a given problem setting. These rules are then used as a template for constructing a number of neural networks, one for each training and testing example. As the different networks corresponding to different examples share their weights, these weights can be efficiently learned using stochastic gradient descent. Our framework provides a exible way for implementing and combining a wide variety of modelling constructs. In particular, the use of first-order logic allows for a declarative specification of latent relational structures, which can then be efficiently discovered in a given data set using neural network learning. Experiments on 78 relational learning benchmarks clearly demonstrate the effectiveness of the framework.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {69–100},
numpages = {32}
}

@article{10.1613/jair.1.11202,
author = {Skibski, Oskar and Michalak, Tomasz P. and Rahwan, Talal},
title = {Axiomatic Characterization of Game-Theoretic Centrality},
year = {2018},
issue_date = {May 2018},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {62},
number = {1},
issn = {1076-9757},
url = {https://doi.org/10.1613/jair.1.11202},
doi = {10.1613/jair.1.11202},
abstract = {One of the fundamental research challenges in network science is centrality analysis, i.e., identifying the nodes that play the most important roles in the network. In this article, we focus on the game-theoretic approach to centrality analysis. While various centrality indices have been recently proposed based on this approach, it is still unknown how general is the game-theoretic approach to centrality and what distinguishes some game-theoretic centralities from others. In this article, we attempt to answer this question by providing the first axiomatic characterization of game-theoretic centralities. Specifically, we show that every possible centrality measure can be obtained following the game-theoretic approach. Furthermore, we study three natural classes of game-theoretic centrality, and prove that they can be characterized by certain intuitive properties pertaining to the well-known notion of Fairness due to Myerson.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {33–68},
numpages = {36}
}

@article{10.1613/jair.1.11201,
author = {Oztok, Umut and Darwiche, Adnan},
title = {An Exhaustive DPLL Algorithm for Model Counting},
year = {2018},
issue_date = {May 2018},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {62},
number = {1},
issn = {1076-9757},
url = {https://doi.org/10.1613/jair.1.11201},
doi = {10.1613/jair.1.11201},
abstract = {State-of-the-art model counters are based on exhaustive DPLL algorithms, and have been successfully used in probabilistic reasoning, one of the key problems in AI. In this article, we present a new exhaustive DPLL algorithm with a formal semantics, a proof of correctness, and a modular design. The modular design is based on the separation of the core model counting algorithm from SAT solving techniques. We also show that the trace of our algorithm belongs to the language of Sentential Decision Diagrams (SDDs), which is a subset of Decision-DNNFs, the trace of existing state-of-the-art model counters. Still, our experimental analysis shows comparable results against state-of-the-art model counters. Furthermore, we obtain the first top-down SDD compiler, and show orders-of-magnitude improvements in SDD construction time against the existing bottom-up SDD compiler.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {1–32},
numpages = {32}
}

@article{10.5555/3241691.3241715,
author = {Costa-juss\`{a}, Marta R.},
title = {From Feature to Paradigm: Deep Learning in Machine Translation},
year = {2018},
issue_date = {January 2018},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {61},
number = {1},
issn = {1076-9757},
abstract = {In the last years, deep learning algorithms have highly revolutionized several areas including speech, image and natural language processing. The specific field of Machine Translation (MT) has not remained invariant. Integration of deep learning in MT varies from re-modeling existing features into standard statistical systems to the development of a new architecture. Among the different neural networks, research works use feedforward neural networks, recurrent neural networks and the encoder-decoder schema. These architectures are able to tackle challenges as having low-resources or morphology variations.This manuscript focuses on describing how these neural networks have been integrated to enhance different aspects and models from statistical MT, including language modeling, word alignment, translation, reordering, and rescoring. Then, we report the new neural MT approach together with a description of the foundational related works and recent approaches on using subword, characters and training with multilingual languages, among others. Finally, we include an analysis of the corresponding challenges and future work in using deep learning in MT.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {947–974},
numpages = {28}
}

@article{10.5555/3241691.3241714,
author = {Alhama, Raquel G. and Zuidema, Willem},
title = {Pre-Wiring and Pre-Training: What Does a Neural Network Need to Learn Truly General Identity Rules?},
year = {2018},
issue_date = {January 2018},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {61},
number = {1},
issn = {1076-9757},
abstract = {In an influential paper ("Rule learning by seven-month-old infants"), Marcus, Vijayan, Rao and Vishton claimed that connectionist models cannot account for human success at learning tasks that involved generalization of abstract knowledge such as grammatical rules. This claim triggered a heated debate, centered mostly around variants of the Simple Recurrent Network model. In our work, we revisit this unresolved debate and analyze the underlying issues from a different perspective. We argue that, in order to simulate human-like learning of grammatical rules, a neural network model should not be used as a tabula rasa, but rather, the initial wiring of the neural connections and the experience acquired prior to the actual task should be incorporated into the model. We present two methods that aim to provide such initial state: a manipulation of the initial connections of the network in a cognitively plausible manner (concretely, by implementing a "delay-line" memory), and a pre-training algorithm that incrementally challenges the network with novel stimuli. We implement such techniques in an Echo State Network (ESN), and we show that only when combining both techniques the ESN is able to learn truly general identity rules. Finally, we discuss the relation between these cognitively motivated techniques and recent advances in Deep Learning.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {927–946},
numpages = {20}
}

@article{10.5555/3241691.3241713,
author = {Hupkes, Dieuwke and Veldhoen, Sara and Zuidema, Willem},
title = {Visualisation and ‘Diagnostic Classifiers’ Reveal How Recurrent and Recursive Neural Networks Process Hierarchical Structure},
year = {2018},
issue_date = {January 2018},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {61},
number = {1},
issn = {1076-9757},
abstract = {We investigate how neural networks can learn and process languages with hierarchical, compositional semantics. To this end, we define the artifical task of processing nested arithmetic expressions, and study whether different types of neural networks can learn to compute their meaning. We find that recursive neural networks can implement a generalising solution to this problem, and we visualise this solution by breaking it up in three steps: project, sum and squash. As a next step, we investigate recurrent neural networks, and show that a gated recurrent unit, that processes its input incrementally, also performs very well on this task: the network learns to predict the outcome of the arithmetic expressions with high accuracy, although performance deteriorates somewhat with increasing length. To develop an understanding of what the recurrent network encodes, visualisation techniques alone do not suffice. Therefore, we develop an approach where we formulate and test multiple hypotheses on the information encoded and processed by the network. For each hypothesis, we derive predictions about features of the hidden state representations at each time step, and train 'diagnostic classifiers' to test those predictions. Our results indicate that the networks follow a strategy similar to our hypothesised 'cumulative strategy', which explains the high accuracy of the network on novel expressions, the generalisation to longer expressions than seen in training, and the mild deterioration with increasing length. This in turn shows that diagnostic classifiers can be a useful technique for opening up the black box of neural networks. We argue that diagnostic classification, unlike most visualisation techniques, does scale up from small networks in a toy domain, to larger and deeper recurrent networks dealing with real-life data, and may therefore contribute to a better understanding of the internal dynamics of current state-of-the-art models in natural language processing.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {907–926},
numpages = {20}
}

@article{10.5555/3241691.3241712,
author = {Fern\'{a}ndez, Alberto and Garc\'{\i}a, Salvador and Herrera, Francisco and Chawla, Nitesh V.},
title = {SMOTE for Learning from Imbalanced Data: Progress and Challenges, Marking the 15-Year Anniversary},
year = {2018},
issue_date = {January 2018},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {61},
number = {1},
issn = {1076-9757},
abstract = {The Synthetic Minority Oversampling Technique (SMOTE) preprocessing algorithm is considered "de facto" standard in the framework of learning from imbalanced data. This is due to its simplicity in the design of the procedure, as well as its robustness when applied to different type of problems. Since its publication in 2002, SMOTE has proven successful in a variety of applications from several different domains. SMOTE has also inspired several approaches to counter the issue of class imbalance, and has also significantly contributed to new supervised learning paradigms, including multilabel classification, incremental learning, semi-supervised learning, multi-instance learning, among others. It is standard benchmark for learning from imbalanced data. It is also featured in a number of different software packages -- from open source to commercial. In this paper, marking the fifteen year anniversary of SMOTE, we reect on the SMOTE journey, discuss the current state of affairs with SMOTE, its applications, and also identify the next set of challenges to extend SMOTE for Big Data problems.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {863–905},
numpages = {43}
}

@article{10.5555/3241691.3241711,
author = {Yaghoobzadeh, Yadollah and Adel, Heike and Sch\"{u}tze, Hinrich},
title = {Corpus-Level Fine-Grained Entity Typing},
year = {2018},
issue_date = {January 2018},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {61},
number = {1},
issn = {1076-9757},
abstract = {Extracting information about entities remains an important research area. This paper addresses the problem of corpus-level entity typing, i.e., inferring from a large corpus that an entity is a member of a class, such as "food" or "artist". The application of entity typing we are interested in is knowledge base completion, specifically, to learn which classes an entity is a member of. We propose FIGMENT to tackle this problem. FIGMENT is embedding-based and combines (i) a global model that computes scores based on global information of an entity and (ii) a context model that first evaluates the individual occurrences of an entity and then aggregates the scores.Each of the two proposed models has specific properties. For the global model, learning high-quality entity representations is crucial because it is the only source used for the predictions. Therefore, we introduce representations using the name and contexts of entities on the three levels of entity, word, and character. We show that each level provides complementary information and a multi-level representation performs best. For the context model, we need to use distant supervision since there are no context-level labels available for entities. Distantly supervised labels are noisy and this harms the performance of models. Therefore, we introduce and apply new algorithms for noise mitigation using multi-instance learning. We show the effectiveness of our models on a large entity typing dataset built from Freebase.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {835–862},
numpages = {28}
}

@article{10.5555/3241691.3241710,
author = {Creignou, Nadia and Ktari, Ra\"{\i}da and Papini, Odile},
title = {Belief Update within Propositional Fragments},
year = {2018},
issue_date = {January 2018},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {61},
number = {1},
issn = {1076-9757},
abstract = {Belief change within the framework of fragments of propositional logic is one of the main and recent challenges in the knowledge representation research area. While previous research works focused on belief revision, belief merging, and belief contraction, the problem of belief update within fragments of classical logic has not been addressed so far. In the context of revision, it has been proposed to refine existing operators so that they operate within propositional fragments, and that the result of revision remains in the fragment under consideration. This approach is not restricted to the Horn fragment but also applicable to other propositional fragments like Krom and affine fragments. We generalize this notion of refinement to any belief change operator. We then focus on a specific belief change operation, namely belief update. We investigate the behavior of the refined update operators with respect to satisfaction of the KM postulates and highlight differences between revision and update in this context.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {807–834},
numpages = {28}
}

@article{10.5555/3241691.3241709,
author = {Raue, Federico and Dengel, Andreas and Breuel, Thomas M. and Liwicki, Marcus},
title = {Symbol Grounding Association in Multimodal Sequences with Missing Elements},
year = {2018},
issue_date = {January 2018},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {61},
number = {1},
issn = {1076-9757},
abstract = {In this paper, we extend a symbolic association framework for being able to handle missing elements in multimodal sequences. The general scope of the work is the symbolic associations of object-word mappings as it happens in language development in infants. In other words, two different representations of the same abstract concepts can associate in both directions. This scenario has been long interested in Artificial Intelligence, Psychology, and Neuroscience. In this work, we extend a recent approach for multimodal sequences (visual and audio) to also cope with missing elements in one or both modalities. Our method uses two parallel Long Short-Term Memories (LSTMs) with a learning rule based on EM-algorithm. It aligns both LSTM outputs via Dynamic Time Warping (DTW). We propose to include an extra step for the combination with the max operation for exploiting the common elements between both sequences. The motivation behind is that the combination acts as a condition selector for choosing the best representation from both LSTMs. We evaluated the proposed extension in the following scenarios: missing elements in one modality (visual or audio) and missing elements in both modalities (visual and sound). The performance of our extension reaches better results than the original model and similar results to individual LSTM trained in each modality.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {787–806},
numpages = {20}
}

@article{10.5555/3241691.3241708,
author = {Maximov, Yury and Amini, Massih-Reza and Harchaoui, Zaid},
title = {Rademacher Complexity Bounds for a Penalized Multi-Class Semi-Supervised Algorithm},
year = {2018},
issue_date = {January 2018},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {61},
number = {1},
issn = {1076-9757},
abstract = {We propose Rademacher complexity bounds for multi-class classifiers trained with a two-step semi-supervised model. In the first step, the algorithm partitions the partially labeled data and then identifies dense clusters containing κ predominant classes using the labeled training examples such that the proportion of their non-predominant classes is below a fixed threshold stands for clustering consistency. In the second step, a classifier is trained by minimizing a margin empirical loss over the labeled training set and a penalization term measuring the disability of the learner to predict the κ predominant classes of the identified clusters. The resulting data-dependent generalization error bound involves the margin distribution of the classifier, the stability of the clustering technique used in the first step and Rademacher complexity terms corresponding to partially labeled training data. Our theoretical result exhibit convergence rates extending those proposed in the literature for the binary case, and experimental results on different multi-class classification problems show empirical evidence that supports the theory.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {761–786},
numpages = {26}
}

@article{10.5555/3241691.3241707,
author = {McCreesh, Ciaran and Prosser, Patrick and Solnon, Christine and Trimble, James},
title = {When Subgraph Isomorphism is Really Hard, and Why This Matters for Graph Databases},
year = {2018},
issue_date = {January 2018},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {61},
number = {1},
issn = {1076-9757},
abstract = {The subgraph isomorphism problem involves deciding whether a copy of a pattern graph occurs inside a larger target graph. The non-induced version allows extra edges in the target, whilst the induced version does not. Although both variants are NP-complete, algorithms inspired by constraint programming can operate comfortably on many real-world problem instances with thousands of vertices. However, they cannot handle arbitrary instances of this size. We show how to generate "really hard" random instances for subgraph isomorphism problems, which are computationally challenging with a couple of hundred vertices in the target, and only twenty pattern vertices. For the non-induced version of the problem, these instances lie on a satisfiable / unsatisfiable phase transition, whose location we can predict; for the induced variant, much richer behaviour is observed, and constrainedness gives a better measure of difficulty than does proximity to a phase transition. These results have practical consequences: we explain why the widely researched "filter / verify" indexing technique used in graph databases is founded upon a misunderstanding of the empirical hardness of NP-complete problems, and cannot be beneficial when paired with any reasonable subgraph isomorphism algorithm.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {723–759},
numpages = {37}
}

@article{10.5555/3241691.3241706,
author = {Booth, Richard and Hunter, Aaron},
title = {Trust as a Precursor to Belief Revision},
year = {2018},
issue_date = {January 2018},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {61},
number = {1},
issn = {1076-9757},
abstract = {Belief revision is concerned with incorporating new information into a pre-existing set of beliefs. When the new information comes from another agent, we must first determine if that agent should be trusted. In this paper, we define trust as a pre-processing step before revision. We emphasize that trust in an agent is often restricted to a particular domain of expertise. We demonstrate that this form of trust can be captured by associating a state partition with each agent, then relativizing all reports to this partition before revising. We position the resulting family of trust-sensitive revision operators within the class of selective revision operators of Ferm\'{e} and Hansson, and we prove a representation result that characterizes the class of trust-sensitive revision operators in terms of a set of postulates. We also show that trust-sensitive revision is manipulable, in the sense that agents can sometimes have incentive to pass on misleading information.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {699–722},
numpages = {24}
}

@article{10.5555/3241691.3241705,
author = {Fioretto, Ferdinando and Pontelli, Enrico and Yeoh, William},
title = {Distributed Constraint Optimization Problems and Applications: A Survey},
year = {2018},
issue_date = {January 2018},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {61},
number = {1},
issn = {1076-9757},
abstract = {The field of multi-agent system (MAS) is an active area of research within artificial intelligence, with an increasingly important impact in industrial and other real-world applications. In a MAS, autonomous agents interact to pursue personal interests and/or to achieve common objectives. Distributed Constraint Optimization Problems (DCOPs) have emerged as a prominent agent model to govern the agents' autonomous behavior, where both algorithms and communication models are driven by the structure of the specific problem. During the last decade, several extensions to the DCOP model have been proposed to enable support of MAS in complex, real-time, and uncertain environments.This survey provides an overview of the DCOP model, offering a classification of its multiple extensions and addressing both resolution methods and applications that find a natural mapping within each class of DCOPs. The proposed classification suggests several future perspectives for DCOP extensions and identifies challenges in the design of efficient resolution algorithms, possibly through the adaptation of strategies from different areas.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {623–698},
numpages = {76}
}

@article{10.5555/3241691.3241704,
author = {D’Ippolito, Nicol\'{a}s and Rodr\'{\i}guez, Natalia and Sardina, Sebastian},
title = {Fully Observable Non-Deterministic Planning as Assumption-Based Reactive Synthesis},
year = {2018},
issue_date = {January 2018},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {61},
number = {1},
issn = {1076-9757},
abstract = {We contribute to recent efforts in relating two approaches to automatic synthesis, namely, automated planning and discrete reactive synthesis. First, we develop a declarative characterization of the standard "fairness" assumption on environments in non-deterministic planning, and show that strong-cyclic plans are correct solution concepts for fair environments. This complements, and arguably completes, the existing foundational work on non-deterministic planning, which focuses on characterizing (and computing) plans enjoying special "structural" properties, namely loopy but closed policy structures. Second, we provide an encoding suitable for reactive synthesis that avoids the naive exponential state space blowup. To do so, special care has to be taken to specify the fairness assumption on the environment in a succinct manner.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {593–621},
numpages = {29}
}

@article{10.5555/3241691.3241703,
author = {Garcia-Gasulla, Dario and Par\'{e}s, Ferran and Vilalta, Armand and Moreno, Jonatan and Ayguad\'{e}, Eduard and Labarta, Jes\'{u}s and Cort\'{e}s, Ulises and Suzumura, Toyotaro},
title = {On the Behavior of Convolutional Nets for Feature Extraction},
year = {2018},
issue_date = {January 2018},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {61},
number = {1},
issn = {1076-9757},
abstract = {Deep neural networks are representation learning techniques. During training, a deep net is capable of generating a descriptive language of unprecedented size and detail in machine learning. Extracting the descriptive language coded within a trained CNN model (in the case of image data), and reusing it for other purposes is a field of interest, as it provides access to the visual descriptors previously learnt by the CNN after processing millions of images, without requiring an expensive training phase. Contributions to this field (commonly known as feature representation transfer or transfer learning) have been purely empirical so far, extracting all CNN features from a single layer close to the output and testing their performance by feeding them to a classi_er. This approach has provided consistent results, although its relevance is limited to classi_cation tasks. In a completely different approach, in this paper we statistically measure the discriminative power of every single feature found within a deep CNN, when used for characterizing every class of 11 datasets. We seek to provide new insights into the behavior of CNN features, particularly the ones from convolutional layers, as this can be relevant for their application to knowledge representation and reasoning. Our results con_rm that low and middle level features may behave di_erently to high level features, but only under certain conditions. We find that all CNN features can be used for knowledge representation purposes both by their presence or by their absence, doubling the information a single CNN feature may provide. We also study how much noise these features may include, and propose a thresholding approach to discard most of it. All these insights have a direct application to the generation of CNN embedding spaces.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {563–592},
numpages = {30}
}

@article{10.5555/3241691.3241702,
author = {Machado, Marlos C. and Bellemare, Marc G. and Talvitie, Erik and Veness, Joel and Hausknecht, Matthew and Bowling, Michael},
title = {Revisiting the Arcade Learning Environment: Evaluation Protocols and Open Problems for General Agents},
year = {2018},
issue_date = {January 2018},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {61},
number = {1},
issn = {1076-9757},
abstract = {The Arcade Learning Environment (ALE) is an evaluation platform that poses the challenge of building AI agents with general competency across dozens of Atari 2600 games. It supports a variety of different problem settings and it has been receiving increasing attention from the scientific community, leading to some high-pro_le success stories such as the much publicized Deep Q-Networks (DQN). In this article we take a big picture look at how the ALE is being used by the research community. We show how diverse the evaluation methodologies in the ALE have become with time, and highlight some key concerns when evaluating agents in the ALE. We use this discussion to present some methodological best practices and provide new benchmark results using these best practices. To further the progress in the field, we introduce a new version of the ALE that supports multiple game modes and provides a form of stochasticity we call sticky actions. We conclude this big picture look by revisiting challenges posed when the ALE was introduced, summarizing the state-of-the-art in various problems and highlighting problems that remain open.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {523–562},
numpages = {40}
}

@article{10.5555/3241691.3241701,
author = {Fi\v{s}er, Daniel and Komenda, Anton\'{\i}n},
title = {Fact-Alternating Mutex Groups for Classical Planning},
year = {2018},
issue_date = {January 2018},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {61},
number = {1},
issn = {1076-9757},
abstract = {Mutex groups are defined in the context of STRIPS planning as sets of facts out of which, maximally, one can be true in any state reachable from the initial state. The importance of computing and exploiting mutex groups was repeatedly pointed out in many studies. However, the theoretical analysis of mutex groups is sparse in current literature. This work provides a complexity analysis showing that inference of mutex groups is as hard as planning itself (PSPACE-Complete) and it also shows a tight relationship between mutex groups and graph cliques. This result motivates us to propose a new type of mutex group called a fact-alternating mutex group (fam-group) of which inference is NP-Complete. Moreover, we introduce an algorithm for the inference of fam-groups based on integer linear programming that is complete with respect to the maximal fam-groups and we demonstrate how beneficial fam-groups can be in the translation of planning tasks into finite domain representation. Finally, we show that fam-groups can be used for the detection of deadend states and we propose a simple algorithm for the pruning of operators and facts as a preprocessing step that takes advantage of the properties of fam-groups. The experimental evaluation of the pruning algorithm shows a substantial increase in a number of solved tasks in domains from the optimal deterministic track of the last two planning competitions (IPC 2011 and 2014).},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {475–521},
numpages = {47}
}

@article{10.5555/3241691.3241700,
author = {Zenonos, Alexandros and Stein, Sebastian and Jennings, Nicholas R.},
title = {Coordinating Measurements for Environmental Monitoring in Uncertain Participatory Sensing Settings},
year = {2018},
issue_date = {January 2018},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {61},
number = {1},
issn = {1076-9757},
abstract = {Environmental monitoring allows authorities to understand the impact of potentially harmful phenomena, such as air pollution, excessive noise and radiation. Recently, there has been considerable interest in participatory sensing as a paradigm for such large-scale data collection because it is cost-effective and able to capture more fine-grained data than traditional approaches that use stationary sensors scattered in cities. In this approach, ordinary citizens (non-expert contributors) collect environmental data using low-cost mobile devices. However, these participants are generally self-interested actors that have their own goals and make local decisions about when and where to take measurements. This can lead to highly ine_cient outcomes, where observations are either taken redundantly or do not provide sufficient information about key areas of interest. To address these challenges, it is necessary to guide and to coordinate participants, so they take measurements when it is most informative. To this end, we develop a computationally-e_cient coordination algorithm (adaptive Best-Match) that suggests to users when and where to take measurements. Our algorithm exploits probabilistic knowledge of human mobility patterns, but explicitly considers the uncertainty of these patterns and the potential unwillingness of people to take measurements when requested to do so. In particular, our algorithm uses a local search technique, clustering and random simulations to map participants to measurements that need to be taken in space and time. We empirically evaluate our algorithm on a real-world human mobility and air quality dataset and show that it outperforms the current state of the art by up to 24% in terms of utility gained.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {433–474},
numpages = {42}
}

@article{10.5555/3241691.3241699,
author = {Zwicker, William S.},
title = {Cycles and Intractability in a Large Class of Aggregation Rules},
year = {2018},
issue_date = {January 2018},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {61},
number = {1},
issn = {1076-9757},
abstract = {We introduce the (j, k)-Kemeny rule - a generalization of Kemeny's voting rule that aggregates j-chotomous weak orders into a k-chotomous weak order. Special cases of (j, k)- Kemeny include approval voting, the mean rule and Borda mean rule, as well as the Borda count and plurality voting. Why, then, is the winner problem computationally tractable for each of these other rules, but intractable for Kemeny? We show that intractability of winner determination for the (j, k)-Kemeny rule first appears at the j = 3, k = 3 level. The proof rests on a reduction of max cut to a related problem on weighted tournaments, and reveals that computational complexity arises from the cyclic part in the fundamental decomposition of a weighted tournament into cyclic and cocyclic components. Thus the existence of majority cycles - the engine driving both Arrow's impossibility theorem and the Gibbard-Satterthwaite theorem - also serves as a source of computational complexity in social choice.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {407–431},
numpages = {25}
}

@article{10.5555/3241691.3241698,
author = {Kara, Yunus Emre and Genc, Gaye and Aran, Oya and Akarun, Lale},
title = {Actively Estimating Crowd Annotation Consensus},
year = {2018},
issue_date = {January 2018},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {61},
number = {1},
issn = {1076-9757},
abstract = {The rapid growth of storage capacity and processing power has caused machine learning applications to increasingly rely on using immense amounts of labeled data. It has become more important than ever to have fast and inexpensive ways to annotate vast amounts of data. With the emergence of crowdsourcing services, the research direction has gravitated toward putting the wisdom of crowds to better use. Unfortunately, spammers and inattentive annotators pose a threat to the quality and trustworthiness of the consensus. Thus, high quality consensus estimation from crowd annotated data requires a meticulous choice of the candidate annotator and the sample in need of a new annotation. Due to time and budget limitations, it is of utmost importance that this choice is carried out while the annotation collection is in progress. We call this process active crowd-labeling. To this end, we propose an active crowd-labeling approach for actively estimating consensus from continuous-valued crowd annotations. Our method is based on annotator models with unknown parameters, and Bayesian inference is employed to reach a consensus in the form of ordinal, binary, or continuous values. We introduce ranking functions for choosing the candidate annotator and sample pair for requesting an annotation. In addition, we propose a penalizing method for preventing annotator domination, investigate the explore-exploit trade-off for incorporating new annotators into the system, and study the effects of inducing a stopping criterion based on consensus quality. We also introduce the crowd-labeled Head Pose Annotations datasets. Experimental results on the benchmark datasets used in the literature and the Head Pose Annotations datasets suggest that our method provides high-quality consensus by using as few as one _fth of the annotations (~ 80% cost reduction), thereby providing a budget and time-sensitive solution to the crowd-labeling problem.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {363–405},
numpages = {43}
}

@article{10.5555/3241691.3241697,
author = {Gaschler, Andre and Petrick, Ronald P. A. and Khatib, Oussama and Knoll, Alois},
title = {KABouM: Knowledge-Level Action and Bounding Geometry Motion Planner},
year = {2018},
issue_date = {January 2018},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {61},
number = {1},
issn = {1076-9757},
abstract = {For robots to solve real world tasks, they often require the ability to reason about both symbolic and geometric knowledge. We present a framework, called KABouM, for integrating knowledge-level task planning and motion planning in a bounding geometry. By representing symbolic information at the knowledge level, we can model incomplete information, sensing actions and information gain; by representing all geometric entities-- objects, robots and swept volumes of motions|by sets of convex polyhedra, we can efficiently plan manipulation actions and raise reasoning about geometric predicates, such as collisions, to the symbolic level. At the geometric level, we take advantage of our bounded convex decomposition and swept volume computation with quadratic convergence, and fast collision detection of convex bodies. We evaluate our approach on a wide set of problems using real robots, including tasks with multiple manipulators, sensing and branched plans, and mobile manipulation.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {323–362},
numpages = {40}
}

@article{10.5555/3241691.3241696,
author = {Kimura, Kei and Makino, Kazuhisa},
title = {Linear Satisfiability Preserving Assignments},
year = {2018},
issue_date = {January 2018},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {61},
number = {1},
issn = {1076-9757},
abstract = {In this paper, we study several classes of satisfiability preserving assignments to the constraint satisfaction problem (CSP). In particular, we consider fixable, autark and satisfying assignments. Since it is in general NP-hard to find a nontrivial (i.e., nonempty) satisfiability preserving assignment, we introduce linear satisfiability preserving assignments, which are defined by polyhedral cones in an associated vector space. The vector space is obtained by the identi_cation, introduced by Kullmann, of assignments with real vectors. We consider arbitrary polyhedral cones, where only restricted classes of cones for autark assignments are considered in the literature. We reveal that cones in certain classes are maximal as a convex subset of the set of the associated vectors, which can be regarded as extensions of Kullmann's results for autark assignments of CNFs. As algorithmic results, we present a pseudo-polynomial time algorithm that computes a linear fixable assignment for a given integer linear system, which implies the well known pseudo-polynomial solvability for integer linear systems such as two-variable-per-inequality (TVPI), Horn and q-Horn systems.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {291–321},
numpages = {31}
}

@article{10.5555/3241691.3241695,
author = {Konidaris, George and Kaelbling, Leslie Pack and Lozano-Perez, Tomas},
title = {From Skills to Symbols: Learning Symbolic Representations for Abstract High-Level Planning},
year = {2018},
issue_date = {January 2018},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {61},
number = {1},
issn = {1076-9757},
abstract = {We consider the problem of constructing abstract representations for planning in high-dimensional, continuous environments. We assume an agent equipped with a collection of high-level actions, and construct representations provably capable of evaluating plans composed of sequences of those actions.We first consider the deterministic planning case, and show that the relevant computation involves set operations performed over sets of states. We define the specific collection of sets that is necessary and su_cient for planning, and use them to construct a grounded abstract symbolic representation that is provably suitable for deterministic planning. The resulting representation can be expressed in PDDL, a canonical high-level planning domain language; we construct such a representation for the Playroom domain and solve it in milliseconds using an off-the-shelf planner.We then consider probabilistic planning, which we show requires generalizing from sets of states to distributions over states. We identify the specific distributions required for planning, and use them to construct a grounded abstract symbolic representation that correctly estimates the expected reward and probability of success of any plan. In addition, we show that learning the relevant probability distributions corresponds to specific instances of probabilistic density estimation and probabilistic classification. We construct an agent that autonomously learns the correct abstract representation of a computer game domain, and rapidly solves it.Finally, we apply these techniques to create a physical robot system that autonomously learns its own symbolic representation of a mobile manipulation task directly from sensorimotor data--point clouds, map locations, and joint angles--and then plans using that representation. Together, these results establish a principled link between high-level actions and abstract representations, a concrete theoretical foundation for constructing abstract representations with provable properties, and a practical mechanism for autonomously learning abstract high-level representations.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {215–289},
numpages = {75}
}

@article{10.5555/3241691.3241694,
author = {Abriola, Sergio and Barcel\'{o}, Pablo and Figueira, Diego and Figueira, Santiago},
title = {Bisimulations on Data Graphs},
year = {2018},
issue_date = {January 2018},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {61},
number = {1},
issn = {1076-9757},
abstract = {Bisimulation provides structural conditions to characterize indistinguishability from an external observer between nodes on labeled graphs. It is a fundamental notion used in many areas, such as verification, graph-structured databases, and constraint satisfaction. However, several current applications use graphs where nodes also contain data (the so called "data graphs"), and where observers can test for equality or inequality of data values (e.g., asking the attribute 'name' of a node to be different from that of all its neighbors). The present work constitutes a first investigation of "data aware" bisimulations on data graphs. We study the problem of computing such bisimulations, based on the observational indistinguishability for XPath "a language that extends modal logics like PDL with tests for data equality" with and without transitive closure operators. We show that in general the problem is PSPACE-complete, but identify several restrictions that yield better complexity bounds (CO-NP, PTIME) by controlling suitable parameters of the problem, namely the amount of non-locality allowed, and the class of models considered (graphs, DAGs, trees). In particular, this analysis yields a hierarchy of tractable fragments.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {171–213},
numpages = {43}
}

@article{10.5555/3241691.3241693,
author = {Gatt, Albert and Krahmer, Emiel},
title = {Survey of the State of the Art in Natural Language Generation: Core Tasks, Applications and Evaluation},
year = {2018},
issue_date = {January 2018},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {61},
number = {1},
issn = {1076-9757},
abstract = {This paper surveys the current state of the art in Natural Language Generation (NLG), defined as the task of generating text or speech from non-linguistic input. A survey of NLG is timely in view of the changes that the field has undergone over the past two decades, especially in relation to new (usually data-driven) methods, as well as new applications of NLG technology. This survey therefore aims to (a) give an up-to-date synthesis of research on the core tasks in NLG and the architectures adopted in which such tasks are organised; (b) highlight a number of recent research topics that have arisen partly as a result of growing synergies between NLG and other areas of artifical intelligence; (c) draw attention to the challenges in NLG evaluation, relating them to similar challenges faced in other areas of nlp, with an emphasis on different evaluation methods and the relationships between them.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {65–170},
numpages = {106}
}

@article{10.5555/3241691.3241692,
author = {Evans, Richard and Grefenstette, Edward},
title = {Learning Explanatory Rules from Noisy Data},
year = {2018},
issue_date = {January 2018},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {61},
number = {1},
issn = {1076-9757},
abstract = {Artificial Neural Networks are powerful function approximators capable of modelling solutions to a wide variety of problems, both supervised and unsupervised. As their size and expressivity increases, so too does the variance of the model, yielding a nearly ubiquitous over_tting problem. Although mitigated by a variety of model regularisation methods, the common cure is to seek large amounts of training data--which is not necessarily easily obtained--that sufficiently approximates the data distribution of the domain we wish to test on. In contrast, logic programming methods such as Inductive Logic Programming offer an extremely data-efficient process by which models can be trained to reason on symbolic domains. However, these methods are unable to deal with the variety of domains neural networks can be applied to: they are not robust to noise in or mislabelling of inputs, and perhaps more importantly, cannot be applied to non-symbolic domains where the data is ambiguous, such as operating on raw pixels. In this paper, we propose a Differentiable Inductive Logic framework, which can not only solve tasks which traditional ILP systems are suited for, but shows a robustness to noise and error in the training data which ILP cannot cope with. Furthermore, as it is trained by backpropagation against a likelihood objective, it can be hybridised by connecting it with neural networks over ambiguous data in order to be applied to domains which ILP cannot address, while providing data efficiency and generalisation beyond what neural networks on their own can achieve.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {1–64},
numpages = {64}
}

@article{10.5555/3207692.3207718,
author = {Delgrande, James P.},
title = {A Knowledge Level Account of Forgetting},
year = {2017},
issue_date = {September 2017},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {60},
number = {1},
issn = {1076-9757},
abstract = {Forgetting is an operation on knowledge bases that has been addressed in different areas of Knowledge Representation and with respect to different formalisms, including classical propositional and first-order logic, modal logics, logic programming, and description logics. Definitions of forgetting have been expressed in terms of manipulation of formulas, sets of postulates, isomorphisms between models, bisimulations, second-order quantification, elementary equivalence, and others. In this paper, forgetting is regarded as an abstract belief change operator, independent of the underlying logic. The central thesis is that forgetting amounts to a reduction in the language, specifically the signature, of a logic. The main definition is simple: the result of forgetting a portion of a signature in a theory is given by the set of logical consequences of this theory over the reduced language. This definition offers several advantages. Foremost, it provides a uniform approach to forgetting, with a definition that is applicable to any logic with a well-defined consequence relation. Hence it generalises a disparate set of logic-specific definitions with a general, high-level definition. Results obtained in this approach are thus applicable to all subsumed formal systems, and many results are obtained much more straightforwardly. This view also leads to insights with respect to specific logics: for example, forgetting in first-order logic is somewhat different from the accepted approach. Moreover, the approach clarifies the relation between forgetting and related operations, including belief contraction.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {1165–1213},
numpages = {49}
}

@article{10.5555/3207692.3207717,
author = {Basat, Ran Ben and Tennenholtz, Moshe and Kurland, Oren},
title = {A Game Theoretic Analysis of the Adversarial Retrieval Setting},
year = {2017},
issue_date = {September 2017},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {60},
number = {1},
issn = {1076-9757},
abstract = {The main goal of search engines is ad hoc retrieval: ranking documents in a corpus by their relevance to the information need expressed by a query. The Probability Ranking Principle (PRP) -- ranking the documents by their relevance probabilities -- is the theoretical foundation of most existing ad hoc document retrieval methods. A key observation that motivates our work is that the PRP does not account for potential post-ranking effects; specifically, changes to documents that result from a given ranking. Yet, in adversarial retrieval settings such as the Web, authors may consistently try to promote their documents in rankings by changing them. We prove that, indeed, the PRP can be sub-optimal in adversarial retrieval settings. We do so by presenting a novel game theoretic analysis of the adversarial setting. The analysis is performed for different types of documents (single-topic and multi-topic) and is based on different assumptions about the writing qualities of documents' authors. We show that in some cases, introducing randomization into the document ranking function yields an overall user utility that transcends that of applying the PRP.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {1127–1164},
numpages = {38}
}

@article{10.5555/3207692.3207716,
author = {Zaffalon, Marco and Miranda, Enrique},
title = {Axiomatising Incomplete Preferences through Sets of Desirable Gambles},
year = {2017},
issue_date = {September 2017},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {60},
number = {1},
issn = {1076-9757},
abstract = {We establish the equivalence of two very general theories: the first is the decision-theoretic formalisation of incomplete preferences based on the mixture independence axiom; the second is the theory of coherent sets of desirable gambles (bounded variables) developed in the context of imprecise probability and extended here to vector-valued gambles. Such an equivalence allows us to analyse the theory of incomplete preferences from the point of view of desirability. Among other things, this leads us to uncover an unexpected and clarifying relation: that the notion of state independence -- the traditional assumption that we can have separate models for beliefs (probabilities) and values (utilities) -- coincides with that of strong independence in imprecise probability; this connection leads us also to propose much weaker, and arguably more realistic, notions of state independence. Then we simplify the treatment of complete beliefs and values by putting them on a more equal footing. We study the role of the Archimedean condition -- which allows us to actually talk of expected utility--, identify some weaknesses and propose alternatives that solve these. More generally speaking, we show that desirability is a valuable alternative foundation to preferences for decision theory that streamlines and unifies a number of concepts while preserving great generality. In addition, the mentioned equivalence shows for the first time how to extend the theory of desirability to imprecise non-linear utility, thus enabling us to formulate one of the most powerful self-consistent theories of reasoning and decision-making available today.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {1057–1126},
numpages = {70}
}

@article{10.5555/3207692.3207715,
author = {De Rosa, Rocco and Cesa-Bianchi, Nicol\`{o}},
title = {Confidence Decision Trees via Online and Active Learning for Streaming Data},
year = {2017},
issue_date = {September 2017},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {60},
number = {1},
issn = {1076-9757},
abstract = {Decision tree classifiers are a widely used tool in data stream mining. The use of confidence intervals to estimate the gain associated with each split leads to very effective methods, like the popular Hoeffding tree algorithm. From a statistical viewpoint, the analysis of decision tree classifiers in a streaming setting requires knowing when enough new information has been collected to justify splitting a leaf. Although some of the issues in the statistical analysis of Hoeffding trees have been already clarified, a general and rigorous study of confidence intervals for splitting criteria is missing. We fill this gap by deriving accurate confidence intervals to estimate the splitting gain in decision tree learning with respect to three criteria: entropy, Gini index, and a third index proposed by Kearns and Mansour. We also extend our confidence analysis to a selective sampling setting, in which the decision tree learner adaptively decides which labels to query in the stream. We provide theoretical guarantees bounding the probability that the decision tree learned via our selective sampling strategy classifies suboptimally the next example in the stream. Experiments on real and synthetic data in a streaming setting show that our trees are indeed more accurate than trees with the same number of leaves generated by state-of-the-art techniques. In addition to that, our active learning module empirically uses fewer labels without significantly hurting the performance.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {1031–1055},
numpages = {25}
}

@article{10.5555/3207692.3207714,
author = {Kiela, Douwe and Clark, Stephen},
title = {Learning Neural Audio Embeddings for Grounding Semantics in Auditory Perception},
year = {2017},
issue_date = {September 2017},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {60},
number = {1},
issn = {1076-9757},
abstract = {Multi-modal semantics, which aims to ground semantic representations in perception, has relied on feature norms or raw image data for perceptual input. In this paper we examine grounding semantic representations in raw auditory data, using standard evaluations for multi-modal semantics. After having shown the quality of such auditorily grounded representations, we show how they can be applied to tasks where auditory perception is relevant, including two unsupervised categorization experiments, and provide further analysis. We find that features transfered from deep neural networks outperform bag of audio words approaches. To our knowledge, this is the first work to construct multi-modal models from a combination of textual information and auditory information extracted from deep neural networks, and the first work to evaluate the performance of tri-modal (textual, visual and auditory) semantic models.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {1003–1030},
numpages = {28}
}

@article{10.5555/3207692.3207713,
author = {Chen, Jiehua and Faliszewski, Piotr and Niedermeier, Rolf and Talmon, Nimrod},
title = {Elections with Few Voters: Candidate Control Can Be Easy},
year = {2017},
issue_date = {September 2017},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {60},
number = {1},
issn = {1076-9757},
abstract = {We study the computational complexity of candidate control in elections with few voters, that is, we consider the parameterized complexity of candidate control in elections with respect to the number of voters as a parameter. We consider both the standard scenario of adding and deleting candidates, where one asks whether a given candidate can become a winner (or, in the destructive case, can be precluded from winning) by adding or deleting few candidates, as well as a combinatorial scenario where adding/deleting a candidate automatically means adding or deleting a whole group of candidates. Considering several fundamental voting rules, our results show that the parameterized complexity of candidate control, with the number of voters as the parameter, is much more varied than in the setting with many voters.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {937–1002},
numpages = {66}
}

@article{10.5555/3207692.3207712,
author = {Vodopivec, Tom and Samothrakis, Spyridon and \v{S}ter, Branko},
title = {On Monte Carlo Tree Search and Reinforcement Learning},
year = {2017},
issue_date = {September 2017},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {60},
number = {1},
issn = {1076-9757},
abstract = {Fuelled by successes in Computer Go, Monte Carlo tree search (MCTS) has achieved wide-spread adoption within the games community. Its links to traditional reinforcement learning (RL) methods have been outlined in the past; however, the use of RL techniques within tree search has not been thoroughly studied yet. In this paper we re-examine in depth this close relation between the two fields; our goal is to improve the cross-awareness between the two communities. We show that a straightforward adaptation of RL semantics within tree search can lead to a wealth of new algorithms, for which the traditional MCTS is only one of the variants. We confirm that planning methods inspired by RL in conjunction with online search demonstrate encouraging results on several classic board games and in arcade video game competitions, where our algorithm recently ranked first. Our study promotes a unified view of learning, planning, and search.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {881–936},
numpages = {56}
}

@article{10.5555/3207692.3207711,
author = {Echenim, Mnacho and Peltier, Nicolas and Tourret, Sophie},
title = {Prime Implicate Generation in Equational Logic},
year = {2017},
issue_date = {September 2017},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {60},
number = {1},
issn = {1076-9757},
abstract = {We present an algorithm for the generation of prime implicates in equational logic, that is, of the most general consequences of formul\ae{} containing equations and disequations between first-order terms. This algorithm is defined by a calculus that is proved to be correct and complete. We then focus on the case where the considered clause set is ground, i.e., contains no variables, and devise a specialized tree data structure that is designed to efficiently detect and delete redundant implicates. The corresponding algorithms are presented along with their termination and correctness proofs. Finally, an experimental evaluation of this prime implicate generation method is conducted in the ground case, including a comparison with state-of-the-art propositional and first-order prime implicate generation tools.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {827–880},
numpages = {54}
}

@article{10.5555/3207692.3207710,
author = {Caminada, Martin and Schulz, Claudia},
title = {On the Equivalence between Assumption-Based Argumentation and Logic Programming},
year = {2017},
issue_date = {September 2017},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {60},
number = {1},
issn = {1076-9757},
abstract = {Assumption-Based Argumentation (ABA) has been shown to subsume various other non-monotonic reasoning formalisms, among them normal logic programming (LP). We re-examine the relationship between ABA and LP and show that normal LP also subsumes (flat) ABA. More precisely, we specify a procedure that given a (flat) ABA framework yields an associated logic program with almost the same syntax whose semantics coincide with those of the ABA framework. That is, the 3-valued stable (respectively well-founded, regular, 2-valued stable, and ideal) models of the associated logic program coincide with the complete (respectively grounded, preferred, stable, and ideal) assumption labellings and extensions of the ABA framework. Moreover, we show how our results on the translation from ABA to LP can be reapplied for a reverse translation from LP to ABA, and observe that some of the existing results in the literature are in fact special cases of our work. Overall, we show that (flat) ABA frameworks can be seen as normal logic programs with a slightly different syntax. This implies that methods developed for one of these formalisms can be equivalently applied to the other by simply modifying the syntax.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {779–825},
numpages = {47}
}

@article{10.5555/3207692.3207709,
author = {Hostetler, Jesse and Fern, Alan and Dietterich, Thomas},
title = {Sample-Based Tree Search with Fixed and Adaptive State Abstractions},
year = {2017},
issue_date = {September 2017},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {60},
number = {1},
issn = {1076-9757},
abstract = {Sample-based tree search (SBTS) is an approach to solving Markov decision problems based on constructing a lookahead search tree using random samples from a generative model of the MDP. It encompasses Monte Carlo tree search (MCTS) algorithms like UCT as well as algorithms such as sparse sampling. SBTS is well-suited to solving MDPs with large state spaces due to the relative insensitivity of SBTS algorithms to the size of the state space. The limiting factor in the performance of SBTS tends to be the exponential dependence of sample complexity on the depth of the search tree. The number of samples required to build a search tree is O((|A|B)d), where |A| is the number of available actions, B is the number of possible random outcomes of taking an action, and d is the depth of the tree. State abstraction can be used to reduce B by aggregating random outcomes together into abstract states. Recent work has shown that abstract tree search often performs substantially better than tree search conducted in the ground state space.This paper presents a theoretical and empirical evaluation of tree search with both fixed and adaptive state abstractions. We derive a bound on regret due to state abstraction in tree search that decomposes abstraction error into three components arising from properties of the abstraction and the search algorithm. We describe versions of popular SBTS algorithms that use fixed state abstractions, and we introduce the Progressive Abstraction Refinement in Sparse Sampling (PARSS) algorithm, which adapts its abstraction during search. We evaluate PARSS as well as sparse sampling with fixed abstractions on 12 experimental problems, and find that PARSS outperforms search with a fixed abstraction and that search with even highly inaccurate fixed abstractions outperforms search without abstraction. These results establish progressive abstraction refinement as a promising basis for new tree search algorithms, and we propose directions for future work within the progressive refinement framework.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {717–777},
numpages = {61}
}

@article{10.5555/3207692.3207708,
author = {Skowron, Piotr and Faliszewski, Piotr},
title = {Chamberlin-Courant Rule with Approval Ballots: Approximating the Maxcover Problem with Bounded Frequencies in FPT Time},
year = {2017},
issue_date = {September 2017},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {60},
number = {1},
issn = {1076-9757},
abstract = {We consider the problem of winner determination under Chamberlin-Courant's multiwinner voting rule with approval utilities. This problem is equivalent to the well-known NP-complete MaxCover problem and, so, the best polynomial-time approximation algorithm for it has approximation ratio 1-1/e. We show exponential-time/FPT approximation algorithms that, on one hand, achieve arbitrarily good approximation ratios and, on the other hand, have running times much better than known exact algorithms. We focus on the cases where the voters have to approve of at most/at least a given number of candidates.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {687–716},
numpages = {30}
}

@article{10.5555/3207692.3207707,
author = {Inclezan, Daniela and Pr\'{a}danos, Luis I.},
title = {Viewpoint: A Critical View on Smart Cities and AI},
year = {2017},
issue_date = {September 2017},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {60},
number = {1},
issn = {1076-9757},
abstract = {AI developments on smart cities, if not critical, risk making a flawed urban model more efficient. Instead, we suggest that AI should challenge the mainstream techno-optimistic approach to solving urban problems by dialoguing with other academic fields, questioning the dominant urban paradigm, and creating transformative solutions. We claim that doing differently, rather than doing better, may be smarter for cities and the common good.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {681–686},
numpages = {6}
}

@article{10.5555/3207692.3207706,
author = {Dickerson, John P. and Sandholm, Tuomas},
title = {Multi-Organ Exchange},
year = {2017},
issue_date = {September 2017},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {60},
number = {1},
issn = {1076-9757},
abstract = {Kidney exchange, where candidates with organ failure trade incompatible but willing donors, is a life-saving alternative to the deceased donor waitlist, which has inadequate supply to meet demand. While fielded kidney exchanges see huge benefit from altruistic kidney donors (who give an organ without a paired needy candidate), a significantly higher medical risk to the donor deters similar altruism with livers. In this paper, we begin by exploring the idea of large-scale liver exchange, and show on demographically accurate data that vetted kidney exchange algorithms can be adapted to clear such an exchange at the nationwide level. We then propose cross-organ donation where kidneys and livers can be bartered for each other. We show theoretically that this multi-organ exchange provides linearly more transplants than running separate kidney and liver exchanges. This linear gain is a product of altruistic kidney donors creating chains that thread through the liver pool; it exists even when only a small but constant portion of the donors on the kidney side of the pool are willing to donate a liver lobe. We support this result experimentally on demographically accurate multi-organ exchanges. We conclude with thoughts regarding the fielding of a nationwide liver or joint liver-kidney exchange from a legal and computational point of view.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {639–679},
numpages = {41}
}

@article{10.5555/3207692.3207705,
author = {B\"{a}ckstr\"{o}m, Christer and Jonsson, Peter},
title = {Time and Space Bounds for Planning},
year = {2017},
issue_date = {September 2017},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {60},
number = {1},
issn = {1076-9757},
abstract = {There is an extensive literature on the complexity of planning, but explicit bounds on time and space complexity are very rare. On the other hand, problems like the constraint satisfaction problem (CSP) have been thoroughly analysed in this respect. We provide a number of upper- and lower-bound results (the latter based on various complexity-theoretic assumptions such as the Exponential Time Hypothesis) for both satisficing and optimal planning. We show that many classes of planning instances exhibit a dichotomy: either they can be solved in polynomial time or they cannot be solved in subexponential time and thus require O(2cn) time for some c > 0. In many cases, we can even prove closely matching upper and lower bounds; for every ε > 0, the problem can be solved in time O(2(1+ε)n) but not in time O(2(1-ε)n). Our results also indicate, analogously to CSPs, the existence of sharp phase transitions. We finally study and discuss the trade-off between time and space. In particular, we show that depth-first search may sometimes be a viable option for planning under severe space constraints.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {595–638},
numpages = {44}
}

@article{10.5555/3207692.3207704,
author = {Paetzold, Gustavo H. and Specia, Lucia},
title = {A Survey on Lexical Simplification},
year = {2017},
issue_date = {September 2017},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {60},
number = {1},
issn = {1076-9757},
abstract = {Lexical Simplification is the process of replacing complex words in a given sentence with simpler alternatives of equivalent meaning. This task has wide applicability both as an assistive technology for readers with cognitive impairments or disabilities, such as Dyslexia and Aphasia, and as a pre-processing tool for other Natural Language Processing tasks, such as machine translation and summarisation. The problem is commonly framed as a pipeline of four steps: the identification of complex words, the generation of substitution candidates, the selection of those candidates that fit the context, and the ranking of the selected substitutes according to their simplicity. In this survey we review the literature for each step in this typical Lexical Simplification pipeline and provide a benchmarking of existing approaches for these steps on publicly available datasets. We also provide pointers for datasets and resources available for the task.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {549–593},
numpages = {45}
}

@article{10.5555/3207692.3207703,
author = {Jinnai, Yuu and Fukunaga, Alex},
title = {On Hash-Based Work Distribution Methods for Parallel Best-First Search},
year = {2017},
issue_date = {September 2017},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {60},
number = {1},
issn = {1076-9757},
abstract = {Parallel best-first search algorithms such as Hash Distributed A* (HDA*) distribute work among the processes using a global hash function. We analyze the search and communication overheads of state-of-the-art hash-based parallel best-first search algorithms, and show that although Zobrist hashing, the standard hash function used by HDA*, achieves good load balance for many domains, it incurs significant communication overhead since almost all generated nodes are transferred to a different processor than their parents. We propose Abstract Zobrist hashing, a new work distribution method for parallel search which, instead of computing a hash value based on the raw features of a state, uses a feature projection function to generate a set of abstract features which results in a higher locality, resulting in reduced communications overhead. We show that Abstract Zobrist hashing outperforms previous methods on search domains using hand-coded, domain specific feature projection functions. We then propose GRAZHDA*, a graph-partitioning based approach to automatically generating feature projection functions. GRAZHDA* seeks to approximate the partitioning of the actual search space graph by partitioning the domain transition graph, an abstraction of the state space graph. We show that GRAZHDA* outperforms previous methods on domain-independent planning.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {491–548},
numpages = {58}
}

@article{10.5555/3207692.3207702,
author = {Yu, Peng and Williams, Brian and Fang, Cheng and Cui, Jing and Haslum, Patrik},
title = {Resolving Over-Constrained Temporal Problems with Uncertainty through Conflict-Directed Relaxation},
year = {2017},
issue_date = {September 2017},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {60},
number = {1},
issn = {1076-9757},
abstract = {Over-subscription, that is, being assigned too many things to do, is commonly encountered in temporal scheduling problems. As human beings, we often want to do more than we can actually do, and underestimate how long it takes to perform each task. Decision makers can benefit from aids that identify when these failure situations are likely, the root causes of these failures, and resolutions to these failures.In this paper, we present a decision assistant that helps users resolve oversubscribed temporal problems. The system works like an experienced advisor that can quickly identify the cause of failure underlying temporal problems and compute resolutions. The core of the decision assistant is the Best-first Con ict-Directed Relaxation (BCDR) algorithm, which can detect conflicting sets of constraints within temporal problems, and computes continuous relaxations for them that weaken constraints to the minimum extent, instead of removing them completely. BCDR is an extension to the Con ict-Directed A* algorithm, first developed in the model-based reasoning community to compute most likely system diagnoses or reconfigurations. It generalizes the discrete conflicts and relaxations, to hybrid conflicts and relaxations, which denote minimal inconsistencies and minimal relaxations to both discrete and continuous relaxable constraints. In addition, BCDR is capable of handling temporal uncertainty, expressed as either set-bounded or probabilistic durations, and can compute preferred trade-offs between the risk of violating a schedule requirement, versus the loss of utility by weakening those requirements.BCDR has been applied to several decision support applications in different domains, including deep-sea exploration, urban travel planning and transit system management. It has demonstrated its effectiveness in helping users resolve over-subscribed scheduling problems and evaluate the robustness of existing solutions. In our benchmark experiments, BCDR has also demonstrated its efficiency on solving large-scale scheduling problems in the aforementioned domains. Thanks to its conflict-driven approach for computing relaxations, BCDR achieves one to two orders of magnitude improvements on runtime performance when compared to state-of-the-art numerical solvers.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {425–490},
numpages = {66}
}

@article{10.5555/3207692.3207701,
author = {Eiter, Thomas and Weinzierl, Antonius},
title = {Preference-Based Inconsistency Management in Multi-Context Systems},
year = {2017},
issue_date = {September 2017},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {60},
number = {1},
issn = {1076-9757},
abstract = {Multi-Context Systems (MCS) are a powerful framework for interlinking possibly heterogeneous, autonomous knowledge bases, where information can be exchanged among knowledge bases by designated bridge rules with negation as failure. An acknowledged issue with MCS is inconsistency that arises due to the information exchange. To remedy this problem, inconsistency removal has been proposed in terms of repairs, which modify bridge rules based on suitable notions for diagnosis of inconsistency. In general, multiple diagnoses and repairs do exist; this leaves the user, who arguably may oversee the inconsistency removal, with the task of selecting some repair among all possible ones. To aid in this regard, we extend the MCS framework with preference information for diagnoses, such that undesired diagnoses are filtered out and diagnoses that are most preferred according to a preference ordering are selected. We consider preference information at a generic level and develop meta-reasoning techniques on diagnoses in MCS that can be exploited to reduce preference-based selection of diagnoses to computing ordinary subset-minimal diagnoses in an extended MCS. We describe two meta-reasoning encodings for preference orders: the first is conceptually simple but may incur an exponential blowup. The second is increasing only linearly in size and based on duplicating the original MCS. The latter requires nondeterministic guessing if a subset-minimal among all most preferred diagnoses should be computed. However, a complexity analysis of diagnoses shows that this is worst-case optimal, and that in general, preferred diagnoses have the same complexity as subset-minimal ordinary diagnoses. Furthermore, (subset-minimal) filtered diagnoses and (subset-minimal) ordinary diagnoses also have the same complexity.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {347–424},
numpages = {78}
}

@article{10.5555/3207692.3207700,
author = {Lam, William and Kask, Kalev and Larrosa, Javier and Dechter, Rina},
title = {Residual-Guided Look-Ahead in and/or Search for Graphical Models},
year = {2017},
issue_date = {September 2017},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {60},
number = {1},
issn = {1076-9757},
abstract = {We introduce the concept of local bucket error for the mini-bucket heuristics and show how it can be used to improve the power of AND/OR search for combinatorial optimization tasks in graphical models (e.g. MAP/MPE or weighted CSPs). The local bucket error illuminates how the heuristic errors are distributed in the search space, guided by the mini-bucket heuristic. We present and analyze methods for compiling the local bucket-errors (exactly and approximately) and show that they can be used to yield an effective tool for balancing look-ahead overhead during search. This can be especially instrumental when memory is restricted, accommodating the generation of only weak compiled heuristics. We illustrate the impact of the proposed schemes in an extensive empirical evaluation for both finding exact solutions and anytime suboptimal solutions.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {287–346},
numpages = {60}
}

@article{10.5555/3207692.3207699,
author = {Kariotoglou, Nikolaos and Kamgarpour, Maryam and Summers, Tyler H. and Lygeros, John},
title = {The Linear Programming Approach to Reach-Avoid Problems for Markov Decision Processes},
year = {2017},
issue_date = {September 2017},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {60},
number = {1},
issn = {1076-9757},
abstract = {One of the most fundamental problems in Markov decision processes is analysis and control synthesis for safety and reachability specifications. We consider the stochastic reach-avoid problem, in which the objective is to synthesize a control policy to maximize the probability of reaching a target set at a given time, while staying in a safe set at all prior times. We characterize the solution to this problem through an infinite dimensional linear program. We then develop a tractable approximation to the infinite dimensional linear program through finite dimensional approximations of the decision space and constraints. For a large class of Markov decision processes modeled by Gaussian mixtures kernels we show that through a proper selection of the finite dimensional space, one can further reduce the computational complexity of the resulting linear program. We validate the proposed method and analyze its potential with numerical case studies.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {263–285},
numpages = {23}
}

@article{10.5555/3207692.3207698,
author = {Cozman, Fabio Gagliardi and Mau\'{a}, Denis Deratani},
title = {On the Semantics and Complexity of Probabilistic Logic Programs},
year = {2017},
issue_date = {September 2017},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {60},
number = {1},
issn = {1076-9757},
abstract = {We examine the meaning and the complexity of probabilistic logic programs that consist of a set of rules and a set of independent probabilistic facts (that is, programs based on Sato's distribution semantics). We focus on two semantics, respectively based on stable and on well-founded models. We show that the semantics based on stable models (referred to as the "credal semantics") produces sets of probability measures that dominate infinitely monotone Choquet capacities; we describe several useful consequences of this result. We then examine the complexity of inference with probabilistic logic programs. We distinguish between the complexity of inference when a probabilistic program and a query are given (the inferential complexity), and the complexity of inference when the probabilistic program is fixed and the query is given (the query complexity, akin to data complexity as used in database theory). We obtain results on the inferential and query complexity for acyclic, stratified, and normal propositional and relational programs; complexity reaches various levels of the counting hierarchy and even exponential levels.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {221–262},
numpages = {42}
}

@article{10.5555/3207692.3207697,
author = {Yang, Yinfei and Nenkova, Ani},
title = {Combining Lexical and Syntactic Features for Detecting Content-Dense Texts in News},
year = {2017},
issue_date = {September 2017},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {60},
number = {1},
issn = {1076-9757},
abstract = {Content-dense news report important factual information about an event in direct, succinct manner. Information seeking applications such as information extraction, question answering and summarization normally assume all text they deal with is content-dense. Here we empirically test this assumption on news articles from the business, U.S. international relations, sports and science journalism domains. Our findings clearly indicate that about half of the news texts in our study are in fact not content-dense and motivate the development of a supervised content-density detector. We heuristically label a large training corpus for the task and train a two-layer classifying model based on lexical and unlexicalized syntactic features. On manually annotated data, we compare the performance of domain-specific classifiers, trained on data only from a given news domain and a general classifier in which data from all four domains is pooled together. Our annotation and prediction experiments demonstrate that the concept of content density varies depending on the domain and that naive annotators provide judgement biased toward the stereotypical domain label. Domain-specific classifiers are more accurate for domains in which content-dense texts are typically fewer. Domain independent classifiers reproduce better naive crowdsourced judgements. Classification prediction is high across all conditions, around 80%.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {179–219},
numpages = {41}
}

@article{10.5555/3207692.3207696,
author = {Airiau, St\'{e}phane and Bonzon, Elise and Endriss, Ulle and Maudet, Nicolas and Rossit, Julien},
title = {Rationalisation of Profiles of Abstract Argumentation Frameworks: Characterisation and Complexity},
year = {2017},
issue_date = {September 2017},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {60},
number = {1},
issn = {1076-9757},
abstract = {Different agents may have different points of view. Following a popular approach in the artificial intelligence literature, this can be modelled by means of different abstract argumentation frameworks, each consisting of a set of arguments the agent is contemplating and a binary attack-relation between them. A question arising in this context is whether the diversity of views observed in such a profile of argumentation frameworks is consistent with the assumption that every individual argumentation framework is induced by a combination of, first, some basic factual attack-relation between the arguments and, second, the personal preferences of the agent concerned regarding the moral or social values the arguments under scrutiny relate to. We treat this question of rationalisability of a profile as an algorithmic problem and identify tractable and intractable cases. In doing so, we distinguish different constraints on admissible rationalisations, e.g., concerning the types of preferences used or the number of distinct values involved. We also distinguish two different semantics for rationalisability, which differ in the assumptions made on how agents treat attacks between arguments they do not report. This research agenda, bringing together ideas from abstract argumentation and social choice, is useful for understanding what types of profiles can reasonably be expected to occur in a multiagent system.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {149–177},
numpages = {29}
}

@article{10.5555/3207692.3207695,
author = {Oveisi, Mehrdad and Delgrande, James P. and Pelletier, Francis Jeffry and Popowich, Fred},
title = {Kernel Contraction and Base Dependence},
year = {2017},
issue_date = {September 2017},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {60},
number = {1},
issn = {1076-9757},
abstract = {The AGM paradigm of belief change studies the dynamics of belief states in light of new information. Finding, or even approximating, those beliefs that are dependent on or relevant to a change is valuable because, for example, it can narrow the set of beliefs considered during belief change operations. A strong intuition in this area is captured by G\"{a}rdenfors's preservation criterion (GPC), which suggests that formulas independent of a belief change should remain intact. GPC thus allows one to build dependence relations that are linked with belief change. Such dependence relations can in turn be used as a theoretical benchmark against which to evaluate other approximate dependence or relevance relations. Fari\~{n}as and Herzig axiomatize a dependence relation with respect to a belief set, and, based on GPC, they characterize the correspondence between AGM contraction functions and dependence relations. In this paper, we introduce base dependence as a relation between formulas with respect to a belief base, and prove a more general characterization that shows the correspondence between kernel contraction and base dependence. At this level of generalization, different types of base dependence emerge, which we show to be a result of possible redundancy in the belief base. We further show that one of these relations that emerge, strong base dependence, is parallel to saturated kernel contraction. We then prove that our latter characterization is a reversible generalization of Fari\~{n}as and Herzig's characterization. That is, in the special case when the underlying belief base is deductively closed (i.e., it is a belief set), strong base dependence reduces to dependence, and so do their respective characterizations. Finally, an intriguing feature of Fari\~{n}as and Herzig's formalism is that it meets other criteria for dependence, namely, Keynes's conjunction criterion for dependence (CCD) and G\"{a}rdenfors's conjunction criterion for independence (CCI). We prove that our base dependence formalism also meets these criteria. Even more interestingly, we offer a more specific criterion that implies both CCD and CCI, and show our base dependence formalism also meets this new criterion.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {97–148},
numpages = {52}
}

@article{10.5555/3207692.3207694,
author = {Gebser, Martin and Maratea, Marco and Ricca, Francesco},
title = {The Sixth Answer Set Programming Competition},
year = {2017},
issue_date = {September 2017},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {60},
number = {1},
issn = {1076-9757},
abstract = {Answer Set Programming (ASP) is a well-known paradigm of declarative programming with roots in logic programming and non-monotonic reasoning. Similar to other closely related problem-solving technologies, such as SAT/SMT, QBF, Planning and Scheduling, advancements in ASP solving are assessed in competition events. In this paper, we report about the design and results of the Sixth ASP Competition, which was jointly organized by the University of Calabria (Italy), Aalto University (Finland), and the University of Genoa (Italy), in affiliation with the 13th International Conference on Logic Programming and Non-Monotonic Reasoning. This edition maintained some of the design decisions introduced in 2014, e.g., the conception of sub-tracks, the scoring scheme, and the adherence to a fixed modeling language in order to push the adoption of the ASP-Core-2 standard. On the other hand, it featured also some novelties, like a benchmark selection stage classifying instances according to their empirical hardness, and a "Marathon" track where the top-performing systems are given more time for solving hard benchmarks.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {41–95},
numpages = {55}
}

@article{10.5555/3207692.3207693,
author = {Wallner, Johannes P. and Niskanen, Andreas and J\"{a}rvisalo, Matti},
title = {Complexity Results and Algorithms for Extension Enforcement in Abstract Argumentation},
year = {2017},
issue_date = {September 2017},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {60},
number = {1},
issn = {1076-9757},
abstract = {Argumentation is an active area of modern artificial intelligence (AI) research, with connections to a range of fields, from computational complexity theory and knowledge representation and reasoning to philosophy and social sciences, as well as application-oriented work in domains such as legal reasoning, multi-agent systems, and decision support. Argumentation frameworks (AFs) of abstract argumentation have become the graph-based formal model of choice for many approaches to argumentation in AI, with semantics defining sets of jointly acceptable arguments, i.e., extensions. Understanding the dynamics of AFs has been recently recognized as an important topic in the study of argumentation in AI. In this work, we focus on the so-called extension enforcement problem in abstract argumentation as a recently proposed form of argumentation dynamics. We provide a nearly complete computational complexity map of argument-fixed extension enforcement under various major AF semantics, with results ranging from polynomial-time algorithms to completeness for the second level of the polynomial hierarchy. Complementing the complexity results, we propose algorithms for NP-hard extension enforcement based on constraint optimization under the maximum satisfiability (MaxSAT) paradigm. Going beyond NP, we propose novel MaxSAT-based counterexample-guided abstraction refinement procedures for the second-level complete problems and present empirical results on a prototype system constituting the first approach to extension enforcement in its generality.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {1–40},
numpages = {40}
}

@article{10.5555/3176788.3176807,
author = {Gent, Ian P. and Jefferson, Christopher and Nightingale, Peter},
title = {Complexity of N-Queens Completion},
year = {2017},
issue_date = {May 2017},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {59},
number = {1},
issn = {1076-9757},
abstract = {The n-Queens problem is to place n chess queens on an n by n chessboard so that no two queens are on the same row, column or diagonal. The n-Queens Completion problem is a variant, dating to 1850, in which some queens are already placed and the solver is asked to place the rest, if possible. We show that n-Queens Completion is both NP-Complete and #P-Complete. A corollary is that any non-attacking arrangement of queens can be included as a part of a solution to a larger n-Queens problem. We introduce generators of random instances for n-Queens Completion and the closely related Blocked n-Queens and Excluded Diagonals Problem. We describe three solvers for these problems, and empirically analyse the hardness of randomly generated instances. For Blocked n-Queens and the Excluded Diagonals Problem, we show the existence of a phase transition associated with hard instances as has been seen in other NP-Complete problems, but a natural generator for n-Queens Completion did not generate consistently hard instances. The significance of this work is that the n-Queens problem has been very widely used as a benchmark in Artificial Intelligence, but conclusions on it are often disputable because of the simple complexity of the decision problem. Our results give alternative benchmarks which are hard theoretically and empirically, but for which solving techniques designed for n-Queens need minimal or no change.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {815–848},
numpages = {34}
}

@article{10.5555/3176788.3176806,
author = {Allen, Thomas E. and Goldsmith, Judy and Justice, Hayden Elizabeth and Mattei, Nicholas and Raines, Kayla},
title = {Uniform Random Generation and Dominance Testing for CP-Nets},
year = {2017},
issue_date = {May 2017},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {59},
number = {1},
issn = {1076-9757},
abstract = {The generation of preferences represented as CP-nets for experiments and empirical testing has typically been done in an ad hoc manner that may have introduced a large statistical bias in previous experimental work. We present novel polynomial-time algorithms for generating CP-nets with n nodes and maximum in-degree c uniformly at random. We extend this result to several statistical cultures commonly used in the social choice and preference reasoning literature. A CP-net is composed of both a graph and underlying cp-statements; our algorithm is the first to provably generate both the graph structure and cp-statements, and hence the underlying preference orders themselves, uniformly at random. We have released this code as a free and open source project. We use the uniform generation algorithm to investigate the maximum and expected flipping lengths, i.e., the maximum length over all outcomes o1 and o2, of a minimal proof that o1 is preferred to o2. Using our new statistical evidence, we conjecture that, for CP-nets with binary variables and complete conditional preference tables, the expected flipping length is polynomial in the number of preference variables. This has positive implications for the usability of CP-nets as compact preference models.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {771–813},
numpages = {43}
}

@article{10.5555/3176788.3176805,
author = {Sonu, Ekhlas and Chen, Yingke and Doshi, Prashant},
title = {Decision-Theoretic Planning under Anonymity in Agent Populations},
year = {2017},
issue_date = {May 2017},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {59},
number = {1},
issn = {1076-9757},
abstract = {We study the problem of self-interested planning under uncertainty in settings shared with more than a thousand other agents, each of which plans at its own individual level. We refer to such large numbers of agents as an agent population. The decision-theoretic formalism of interactive partially observable Markov decision process (I-POMDP) is used to model the agent's self-interested planning. The first contribution of this article is a method for drastically scaling the finitely-nested I-POMDP to certain agent populations for the first time. Our method exploits two types of structure that is often exhibited by agent populations - anonymity and context-specific independence. We present a variant called the many-agent I-POMDP that models both these types of structure to plan efficiently under uncertainty in multiagent settings. In particular, the complexity of the belief update and solution in the many-agent I-POMDP is polynomial in the number of agents compared with the exponential growth that challenges the original framework.While exploiting structure helps mitigate the curse of many agents, the well-known curse of history that afflicts I-POMDPs continues to challenge scalability in terms of the planning horizon. The second contribution of this article is an application of the branch-and-bound scheme to reduce the exponential growth of the search tree for look ahead. For this, we introduce new fast-computing upper and lower bounds for the exact value function of the many-agent I-POMDP. This speeds up the look-ahead computations without trading off optimality, and reduces both memory and run time complexity. The third contribution is a comprehensive empirical evaluation of the methods on three new problems domains - policing large protests, controlling traffic congestion at a busy intersection, and improving the AI for the popular Clash of Clans multiplayer game. We demonstrate the feasibility of exact self-interested planning in these large problems, and that our methods for speeding up the planning are effective. Altogether, these contributions represent a principled and significant advance toward moving self-interested planning under uncertainty to real-world applications.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {725–770},
numpages = {46}
}

@article{10.5555/3176788.3176804,
author = {Davis, Ernest},
title = {Logical Formalizations of Commonsense Reasoning: A Survey},
year = {2017},
issue_date = {May 2017},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {59},
number = {1},
issn = {1076-9757},
abstract = {Commonsense reasoning is in principle a central problem in artificial intelligence, but it is a very difficult one. One approach that has been pursued since the earliest days of the field has been to encode commonsense knowledge as statements in a logic-based representation language and to implement commonsense reasoning as some form of logical inference. This paper surveys the use of logic-based representations of commonsense knowledge in artificial intelligence research.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {651–723},
numpages = {73}
}

@article{10.5555/3176788.3176803,
author = {Wah, Elaine and Wright, Mason and Wellman, Michael P.},
title = {Welfare Effects of Market Making in Continuous Double Auctions},
year = {2017},
issue_date = {May 2017},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {59},
number = {1},
issn = {1076-9757},
abstract = {We investigate the effects of market making on market performance, focusing on allocative efficiency as well as gains from trade accrued by background traders. We employ empirical simulation-based methods to evaluate heuristic strategies for market makers as well as background investors in a variety of complex trading environments. Our market model incorporates private and common valuation elements, with dynamic fundamental value and asymmetric information. In this context, we compare the surplus achieved by background traders in strategic equilibrium, with and without a market maker. Our findings indicate that the presence of the market maker strongly tends to increase total welfare across various environments. Market-maker profit may or may not exceed the welfare gain, thus the effect on background-investor surplus is ambiguous. We find that market making tends to benefit investors in relatively thin markets, and situations where background traders are impatient, due to limited trading opportunities. The presence of additional market makers increases these benefits, as competition drives the market makers to provide liquidity at lower price spreads. A thorough sensitivity analysis indicates that these results are robust to reasonable changes in model parameters.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {613–650},
numpages = {38}
}

@article{10.5555/3176788.3176802,
author = {Hunter, Anthony and Thimm, Matthias},
title = {Probabilistic Reasoning with Abstract Argumentation Frameworks},
year = {2017},
issue_date = {May 2017},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {59},
number = {1},
issn = {1076-9757},
abstract = {Abstract argumentation offers an appealing way of representing and evaluating arguments and counterarguments. This approach can be enhanced by considering probability assignments on arguments, allowing for a quantitative treatment of formal argumentation. In this paper, we regard the assignment as denoting the degree of belief that an agent has in an argument being acceptable. While there are various interpretations of this, an example is how it could be applied to a deductive argument. Here, the degree of belief that an agent has in an argument being acceptable is a combination of the degree to which it believes the premises, the claim, and the derivation of the claim from the premises. We consider constraints on these probability assignments, inspired by crisp notions from classical abstract argumentation frameworks and discuss

license: Unlicense

repository: goyalkaraniit/acm-cr

repo_name: goyalkaraniit/acm-cr