text:
action is based. In addition to continuous feedback, T-R programs support parameter binding and recursion. A primary difference between T-R programs and many other circuit-based systems is that the circuitry of T-R programs is more compact; it is constructed at run time and thus does not have to anticipate all the contingencies that might arise over all possible runs. In addition, T-R programs are intuitive and easy to write and are written in a form that is compatible with automatic planning and learning methods. We briefly describe some experimental applications of T-R programs in the control of simulated and actual mobile robots.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {139–158},
numpages = {20}
}

@article{10.5555/1618595.1618601,
author = {Buchheit, Martin and Donini, Francesco M. and Schaerf, Andrea},
title = {Decidable Reasoning in Terminological Knowledge Representation Systems},
year = {1993},
issue_date = {August 1993},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {1},
number = {1},
issn = {1076-9757},
abstract = {Terminological knowledge representation systems (TKRSs) are tools for designing and using knowledge bases that make use of terminological languages (or concept languages). We analyze from a theoretical point of view a TKRS whose capabilities go beyond the ones of presently available TKRSs. The new features studied, often required in practical applications, can be summarized in three main points. First, we consider a highly expressive terminological language, called ALCNR, including general complements of concepts, number restrictions and role conjunction. Second, we allow to express inclusion statements between general concepts, and terminological cycles as a particular case. Third, we prove the decidability of a number of desirable TKRS-deduction services (like satisfiability, subsumption and instance checking) through a sound, complete and terminating calculus for reasoning in ALCNR-knowledge bases. Our calculus extends the general technique of constraint systems. As a byproduct of the proof, we get also the result that inclusion statements in ALCNR can be simulated by terminological cycles, if descriptive semantics is adopted.},
journal = {J. Artif. Int. Res.},
month = dec,
pages = {109–138},
numpages = {30}
}

@article{10.5555/1618595.1618600,
author = {Bergadano, Francesco and Gunetti, Daniele and Trinchero, Umberto},
title = {The Difficulties of Learning Logic Programs with Cut},
year = {1993},
issue_date = {August 1993},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {1},
number = {1},
issn = {1076-9757},
abstract = {As real logic programmers normally use cut (!), an effective learning procedure for logic programs should be able to deal with it. Because the cut predicate has only a procedural meaning, clauses containing cut cannot be learned using an extensional evaluation method, as is done in most learning systems. On the other hand, searching a space of possible programs (instead of a space of independent clauses) is unfeasible. An alternative solution is to generate first a candidate base program which covers the positive examples, and then make it consistent by inserting cut where appropriate. The problem of learning programs with cut has not been investigated before and this seems to be a natural and reasonable approach. We generalize this scheme and investigate the difficulties that arise. Some of the major shortcomings are actually caused, in general, by the need for intensional evaluation. As a conclusion, the analysis of this paper suggests, on precise and technical grounds, that learning cut is difficult, and current induction techniques should probably be restricted to purely declarative logic languages.},
journal = {J. Artif. Int. Res.},
month = nov,
pages = {91–107},
numpages = {17}
}

@article{10.5555/1618595.1618599,
author = {Schlimmer, Jeffrey C. and Hermens, Leonard A.},
title = {Software Agents: Completing Patterns and Constructing User Interfaces},
year = {1993},
issue_date = {August 1993},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {1},
number = {1},
issn = {1076-9757},
abstract = {To support the goal of allowing users to record and retrieve information, this paper describes an interactive note-taking system for pen-based computers with two distinctive features. First, it actively predicts what the user is going to write. Second, it automatically constructs a custom, button-box user interface on request. The system is an example of a learning-apprentice software-agent. A machine learning component characterizes the syntax and semantics of the user's information. A performance system uses this learned information to generate completion strings and construct a user interface.},
journal = {J. Artif. Int. Res.},
month = nov,
pages = {61–89},
numpages = {29}
}

@article{10.5555/1618595.1618598,
author = {Gent, Ian P. and Walsh, Toby},
title = {An Empirical Analysis of Search in GSAT},
year = {1993},
issue_date = {August 1993},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {1},
number = {1},
issn = {1076-9757},
abstract = {We describe an extensive study of search in GSAT, an approximation procedure for propositional satisfiability. GSAT performs greedy hill-climbing on the number of satisfied clauses in a truth assignment. Our experiments provide a more complete picture of GSAT's search than previous accounts. We describe in detail the two phases of search: rapid hill-climbing followed by a long plateau search. We demonstrate that when applied to randomly generated 3-SAT problems, there is a very simple scaling with problem size for both the mean number of satisfied clauses and the mean branching rate. Our results allow us to make detailed numerical conjectures about the length of the hill-climbing phase, the average gradient of this phase, and to conjecture that both the average score and average branching rate decay exponentially during plateau search. We end by showing how these results can be used to direct future theoretical analysis. This work provides a case study of how computer experiments can be used to improve understanding of the theoretical properties of algorithms.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {47–59},
numpages = {13}
}

@article{10.5555/1618595.1618597,
author = {Ginsberg, Matthew L.},
title = {Dynamic Backtracking},
year = {1993},
issue_date = {August 1993},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {1},
number = {1},
issn = {1076-9757},
abstract = {Because of their occasional need to return to shallow points in a search tree, existing backtracking methods can sometimes erase meaningful progress toward solving a search problem. In this paper, we present a method by which backtrack points can be moved deeper in the search space, thereby avoiding this difficulty. The technique developed is a variant of dependency-directed backtracking that uses only polynomial space while still providing useful control information and retaining the completeness guarantees provided by earlier approaches.},
journal = {J. Artif. Int. Res.},
month = aug,
pages = {25–46},
numpages = {22}
}

@article{10.5555/1618595.1618596,
author = {Wellman, Michael P.},
title = {A Market-Oriented Programming Environment and Its Application to Distributed Multicommodity Flow Problems},
year = {1993},
issue_date = {August 1993},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {1},
number = {1},
issn = {1076-9757},
abstract = {Market price systems constitute a well-understood class of mechanisms that under certain conditions provide effective decentralization of decision making with minimal communication overhead. In a market-oriented programming approach to distributed problem solving, we derive the activities and resource allocations for a set of computational agents by computing the competitive equilibrium of an artificial economy. WALRAS provides basic constructs for defining computational market structures, and protocols for deriving their corresponding price equilibria. In a particular realization of this approach for a form of multicommodity flow problem, we see that careful construction of the decision process according to economic principles can lead to efficient distributed resource allocation, and that the behavior of the system can be meaningfully analyzed in economic terms.},
journal = {J. Artif. Int. Res.},
month = aug,
pages = {1–23},
numpages = {23}
}

@article{10.1613/jair.1.11675,
author = {Jauhiainen, Tommi and Lui, Marco and Zampieri, Marcos and Baldwin, Timothy and Lind\'{e}n, Krister},
title = {Automatic Language Identification in Texts: A Survey},
year = {2019},
issue_date = {May 2019},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {65},
number = {1},
issn = {1076-9757},
url = {https://doi.org/10.1613/jair.1.11675},
doi = {10.1613/jair.1.11675},
abstract = {Language identification ("LI") is the problem of determining the natural language that a document or part thereof is written in. Automatic LI has been extensively researched for over fifty years. Today, LI is a key part of many text processing pipelines, as text processing techniques generally assume that the language of the input text is known. Research in this area has recently been especially active. This article provides a brief history of LI research, and an extensive survey of the features and methods used in the LI literature. We describe the features and methods using a unified notation, to make the relationships between methods clearer. We discuss evaluation methods, applications of LI, as well as off-the-shelf LI systems that do not require training by the end user. Finally, we identify open issues, survey the work to date on each issue, and propose future directions for research in LI.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {675–682},
numpages = {8}
}

@article{10.1613/jair.1.11640,
author = {Ruder, Sebastian and Vuli\'{c}, Ivan and S\o{}gaard, Anders},
title = {A Survey of Cross-Lingual Word Embedding Models},
year = {2019},
issue_date = {May 2019},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {65},
number = {1},
issn = {1076-9757},
url = {https://doi.org/10.1613/jair.1.11640},
doi = {10.1613/jair.1.11640},
abstract = {Cross-lingual representations of words enable us to reason about word meaning in multilingual contexts and are a key facilitator of cross-lingual transfer when developing natural language processing models for low-resource languages. In this survey, we provide a comprehensive typology of cross-lingual word embedding models. We compare their data requirements and objective functions. The recurring theme of the survey is that many of the models presented in the literature optimize for the same objectives, and that seemingly different models are often equivalent, modulo optimization strategies, hyper-parameters, and such. We also discuss the different ways cross-lingual word embeddings are evaluated, as well as future challenges and research horizons.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {569–630},
numpages = {62}
}

@article{10.1613/jair.1.11635,
author = {Piacentini, Chiara and Bernardini, Sara and Beck, J. Christopher},
title = {Autonomous Target Search with Multiple Coordinated UAVs},
year = {2019},
issue_date = {May 2019},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {65},
number = {1},
issn = {1076-9757},
url = {https://doi.org/10.1613/jair.1.11635},
doi = {10.1613/jair.1.11635},
abstract = {Search and tracking is the problem of locating a moving target and following it to its destination. In this work, we consider a scenario in which the target moves across a large geographical area by following a road network and the search is performed by a team of unmanned aerial vehicles (UAVs). We formulate search and tracking as a combinatorial optimization problem and prove that the objective function is submodular. We exploit this property to devise a greedy algorithm. Although this algorithm does not offer strong theoretical guarantees because of the presence of temporal constraints that limit the feasibility of the solutions, it presents remarkably good performance, especially when several UAVs are available for the mission. As the greedy algorithm suffers when resources are scarce, we investigate two alternative optimization techniques: Constraint Programming (CP) and AI planning. Both approaches struggle to cope with large problems, and so we strengthen them by leveraging the greedy algorithm. We use the greedy solution to warm start the CP model and to devise a domain-dependent heuristic for planning. Our extensive experimental evaluation studies the scalability of the different techniques and identifies the conditions under which one approach becomes preferable to the others.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {519–568},
numpages = {50}
}

@article{10.1613/jair.1.11592,
author = {Zhang, Dianmu and Hannaford, Blake},
title = {IKBT: Solving Symbolic Inverse Kinematics with Behavior Tree},
year = {2019},
issue_date = {May 2019},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {65},
number = {1},
issn = {1076-9757},
url = {https://doi.org/10.1613/jair.1.11592},
doi = {10.1613/jair.1.11592},
abstract = {Inverse kinematics solves the problem of how to control robot arm joints to achieve desired end effector positions, which is critical to any robot arm design and implementations of control algorithms. It is a common misunderstanding that closed-form inverse kinematics analysis is solved. Popular software and algorithms, such as gradient descent or any multi-variant equations solving algorithm, claims solving inverse kinematics but only on the numerical level. While the numerical inverse kinematics solutions are relatively straightforward to obtain, these methods often fail, due to dependency on specific numerical values, even when the inverse kinematics solutions exist. Therefore, closed-form inverse kinematics analysis is superior, but there is no generalized automated algorithm. Up till now, the high-level logical reasoning involved in solving closed-form inverse kinematics made it hard to automate, so it's handled by human experts. We developed IKBT, a knowledge-based intelligent system that can mimic human experts' behaviors in solving closed-from inverse kinematics using Behavior Tree. Knowledge and rules used by engineers when solving closed-from inverse kinematics are encoded as actions in Behavior Tree. The order of applying these rules is governed by higher level composite nodes, which resembles the logical reasoning process of engineers. It is also the first time that the dependency of joint variables, an important issue in inverse kinematics analysis, is automatically tracked in graph form. Besides generating closed-form solutions, IKBT also explains its solving strategies in human (engineers) interpretable form. This is a proof-of-concept of using Behavior Trees to solve high-cognitive problems.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {457–486},
numpages = {30}
}

@article{10.1613/jair.1.11583,
author = {Fioretto, Ferdinando and Van Hentenryck, Pascal},
title = {Optstream: Releasing Time Series Privately},
year = {2019},
issue_date = {May 2019},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {65},
number = {1},
issn = {1076-9757},
url = {https://doi.org/10.1613/jair.1.11583},
doi = {10.1613/jair.1.11583},
abstract = {Many applications of machine learning and optimization operate on data streams. While these datasets are fundamental to fuel decision-making algorithms, often they contain sensitive information about individuals, and their usage poses significant privacy risks. Motivated by an application in energy systems, this paper presents OPTSTREAM, a novel algorithm for releasing differentially private data streams under the w-event model of privacy. OPTSTREAM is a 4-step procedure consisting of sampling, perturbation, reconstruction, and post-processing modules. First, the sampling module selects a small set of points to access in each period of interest. Then, the perturbation module adds noise to the sampled data points to guarantee privacy. Next, the reconstruction module reassembles non-sampled data points from the perturbed sample points. Finally, the post-processing module uses convex optimization over the privacy-preserving output of the previous modules, as well as the privacy-preserving answers of additional queries on the data stream, to improve accuracy by redistributing the added noise. OPTSTREAM is evaluated on a test case involving the release of a real data stream from the largest European transmission operator. Experimental results show that OPTSTREAM may not only improve the accuracy of state-of-the-art methods by at least one order of magnitude but also supports accurate load forecasting on the privacy-preserving data.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {423–456},
numpages = {34}
}

@article{10.1613/jair.1.11582,
author = {Ismaili, Anisse and Hamada, Naoto and Zhang, Yuzhe and Suzuki, Takamasa and Yokoo, Makoto},
title = {Weighted Matching Markets with Budget Constraints},
year = {2019},
issue_date = {May 2019},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {65},
number = {1},
issn = {1076-9757},
url = {https://doi.org/10.1613/jair.1.11582},
doi = {10.1613/jair.1.11582},
abstract = {We investigate markets with a set of students on one side and a set of colleges on the other. A student and college can be linked by a weighted contract that defines the student's wage, while a college's budget for hiring students is limited. Stability is a crucial requirement for matching mechanisms to be applied in the real world. A standard stability requirement is coalitional stability, i.e., no pair of a college and group of students has any incentive to deviate. We find that a coalitionally stable matching is not guaranteed to exist, verifying the coalitional stability for a given matching is coNP-complete, and the problem of finding whether a coalitionally stable matching exists in a given market, is Σ2P-complete: NPNP-complete. Other negative results also hold when blocking coalitions contain at most two students and one college. Given these computational hardness results, we pursue a weaker stability requirement called pairwise stability, where no pair of a college and single student has an incentive to deviate. Unfortunately, a pairwise stable matching is not guaranteed to exist either. Thus, we consider a restricted market called a typed weighted market, in which students are partitioned into types that induce their possible wages. We then design a strategy-proof and Pareto efficient mechanism that works in polynomial-time for computing a pairwise stable matching in typed weighted markets.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {393–421},
numpages = {29}
}

@article{10.1613/jair.1.11576,
author = {Gnad, Daniel and Hoffmann, J\"{o}rg and Wehrle, Martin},
title = {Strong Stubborn Set Pruning for Star-Topology Decoupled State Space Search},
year = {2019},
issue_date = {May 2019},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {65},
number = {1},
issn = {1076-9757},
url = {https://doi.org/10.1613/jair.1.11576},
doi = {10.1613/jair.1.11576},
abstract = {Analyzing reachability in large discrete transition systems is an important sub-problem in several areas of AI, and of CS in general. State space search is a basic method for conducting such an analysis. A wealth of techniques have been proposed to reduce the search space without affecting the existence of (optimal) solution paths. In particular, strong stubborn set (SSS) pruning is a prominent such method, analyzing action dependencies to prune commutative parts of the search space. We herein show how to apply this idea to star-topology decoupled state space search, a recent search reformulation method invented in the context of classical AI planning.Star-topology decoupled state space search, short decoupled search, addresses planning tasks where a single center component interacts with several leaf components. The search exploits a form of conditional independence arising in this setting: given a fixed path πC of transitions by the center, the possible leaf moves compliant with πC are independent across the leaves. Decoupled search thus searches over center paths only, maintaining the compliant paths for each leaf separately. This avoids the enumeration of combined states across leaves.Just like standard search, decoupled search is adversely affected by commutative parts of its search space. The adaptation of strong stubborn set pruning is challenging due to the more complex structure of the search space, and the resulting ways in which action dependencies may affect the search. We spell out how to address this challenge, designing optimality-preserving decoupled strong stubborn set (DSSS) pruning methods. We introduce a design for star topologies in full generality, as well as simpler design variants for the practically relevant fork and inverted fork special cases. We show that there are cases where DSSS pruning is exponentially more effective than both, decoupled search and SSS pruning, exhibiting true synergy where the whole is more than the sum of its parts. Empirically, DSSS pruning reliably inherits the best of its components, and sometimes outperforms both.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {343–392},
numpages = {50}
}

@article{10.1613/jair.1.11569,
author = {Pineda, Luis and Zilberstein, Shlomo},
title = {Probabilistic Planning with Reduced Models},
year = {2019},
issue_date = {May 2019},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {65},
number = {1},
issn = {1076-9757},
url = {https://doi.org/10.1613/jair.1.11569},
doi = {10.1613/jair.1.11569},
abstract = {Reduced models are simplified versions of a given domain, designed to accelerate the planning process. Interest in reduced models has grown since the surprising success of determinization in the first international probabilistic planning competition, leading to the development of several enhanced determinization techniques. To address the drawbacks of previous determinization methods, we introduce a family of reduced models in which probabilistic outcomes are classified as one of two types: primary and exceptional. In each model that belongs to this family of reductions, primary outcomes can occur an unbounded number of times per trajectory, while exceptions can occur at most a finite number of times, specified by a parameter. Distinct reduced models are characterized by two parameters: the maximum number of primary outcomes per action, and the maximum number of occurrences of exceptions per trajectory. This family of reductions generalizes the well-known most-likely-outcome determinization approach, which includes one primary outcome per action and zero exceptional outcomes per plan. We present a framework to determine the benefits of planning with reduced models, and develop a continual planning approach that handles situations where the number of exceptions exceeds the specified bound during plan execution. Using this framework, we compare the performance of various reduced models and consider the challenge of generating good ones automatically. We show that each one of the dimensions--allowing more than one primary outcome or planning for some limited number of exceptions--could improve performance relative to standard determinization. The results place previous work on determinization in a broader context and lay the foundation for a systematic exploration of the space of model reductions.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {271–306},
numpages = {36}
}

@article{10.1613/jair.1.11551,
author = {Keren, Sarah and Gal, Avigdor and Karpas, Erez},
title = {Goal Recognition Design in Deterministic Environments},
year = {2019},
issue_date = {May 2019},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {65},
number = {1},
issn = {1076-9757},
url = {https://doi.org/10.1613/jair.1.11551},
doi = {10.1613/jair.1.11551},
abstract = {Goal recognition design (GRD) facilitates understanding the goals of acting agents through the analysis and redesign of goal recognition models, thus offering a solution for assessing and minimizing the maximal progress of any agent in the model before goal recognition is guaranteed. In a nutshell, given a model of a domain and a set of possible goals, a solution to a GRD problem determines (1) the extent to which actions performed by an agent within the model reveal the agent's objective; and (2) how best to modify the model so that the objective of an agent can be detected as early as possible. This approach is relevant to any domain in which rapid goal recognition is essential and the model design can be controlled. Applications include intrusion detection, assisted cognition, computer games, and human-robot collaboration.A GRD problem has two components: the analyzed goal recognition setting, and a design model specifying the possible ways the environment in which agents act can be modified so as to facilitate recognition. This work formulates a general framework for GRD in deterministic and partially observable environments, and offers a toolbox of solutions for evaluating and optimizing model quality for various settings.For the purpose of evaluation we suggest the worst case distinctiveness (WCD) measure, which represents the maximal cost of a path an agent may follow before its goal can be inferred by a goal recognition system. We offer novel compilations to classical planning for calculating WCD in settings where agents are bounded-suboptimal. We then suggest methods for minimizing WCD by searching for an optimal redesign strategy within the space of possible modifications, and using pruning to increase efficiency. We support our approach with an empirical evaluation that measures WCD in a variety of GRD settings and tests the efficiency of our compilation-based methods for computing it. We also examine the effectiveness of reducing WCD via redesign and the performance gain brought about by our proposed pruning strategy.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {209–269},
numpages = {61}
}

@article{10.1613/jair.1.11529,
author = {Peitl, Tom\'{a}\v{s} and Slivovsky, Friedrich and Szeider, Stefan},
title = {Dependency Learning for QBF},
year = {2019},
issue_date = {May 2019},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {65},
number = {1},
issn = {1076-9757},
url = {https://doi.org/10.1613/jair.1.11529},
doi = {10.1613/jair.1.11529},
abstract = {Quantified Boolean Formulas (QBFs) can be used to succinctly encode problems from domains such as formal verification, planning, and synthesis. One of the main approaches to QBF solving is Quantified Conflict Driven Clause Learning (QCDCL). By default, QCDCL assigns variables in the order of their appearance in the quantifier prefix so as to account for dependencies among variables. Dependency schemes can be used to relax this restriction and exploit independence among variables in certain cases, but only at the cost of nontrivial interferences with the proof system underlying QCDCL. We introduce dependency learning, a new technique for exploiting variable independence within QCDCL that allows solvers to learn variable dependencies on the fly. The resulting version of QCDCL enjoys improved propagation and increased flexibility in choosing variables for branching while retaining ordinary (long-distance) Q-resolution as its underlying proof system. We show that dependency learning can achieve exponential speedups over ordinary QCDCL. Experiments on standard benchmark sets demonstrate the effectiveness of this technique.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {181–208},
numpages = {28}
}

@article{10.1613/jair.1.11524,
author = {Sridharan, Mohan and Gelfond, Michael and Zhang, Shiqi and Wyatt, Jeremy},
title = {REBA: A Refinement-Based Architecture for Knowledge Representation and Reasoning in Robotics},
year = {2019},
issue_date = {May 2019},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {65},
number = {1},
issn = {1076-9757},
url = {https://doi.org/10.1613/jair.1.11524},
doi = {10.1613/jair.1.11524},
abstract = {This article describes REBA, a knowledge representation and reasoning architecture for robots that is based on tightly-coupled transition diagrams of the domain at two different levels of granularity. An action language is extended to support non-boolean fluents and non-deterministic causal laws, and used to describe the domain's transition diagrams, with the fine-resolution transition diagram being defined as a refinement of the coarse-resolution transition diagram. The coarse-resolution system description, and a history that includes prioritized defaults, are translated into an Answer Set Prolog (ASP) program. For any given goal, inference in the ASP program provides a plan of abstract actions. To implement each such abstract action, the robot automatically zooms to the part of the fine-resolution transition diagram relevant to this abstract transition. The zoomed fine-resolution system description, and a probabilistic representation of the uncertainty in sensing and actuation, are used to construct a partially observable Markov decision process (POMDP). The policy obtained by solving the POMDP is invoked repeatedly to implement the abstract transition as a sequence of concrete actions. The fine-resolution outcomes of executing these concrete actions are used to infer coarse-resolution outcomes that are added to the coarse-resolution history and used for subsequent coarse-resolution reasoning. The architecture thus combines the complementary strengths of declarative programming and probabilistic graphical models to represent and reason with non-monotonic logic-based and probabilistic descriptions of uncertainty and incomplete domain knowledge. In addition, we describe a general methodology for the design of software components of a robot based on these knowledge representation and reasoning tools, and provide a path for proving the correctness of these components. The architecture is evaluated in simulation and on a mobile robot finding and moving target objects to desired locations in indoor domains, to show that the architecture supports reliable and efficient reasoning with violation of defaults, noisy observations and unreliable actions, in complex domains.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {87–180},
numpages = {94}
}

@article{10.1613/jair.1.11494,
author = {Telang, Pankaj R. and Singh, Munindar P. and Yorke-Smith, Neil},
title = {A Coupled Operational Semantics for Goals and Commitments},
year = {2019},
issue_date = {May 2019},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {65},
number = {1},
issn = {1076-9757},
url = {https://doi.org/10.1613/jair.1.11494},
doi = {10.1613/jair.1.11494},
abstract = {Commitments capture how an agent relates to another agent, whereas goals describe states of the world that an agent is motivated to bring about. Commitments are elements of the social state of a set of agents whereas goals are elements of the private states of individual agents. It makes intuitive sense that goals and commitments are understood as being complementary to each other. More importantly, an agent's goals and commitments ought to be coherent, in the sense that an agent's goals would lead it to adopt or modify relevant commitments and an agent's commitments would lead it to adopt or modify relevant goals. However, despite the intuitive naturalness of the above connections, they have not been adequately studied in a formal framework. This article provides a combined operational semantics for goals and commitments by relating their respective life cycles as a basis for how these concepts (1) cohere for an individual agent and (2) engender cooperation among agents. Our semantics yields important desirable properties of convergence of the configurations of cooperating agents, thereby delineating some theoretically well-founded yet practical modes of cooperation in a multiagent system.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {31–85},
numpages = {55}
}

@article{10.1613/jair.1.11478,
author = {Fran\c{c}ois-Lavet, Vincent and Rabusseau, Guillaume and Pineau, Joelle and Ernst, Damien and Fonteneau, Raphael},
title = {On Overfitting and Asymptotic Bias in Batch Reinforcement Learning with Partial Observability},
year = {2019},
issue_date = {May 2019},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {65},
number = {1},
issn = {1076-9757},
url = {https://doi.org/10.1613/jair.1.11478},
doi = {10.1613/jair.1.11478},
abstract = {This paper provides an analysis of the tradeoff between asymptotic bias (suboptimality with unlimited data) and overfitting (additional suboptimality due to limited data) in the context of reinforcement learning with partial observability. Our theoretical analysis formally characterizes that while potentially increasing the asymptotic bias, a smaller state representation decreases the risk of overfitting. This analysis relies on expressing the quality of a state representation by bounding L1 error terms of the associated belief states. Theoretical results are empirically illustrated when the state representation is a truncated history of observations, both on synthetic POMDPs and on a large-scale POMDP in the context of smartgrids, with real-world data. Finally, similarly to known results in the fully observable setting, we also briefly discuss and empirically illustrate how using function approximators and adapting the discount factor may enhance the tradeoff between asymptotic bias and overfitting in the partially observable context.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {1–30},
numpages = {30}
}

@article{10.1613/jair.1.11422,
author = {Botea, Adi and Kishimoto, Akihiro and Nikolova, Evdokia and Braghin, Stefano and Berlingerio, Michele and Daly, Elizabeth},
title = {Computing Multi-Modal Journey Plans under Uncertainty},
year = {2019},
issue_date = {May 2019},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {65},
number = {1},
issn = {1076-9757},
url = {https://doi.org/10.1613/jair.1.11422},
doi = {10.1613/jair.1.11422},
abstract = {Multi-modal journey planning, which allows multiple types of transport within a single trip, is becoming increasingly popular, due to a strong practical interest and an increasing availability of data. In real life, transport networks feature uncertainty. Yet, most approaches assume a deterministic environment, making plans more prone to failures such as missed connections and major delays in the arrival.This paper presents an approach to computing optimal contingent plans in multi-modal journey planning. The problem is modeled as a search in an And/Or state space. We describe search enhancements used on top of the AO* algorithm. Enhancements include admissible heuristics, multiple types of pruning that preserve the completeness and the optimality, and a hybrid search approach with a deterministic and a nondeterministic search. We demonstrate an NP-hardness result, with the hardness stemming from the dynamically changing distributions of the travel time random variables. We perform a detailed empirical analysis on realistic transport networks from cities such as Montpellier, Rome and Dublin. The results demonstrate the effectiveness of our algorithmic contributions, and the benefits of contingent plans as compared to standard sequential plans, when the arrival and departure times of buses are characterized by uncertainty.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {633–674},
numpages = {42}
}

@article{10.1613/jair.1.11366,
author = {Balaban, Edward and Johnson, Stephen B. and Kochenderfer, Mykel J.},
title = {Unifying System Health Management and Automated Decision Making},
year = {2019},
issue_date = {May 2019},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {65},
number = {1},
issn = {1076-9757},
url = {https://doi.org/10.1613/jair.1.11366},
doi = {10.1613/jair.1.11366},
abstract = {Health management of complex dynamic systems has evolved from simple automated alarms into a subfield of artificial intelligence with techniques for analyzing off-nominal conditions and generating responses. This evolution took place largely apart from the development of automated system control, planning, and scheduling (generally referred to in this work as decision making). While there have been efforts to establish an information exchange between system health management and decision making, successful practical implementations of integrated architectures remain limited. This article proposes that rather than being treated as connected yet distinct entities, system health management and decision making should be unified in their formulations. Enabled by advances in modeling and algorithms, we believe that a unified approach will increase systems' resilience to faults and improve their effectiveness. We overview the prevalent system health management methodology, illustrate its limitations through numerical examples, and describe a proposed unified approach. We then show how typical system health management concepts are accommodated in the proposed approach without loss of functionality or generality. A computational complexity analysis of the unified approach is also provided.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {487–518},
numpages = {32}
}

@article{10.1613/jair.1.11349,
author = {Jacobs, Bart},
title = {The Mathematics of Changing One's Mind, via Jeffrey's or via Pearl's Update Rule},
year = {2019},
issue_date = {May 2019},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {65},
number = {1},
issn = {1076-9757},
url = {https://doi.org/10.1613/jair.1.11349},
doi = {10.1613/jair.1.11349},
abstract = {Evidence in probabilistic reasoning may be 'hard' or 'soft', that is, it may be of yes/no form, or it may involve a strength of belief, in the unit interval [0, 1]. Reasoning with soft, [0, 1]-valued evidence is important in many situations but may lead to different, confusing interpretations. This paper intends to bring more mathematical and conceptual clarity to the field by shifting the existing focus from specification of soft evidence to accomodation of soft evidence. There are two main approaches, known as Jeffrey's rule and Pearl's method; they give different outcomes on soft evidence. This paper argues that they can be understood as correction and as improvement. It describes these two approaches as different ways of updating with soft evidence, highlighting their differences, similarities and applications. This account is based on a novel channel-based approach to Bayesian probability. Proper understanding of these two update mechanisms is highly relevant for inference, decision tools and probabilistic programming languages.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {783–806},
numpages = {24}
}

@article{10.1613/jair.1.11324,
author = {Walraven, Erwin and Spaan, Matthijs T. J.},
title = {Point-Based Value Iteration for Finite-Horizon POMDPs},
year = {2019},
issue_date = {May 2019},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {65},
number = {1},
issn = {1076-9757},
url = {https://doi.org/10.1613/jair.1.11324},
doi = {10.1613/jair.1.11324},
abstract = {Partially Observable Markov Decision Processes (POMDPs) are a popular formalism for sequential decision making in partially observable environments. Since solving POMDPs to optimality is a difficult task, point-based value iteration methods are widely used. These methods compute an approximate POMDP solution, and in some cases they even provide guarantees on the solution quality, but these algorithms have been designed for problems with an infinite planning horizon. In this paper we discuss why state-of-the-art point-based algorithms cannot be easily applied to finite-horizon problems that do not include discounting. Subsequently, we present a general point-based value iteration algorithm for finite-horizon problems which provides solutions with guarantees on solution quality. Furthermore, we introduce two heuristics to reduce the number of belief points considered during execution, which lowers the computational requirements. In experiments we demonstrate that the algorithm is an effective method for solving finite-horizon POMDPs.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {307–341},
numpages = {35}
}

@article{10.1613/jair.1.11468,
author = {Leite, Allan R. and Enembreck, Fabr\'{\i}cio},
title = {COOPT: Using Collective Behavior of Coupled Oscillators for Solving DCOP},
year = {2019},
issue_date = {January 2019},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {64},
number = {1},
issn = {1076-9757},
url = {https://doi.org/10.1613/jair.1.11468},
doi = {10.1613/jair.1.11468},
abstract = {The distributed constraint optimization problem (DCOP) has emerged as one of the most promising coordination techniques in multiagent systems. However, because DCOP is known to be NP-hard, the existing DCOP techniques are often unsuitable for large-scale applications, which require distributed and scalable algorithms to deal with severely limited computing and communication. In this paper, we present a novel approach to provide approximate solutions for large-scale, complex DCOPs. This approach introduces concepts of synchronization of coupled oscillators for speeding up the convergence process towards high-quality solutions. We propose a new anytime local search DCOP algorithm, called Coupled Oscillator OPTimization (COOPT), which amounts to iteratively solving a DCOP by agents exchanging local information that brings them to a consensus. We empirically evaluate COOPT on constraint networks involving hundreds of variables with different topologies, domains, and densities. Our experimental results demonstrate that COOPT outperforms other incomplete state-of-the-art DCOP algorithms, especially in terms of the agents' communication cost and solution quality.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {987–1023},
numpages = {37}
}

@article{10.1613/jair.1.11453,
author = {Combi, Carlo and Posenato, Roberto and Vigan\`{o}, Luca and Zavatteri, Matteo},
title = {Conditional Simple Temporal Networks with Uncertainty and Resources},
year = {2019},
issue_date = {January 2019},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {64},
number = {1},
issn = {1076-9757},
url = {https://doi.org/10.1613/jair.1.11453},
doi = {10.1613/jair.1.11453},
abstract = {Conditional simple temporal networks with uncertainty (CSTNUs) allow for the representation of temporal plans subject to both conditional constraints and uncertain durations. Dynamic controllability (DC) of CSTNUs ensures the existence of an execution strategy able to execute the network in real time (i.e., scheduling the time points under control) depending on how these two uncontrollable parts behave. However, CSTNUs do not deal with resources.In this paper, we define conditional simple temporal networks with uncertainty and resources (CSTNURs) by injecting resources and runtime resource constraints (RRCs) into the specification. Resources are mandatory for executing the time points and their availability is represented through temporal expressions, whereas RRCs restrict resource availability by further temporal constraints among resources.We provide a fully-automated encoding to translate any CSTNUR into an equivalent timed game automaton in polynomial time for a sound and complete DC-checking.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {931–985},
numpages = {55}
}

@article{10.1613/jair.1.11446,
author = {Grandi, Umberto and Grossi, Davide and Turrini, Paolo},
title = {Negotiable Votes Pre-Vote Negotiations in Binary Voting with Non-Manipulable Rules},
year = {2019},
issue_date = {January 2019},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {64},
number = {1},
issn = {1076-9757},
url = {https://doi.org/10.1613/jair.1.11446},
doi = {10.1613/jair.1.11446},
abstract = {We study voting games on binary issues, where voters hold an objective over the outcome of the collective decision and are allowed, before the vote takes place, to negotiate their ballots with the other participants. We analyse the voters' rational behaviour in the resulting two-phase game when ballots are aggregated via non-manipulable rules and, more specifically, quota rules. We show under what conditions undesirable equilibria can be removed and desirable ones sustained as a consequence of the pre-vote phase.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {895–929},
numpages = {35}
}

@article{10.1613/jair.1.11420,
author = {Eggensperger, Katharina and Lindauer, Marius and Hutter, Frank},
title = {Pitfalls and Best Practices in Algorithm Configuration},
year = {2019},
issue_date = {January 2019},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {64},
number = {1},
issn = {1076-9757},
url = {https://doi.org/10.1613/jair.1.11420},
doi = {10.1613/jair.1.11420},
abstract = {Good parameter settings are crucial to achieve high performance in many areas of artificial intelligence (AI), such as propositional satisfiability solving, AI planning, scheduling, and machine learning (in particular deep learning). Automated algorithm configuration methods have recently received much attention in the AI community since they replace tedious, irreproducible and error-prone manual parameter tuning and can lead to new state-of-the-art performance. However, practical applications of algorithm configuration are prone to several (often subtle) pitfalls in the experimental design that can render the procedure ineffective. We identify several common issues and propose best practices for avoiding them. As one possibility for automatically handling as many of these as possible, we also propose a tool called GenericWrapper4AC.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {861–893},
numpages = {33}
}

@article{10.1613/jair.1.11418,
author = {Amato, Christopher and Konidaris, George and Kaelbling, Leslie P. and How, Jonathan P.},
title = {Modeling and Planning with Macro-Actions in Decentralized POMDPs},
year = {2019},
issue_date = {January 2019},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {64},
number = {1},
issn = {1076-9757},
url = {https://doi.org/10.1613/jair.1.11418},
doi = {10.1613/jair.1.11418},
abstract = {Decentralized partially observable Markov decision processes (Dec-POMDPs) are general models for decentralized multi-agent decision making under uncertainty. However, they typically model a problem at a low level of granularity, where each agent's actions are primitive operations lasting exactly one time step. We address the case where each agent has macro-actions: temporally extended actions that may require different amounts of time to execute. We model macro-actions as options in a Dec-POMDP, focusing on actions that depend only on information directly available to the agent during execution. Therefore, we model systems where coordination decisions only occur at the level of deciding which macro-actions to execute. The core technical difficulty in this setting is that the options chosen by each agent no longer terminate at the same time. We extend three leading Dec-POMDP algorithms for policy generation to the macro-action case, and demonstrate their effectiveness in both standard benchmarks and a multi-robot coordination problem. The results show that our new algorithms retain agent coordination while allowing high-quality solutions to be generated for significantly longer horizons and larger state-spaces than previous Dec-POMDP methods. Furthermore, in the multi-robot domain, we show that, in contrast to most existing methods that are specialized to a particular problem class, our approach can synthesize control policies that exploit opportunities for coordination while balancing uncertainty, sensor information, and information about other agents.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {817–859},
numpages = {43}
}

@article{10.1613/jair.1.11408,
author = {Asuncion, Vernon and Zhang, Yan and Zhang, Heng and Li, Ruixuan},
title = {Polynomial and Exponential Bounded Logic Programs with Function Symbols: Some New Decidable Classes},
year = {2019},
issue_date = {January 2019},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {64},
number = {1},
issn = {1076-9757},
url = {https://doi.org/10.1613/jair.1.11408},
doi = {10.1613/jair.1.11408},
abstract = {A logic program with function symbols is called finitely ground if there is a finite propositional logic program whose stable models are exactly the same as the stable models of this program. Finite groundability is an important property for logic programs with function symbols because it makes feasible to compute such programs' stable models using traditional ASP solvers. In this paper, we introduce new decidable classes of finitely ground programs called poly-bounded and k-EXP-bounded programs, which, to the best of our knowledge, strictly contain all other decidable classes of finitely ground programs discovered so far in the literature. We also study the relevant complexity properties for these classes of programs. We prove that the membership complexities for poly-bounded and k-EXP-bounded programs are EXPTIME-complete and (k+1)-EXPTIME-complete, respectively.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {749–815},
numpages = {67}
}

@article{10.1613/jair.1.11400,
author = {Nguyen, Duc Thien and Yeoh, William and Lau, Hoong Chuin and Zivan, Roie},
title = {Distributed Gibbs: A Linear-Space Sampling-Based DCOP Algorithm},
year = {2019},
issue_date = {January 2019},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {64},
number = {1},
issn = {1076-9757},
url = {https://doi.org/10.1613/jair.1.11400},
doi = {10.1613/jair.1.11400},
abstract = {Researchers have used distributed constraint optimization problems (DCOPs) to model various multi-agent coordination and resource allocation problems. Very recently, Ottens et al. proposed a promising new approach to solve DCOPs that is based on confidence bounds via their Distributed UCT (DUCT) sampling-based algorithm. Unfortunately, its memory requirement per agent is exponential in the number of agents in the problem, which prohibits it from scaling up to large problems. Thus, in this article, we introduce two new sampling-based DCOP algorithms called Sequential Distributed Gibbs (SD-Gibbs) and Parallel Distributed Gibbs (PD-Gibbs). Both algorithms have memory requirements per agent that is linear in the number of agents in the problem. Our empirical results show that our algorithms can find solutions that are better than DUCT, run faster than DUCT, and solve some large problems that DUCT failed to solve due to memory limitations.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {705–748},
numpages = {44}
}

@article{10.1613/jair.1.11396,
author = {Da Silva, Felipe Leno and Costa, Anna Helena Reali},
title = {A Survey on Transfer Learning for Multiagent Reinforcement Learning Systems},
year = {2019},
issue_date = {January 2019},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {64},
number = {1},
issn = {1076-9757},
url = {https://doi.org/10.1613/jair.1.11396},
doi = {10.1613/jair.1.11396},
abstract = {Multiagent Reinforcement Learning (RL) solves complex tasks that require coordination with other agents through autonomous exploration of the environment. However, learning a complex task from scratch is impractical due to the huge sample complexity of RL algorithms. For this reason, reusing knowledge that can come from previous experience or other agents is indispensable to scale up multiagent RL algorithms. This survey provides a unifying view of the literature on knowledge reuse in multiagent RL. We define a taxonomy of solutions for the general knowledge reuse problem, providing a comprehensive discussion of recent progress on knowledge reuse in Multiagent Systems (MAS) and of techniques for knowledge reuse across agents (that may be actuating in a shared environment or not). We aim at encouraging the community to work towards reusing all the knowledge sources available in a MAS. For that, we provide an in-depth discussion of current lines of research and open questions.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {645–703},
numpages = {59}
}

@article{10.1613/jair.1.11395,
author = {Bienvenu, Meghyn and Bourgaux, Camille and Goasdou\'{e}, Fran\c{c}ois},
title = {Computing and Explaining Query Answers over Inconsistent DL-Lite Knowledge Bases},
year = {2019},
issue_date = {January 2019},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {64},
number = {1},
issn = {1076-9757},
url = {https://doi.org/10.1613/jair.1.11395},
doi = {10.1613/jair.1.11395},
abstract = {Several inconsistency-tolerant semantics have been introduced for querying inconsistent description logic knowledge bases. The first contribution of this paper is a practical approach for computing the query answers under three well-known such semantics, namely the AR, IAR and brave semantics, in the lightweight description logic DL-LiteR. We show that query answering under the intractable AR semantics can be performed efficiently by using IAR and brave semantics as tractable approximations and encoding the AR entailment problem as a propositional satisfiability (SAT) problem. The second issue tackled in this work is explaining why a tuple is a (non-)answer to a query under these semantics. We define explanations for positive and negative answers under the brave, AR and IAR semantics. We then study the computational properties of explanations in DL-LiteR. For each type of explanation, we analyze the data complexity of recognizing (preferred) explanations and deciding if a given assertion is relevant or necessary. We establish tight connections between intractable explanation problems and variants of SAT, enabling us to generate explanations by exploiting solvers for Boolean satisfaction and optimization problems. Finally, we empirically study the efficiency of our query answering and explanation framework using a benchmark we built upon the well-established LUBM benchmark.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {563–644},
numpages = {82}
}

@article{10.1613/jair.1.11388,
author = {Hern\'{a}ndez-Orallo, Jos\'{e}},
title = {AI Generality and Spearman's Law of Diminishing Returns},
year = {2019},
issue_date = {January 2019},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {64},
number = {1},
issn = {1076-9757},
url = {https://doi.org/10.1613/jair.1.11388},
doi = {10.1613/jair.1.11388},
abstract = {Many areas of AI today use benchmarks and competitions with larger and wider sets of tasks. This tries to deter AI systems (and research effort) from specialising to a single task, and encourage them to be prepared to solve previously unseen tasks. It is unclear, however, whether the methods with best performance are actually those that are most general and, in perspective, whether the trend moves towards more general AI systems. This question has a striking similarity with the analysis of the so-called positive manifold and general factors in the area of human intelligence. In this paper, we first show how the existence of a manifold (positive average pairwise task correlation) can also be analysed in AI, and how this relates to the notion of agent generality, from the individual and the populational points of view. From the populational perspective, we analyse the following question: is this manifold correlation higher for the most or for the least able group of agents? We contrast this analysis with one of the most controversial issues in human intelligence research, the so-called Spearman's Law of Diminishing Returns (SLODR), which basically states that the relevance of a general factor diminishes for most able human groups. We perform two empirical studies on these issues in AI. We analyse the results of the 2015 general video game AI (GVGAI) competition, with games as tasks and "controllers" as agents, and the results of a synthetic setting, with modified elementary cellular automata (ECA) rules as tasks and simple interactive programs as agents. In both cases, we see that SLODR does not appear. The data, and the use of just two scenarios, does not clearly support the reverse either, a Universal Law of Augmenting Returns (ULOAR), but calls for more experiments on this question.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {529–562},
numpages = {34}
}

@article{10.1613/jair.1.11376,
author = {Nebel, Bernhard and Bolander, Thomas and Engesser, Thorsten and Mattm\"{u}ller, Robert},
title = {Implicitly Coordinated Multi-Agent Path Finding under Destination Uncertainty: Success Guarantees and Computational Complexity},
year = {2019},
issue_date = {January 2019},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {64},
number = {1},
issn = {1076-9757},
url = {https://doi.org/10.1613/jair.1.11376},
doi = {10.1613/jair.1.11376},
abstract = {In multi-agent path finding (MAPF), it is usually assumed that planning is performed centrally and that the destinations of the agents are common knowledge. We will drop both assumptions and analyze under which conditions it can be guaranteed that the agents reach their respective destinations using implicitly coordinated plans without communication. Furthermore, we will analyze what the computational costs associated with such a coordination regime are. As it turns out, guarantees can be given assuming that the agents are of a certain type. However, the implied computational costs are quite severe. In the distributed setting, we either have to solve a sequence of NP-complete problems or have to tolerate exponentially longer executions. In the setting with destination uncertainty, bounded plan existence becomes PSPACE-complete. This clearly demonstrates the value of communicating about plans before execution starts.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {497–527},
numpages = {31}
}

@article{10.1613/jair.1.11375,
author = {Cui, Jing and Haslum, Patrik},
title = {Dynamic Controllability of Controllable Conditional Temporal Problems with Uncertainty},
year = {2019},
issue_date = {January 2019},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {64},
number = {1},
issn = {1076-9757},
url = {https://doi.org/10.1613/jair.1.11375},
doi = {10.1613/jair.1.11375},
abstract = {Dynamic Controllability (DC) of a Simple Temporal Problem with Uncertainty (STPU) uses a dynamic decision strategy, rather than a fixed schedule, to tackle temporal uncertainty. We extend this concept to the Controllable Conditional Temporal Problem with Uncertainty (CCTPU), which extends the STPU by conditioning temporal constraints on the assignment of controllable discrete variables. We define dynamic controllability of a CCTPU as the existence of a strategy that decides on both the values of discrete choice variables and the scheduling of controllable time points dynamically. This contrasts with previous work, which made a static assignment of choice variables and dynamic decisions over time points only. We propose an algorithm to find such a fully dynamic strategy. The algorithm computes the "envelope" of outcomes of temporal uncertainty in which a particular assignment of discrete variables is feasible, and aggregates these over all choices. When an aggregated envelope covers all uncertain situations of the CCTPU, the problem is dynamically controllable. However, the algorithm is complete only under certain assumptions. Experiments on an existing set of CCTPU benchmarks show that there are cases in which making both discrete and temporal decisions dynamically it is feasible to satisfy the problem constraints while assigning the discrete variables statically it is not.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {445–495},
numpages = {51}
}

@article{10.1613/jair.1.11370,
author = {Burch, Neil and Moravcik, Matej and Schmid, Martin},
title = {Revisiting CFR+ and Alternating Updates},
year = {2019},
issue_date = {January 2019},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {64},
number = {1},
issn = {1076-9757},
url = {https://doi.org/10.1613/jair.1.11370},
doi = {10.1613/jair.1.11370},
abstract = {The CFR+ algorithm for solving imperfect information games is a variant of the popular CFR algorithm, with faster empirical performance on a range of problems. It was introduced with a theoretical upper bound on solution error, but subsequent work showed an error in one step of the proof. We provide updated proofs to recover the original bound.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {429–443},
numpages = {15}
}

@article{10.1613/jair.1.11369,
author = {Song, Wen and Kang, Donghun and Zhang, Jie and Cao, Zhiguang and Xi, Hui},
title = {A Sampling Approach for Proactive Project Scheduling under Generalized Time-Dependent Workability Uncertainty},
year = {2019},
issue_date = {January 2019},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {64},
number = {1},
issn = {1076-9757},
url = {https://doi.org/10.1613/jair.1.11369},
doi = {10.1613/jair.1.11369},
abstract = {In real-world project scheduling applications, activity durations are often uncertain. Proactive scheduling can effectively cope with the duration uncertainties, by generating robust baseline solutions according to a priori stochastic knowledge. However, most of the existing proactive approaches assume that the duration uncertainty of an activity is not related to its scheduled start time, which may not hold in many real-world scenarios. In this paper, we relax this assumption by allowing the duration uncertainty to be time-dependent, which is caused by the uncertainty of whether the activity can be executed on each time slot. We propose a stochastic optimization model to find an optimal Partial-order Schedule (POS) that minimizes the expected makespan. This model can cover both the time-dependent uncertainty studied in this paper and the traditional time-independent duration uncertainty. To circumvent the underlying complexity in evaluating a given solution, we approximate the stochastic optimization model based on Sample Average Approximation (SAA). Finally, we design two efficient branch-and-bound algorithms to solve the NP-hard SAA problem. Empirical evaluation confirms that our approach can generate high-quality proactive solutions for a variety of uncertainty distributions.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {385–427},
numpages = {43}
}

@article{10.1613/jair.1.11361,
author = {Wright, James R. and Leyton-Brown, Kevin},
title = {Level-0 Models for Predicting Human Behavior in Games},
year = {2019},
issue_date = {January 2019},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {64},
number = {1},
issn = {1076-9757},
url = {https://doi.org/10.1613/jair.1.11361},
doi = {10.1613/jair.1.11361},
abstract = {Behavioral game theory seeks to describe the way actual people (as compared to idealized, "rational" agents) act in strategic situations. Our own recent work has identified iterative models, such as quantal cognitive hierarchy, as the state of the art for predicting human play in unrepeated, simultaneous-move games. Iterative models predict that agents reason iteratively about their opponents, building up from a specification of nonstrategic behavior called level-0. A modeler is in principle free to choose any description of level-0 behavior that makes sense for a given setting. However, in practice almost all existing work specifies this behavior as a uniform distribution over actions. In most games it is not plausible that even nonstrategic agents would choose an action uniformly at random, nor that other agents would expect them to do so. A more accurate model for level-0 behavior has the potential to dramatically improve predictions of human behavior, since a substantial fraction of agents may play level-0 strategies directly, and furthermore since iterative models ground all higher-level strategies in responses to the level-0 strategy. Our work considers models of the way in which level-0 agents construct a probability distribution over actions, given an arbitrary game. We considered a large space of alternatives and, in the end, recommend a model that achieved excellent performance across the board: a linear weighting of four binary features, each of which is general in the sense that it can be computed from any normal form game. Adding real-valued variants of the same four features yielded further improvements in performance, albeit with a corresponding increase in the number of parameters needing to be estimated. We evaluated the effects of combining these new level-0 models with several iterative models and observed large improvements in predictive accuracy.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {357–383},
numpages = {27}
}

@article{10.1613/jair.1.11358,
author = {Garg, Nikhil and Kamble, Vijay and Goel, Ashish and Marn, David and Munagala, Kamesh},
title = {Iterative Local Voting for Collective Decision-Making in Continuous Spaces},
year = {2019},
issue_date = {January 2019},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {64},
number = {1},
issn = {1076-9757},
url = {https://doi.org/10.1613/jair.1.11358},
doi = {10.1613/jair.1.11358},
abstract = {Many societal decision problems lie in high-dimensional continuous spaces not amenable to the voting techniques common for their discrete or single-dimensional counterparts. These problems are typically discretized before running an election or decided upon through negotiation by representatives. We propose a algorithm called Iterative Local Voting for collective decision-making in this setting. In this algorithm, voters are sequentially sampled and asked to modify a candidate solution within some local neighborhood of its current value, as defined by a ball in some chosen norm, with the size of the ball shrinking at a specified rate.We first prove the convergence of this algorithm under appropriate choices of neighborhoods to Pareto optimal solutions with desirable fairness properties in certain natural settings: when the voters' utilities can be expressed in terms of some form of distance from their ideal solution, and when these utilities are additively decomposable across dimensions. In many of these cases, we obtain convergence to the societal welfare maximizing solution.We then describe an experiment in which we test our algorithm for the decision of the U.S. Federal Budget on Mechanical Turk with over 2,000 workers, employing neighborhoods defined by various L-Norm balls. We make several observations that inform future implementations of such a procedure.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {315–355},
numpages = {41}
}

@article{10.1613/jair.1.11355,
author = {Grau, Bernardo Cuenca and Kostylev, Egor V.},
title = {Logical Foundations of Linked Data Anonymisation},
year = {2019},
issue_date = {January 2019},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {64},
number = {1},
issn = {1076-9757},
url = {https://doi.org/10.1613/jair.1.11355},
doi = {10.1613/jair.1.11355},
abstract = {The widespread adoption of the Linked Data paradigm has been driven by the increasing demand for information exchange between organisations, as well as by regulations in domains such as health care and governance that require certain data to be published. In this setting, sensitive information is at high risk of disclosure since published data can be often seamlessly linked with arbitrary external data sources.In this paper we lay the logical foundations of anonymisation in the context of Linked Data. We consider anonymisations of RDF graphs (and, more generally, relational datasets with labelled nulls) and define notions of policy-compliant and linkage-safe anonymisations. Policy compliance ensures that an anonymised dataset does not reveal any sensitive information as specified by a policy query. Linkage safety ensures that an anonymised dataset remains compliant even if it is linked to (possibly unknown) external datasets available on the Web, thus providing provable protection guarantees against data linkage attacks. We establish the computational complexity of the underpinning decision problems both under the open-world semantics inherent to RDF and under the assumption that an attacker has complete, closed-world knowledge over some parts of the original data.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {253–314},
numpages = {62}
}

@article{10.1613/jair.1.11345,
author = {Zanzotto, Fabio Massimo},
title = {Viewpoint: Human-in-the-Loop Artificial Intelligence},
year = {2019},
issue_date = {January 2019},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {64},
number = {1},
issn = {1076-9757},
url = {https://doi.org/10.1613/jair.1.11345},
doi = {10.1613/jair.1.11345},
abstract = {Little by little, newspapers are revealing the bright future that Artificial Intelligence (AI) is building. Intelligent machines will help everywhere. However, this bright future may have a possible dark side: a dramatic job market contraction before its unpredictable transformation. Hence, in a near future, large numbers of job seekers may need financial support while catching up with these novel unpredictable jobs. This possible job market crisis has an antidote inside. In fact, the rise of AI is sustained by the biggest knowledge theft of the recent years. Many learning AI machines are extracting knowledge from unaware skilled or unskilled workers by analyzing their interactions. By passionately doing their jobs, many of these workers are shooting themselves in the feet.In this paper, we propose Human-in-the-loop Artificial Intelligence (HitAI) as a fairer paradigm for AI systems. Recognizing that any AI system has humans in the loop, HitAI will reward these aware and unaware knowledge producers with a different scheme: decisions of AI systems generating revenues will repay the legitimate owners of the knowledge used for taking those decisions. As modern Merry Men, HitAI researchers should fight for a fairer Robin Hood Artificial Intelligence that gives back what it steals.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {243–252},
numpages = {10}
}

@article{10.1613/jair.1.11343,
author = {Masters, Peta and Sardina, Sebastian},
title = {Cost-Based Goal Recognition in Navigational Domains},
year = {2019},
issue_date = {January 2019},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {64},
number = {1},
issn = {1076-9757},
url = {https://doi.org/10.1613/jair.1.11343},
doi = {10.1613/jair.1.11343},
abstract = {Goal recognition is the problem of determining an agent's intent by observing her behaviour. Contemporary solutions for general task-planning relate the probability of a goal to the cost of reaching it. We adapt this approach to goal recognition in the strict context of path-planning. We show (1) that a simpler formula provides an identical result to current state-of-the-art in less than half the time under all but one set of conditions. Further, we prove (2) that the probability distribution based on this technique is independent of an agent's past behaviour and present a revised formula that achieves goal recognition by reference to the agent's starting point and current location only. Building on this, we demonstrate (3) that a Radius of Maximum Probability (i.e., the distance from a goal within which that goal is guaranteed to be the most probable) can be calculated from relative cost-distances between the candidate goals and a start location, without needing to calculate any actual probabilities. In this extended version of earlier work, we generalise our framework to the continuous domain and discuss our results, including the conditions under which our findings can be generalised back to goal recognition in general task-planning.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {197–242},
numpages = {46}
}

@article{10.1613/jair.1.11338,
author = {Tian, Yan and Wang, Xun and Wu, Jiachen and Wang, Ruili and Yang, Bailin},
title = {Multi-Scale Hierarchical Residual Network for Dense Captioning},
year = {2019},
issue_date = {January 2019},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {64},
number = {1},
issn = {1076-9757},
url = {https://doi.org/10.1613/jair.1.11338},
doi = {10.1613/jair.1.11338},
abstract = {Recent research on dense captioning based on the recurrent neural network and the convolutional neural network has made a great progress. However, mapping from an image feature space to a description space is a nonlinear and multimodel task, which makes it difficult for the current methods to get accurate results. In this paper, we put forward a novel approach for dense captioning based on hourglass-structured residual learning. Discriminant feature maps are obtained by incorporating dense connected networks and residual learning in our model. Finally, the performance of the approach on the Visual Genome V1.0 dataset and the region labelled MS-COCO (Microsoft Common Objects in Context) dataset are demonstrated. The experimental results have shown that our approach outperforms most current methods.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {181–196},
numpages = {16}
}

@article{10.1613/jair.1.11337,
author = {Zhuang, Zhiqiang and Wang, Zhe and Wang, Kewen and Delgrande, James},
title = {A Generalisation of AGM Contraction and Revision to Fragments of First-Order Logic},
year = {2019},
issue_date = {January 2019},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {64},
number = {1},
issn = {1076-9757},
url = {https://doi.org/10.1613/jair.1.11337},
doi = {10.1613/jair.1.11337},
abstract = {AGM contraction and revision assume an underlying logic that contains propositional logic. Consequently, this assumption excludes many useful logics such as the Horn fragment of propositional logic and most description logics. Our goal in this paper is to generalise AGM contraction and revision to (near-)arbitrary fragments of classical first-order logic. To this end, we first define a very general logic that captures these fragments. In so doing, we make the modest assumptions that a logic contains conjunction and that information is expressed by closed formulas or sentences. The resulting logic is called first-order conjunctive logic or FC logic for short. We then take as the point of departure the AGM approach of constructing contraction functions through epistemic entrenchment, that is the entrenchment-based contraction. We redefine entrenchment-based contraction in ways that apply to any FC logic, which we call FC contraction. We prove a representation theorem showing its compliance with all the AGM contraction postulates except for the controversial recovery postulate. We also give methods for constructing revision functions through epistemic entrenchment which we call FC revision; which also apply to any FC logic. We show that if the underlying FC logic contains tautologies then FC revision complies with all the AGM revision postulates. Finally, in the context of FC logic, we provide three methods for generating revision functions via a variant of the Levi Identity, which we call contraction, withdrawal and cut generated revision, and explore the notion of revision equivalence. We show that withdrawal and cut generated revision coincide with FC revision and so does contraction generated revision under a finiteness condition.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {147–179},
numpages = {33}
}

@article{10.1613/jair.1.11335,
author = {Keller, Orgad and Hassidim, Avinatan and Hazon, Noam},
title = {New Approximations for Coalitional Manipulation in Scoring Rules},
year = {2019},
issue_date = {January 2019},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {64},
number = {1},
issn = {1076-9757},
url = {https://doi.org/10.1613/jair.1.11335},
doi = {10.1613/jair.1.11335},
abstract = {We study the problem of coalitional manipulation--where k manipulators try to manipulate an election on m candidates--for any scoring rule, with focus on the Borda protocol. We do so in both the weighted and unweighted settings. For these problems, recent approximation approaches have tried to minimize k, the number of manipulators needed to make some preferred candidate p win (thus assuming that the number of manipulators is not limited in advance). In contrast, we focus on minimizing the score margin of p which is the difference between the maximum score of a candidate and the score of p.We provide algorithms that approximate the optimum score margin, which are applicable to any scoring rule. For the specific case of the Borda protocol in the unweighted setting, our algorithm provides a superior approximation factor for lower values of k.Our methods are novel and adapt techniques from multiprocessor scheduling by carefully rounding an exponentially-large configuration linear program that is solved by using the ellipsoid method with an Efficient separation oracle. We believe that such methods could be benEfficial in other social choice settings as well.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {109–145},
numpages = {37}
}

@article{10.1613/jair.1.11323,
author = {Laing, Kathryn and Thwaites, Peter Adam and Gosling, John Paul},
title = {Rank Pruning for Dominance Queries in CP-Nets},
year = {2019},
issue_date = {January 2019},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {64},
number = {1},
issn = {1076-9757},
url = {https://doi.org/10.1613/jair.1.11323},
doi = {10.1613/jair.1.11323},
abstract = {Conditional preference networks (CP-nets) are a graphical representation of a person's (conditional) preferences over a set of discrete features. In this paper, we introduce a novel method of quantifying preference for any given outcome based on a CP-net representation of a user's preferences. We demonstrate that these values are useful for reasoning about user preferences. In particular, they allow us to order (any subset of) the possible outcomes in accordance with the user's preferences. Further, these values can be used to improve the efficiency of outcome dominance testing. That is, given a pair of outcomes, we can determine which the user prefers more efficiently. Through experimental results, we show that this method is more effective than existing techniques for improving dominance testing efficiency. We show that the above results also hold for CP-nets that express indifference between variable values.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {55–107},
numpages = {53}
}

@article{10.1613/jair.1.11305,
author = {Trouillon, Th\'{e}o and Gaussier, \'{E}ric and Dance, Christopher R. and Bouchard, Guillaume},
title = {On Inductive Abilities of Latent Factor Models for Relational Learning},
year = {2019},
issue_date = {January 2019},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {64},
number = {1},
issn = {1076-9757},
url = {https://doi.org/10.1613/jair.1.11305},
doi = {10.1613/jair.1.11305},
abstract = {Latent factor models are increasingly popular for modeling multi-relational knowledge graphs. By their vectorial nature, it is not only hard to interpret why this class of models works so well, but also to understand where they fail and how they might be improved. We conduct an experimental survey of state-of-the-art models, not towards a purely comparative end, but as a means to get insight about their inductive abilities. To assess the strengths and weaknesses of each model, we create simple tasks that exhibit first, atomic properties of binary relations, and then, common inter-relational inference through synthetic genealogies. Based on these experimental results, we propose new research directions to improve on existing models.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {21–53},
numpages = {33}
}

@article{10.1613/jair.1.11291,
author = {Farhadi, Alireza and Ghodsi, Mohammad and Hajiaghayi, MohammadTaghi and Lahaie, S\'{e}bastien and Pennock, David and Seddighin, Masoud and Seddighin, Saeed and Yami, Hadi},
title = {Fair Allocation of Indivisible Goods to Asymmetric Agents},
year = {2019},
issue_date = {January 2019},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {64},
number = {1},
issn = {1076-9757},
url = {https://doi.org/10.1613/jair.1.11291},
doi = {10.1613/jair.1.11291},
abstract = {We study fair allocation of indivisible goods to agents with unequal entitlements. Fair allocation has been the subject of many studies in both divisible and indivisible settings. Our emphasis is on the case where the goods are indivisible and agents have unequal entitlements. This problem is a generalization of the work by Procaccia and Wang (Procaccia & Wang, 2014) wherein the agents are assumed to be symmetric with respect to their entitlements. Although Procaccia and Wang show an almost fair (constant approximation) allocation exists in their setting, our main result is in sharp contrast to their observation. We show that, in some cases with n agents, no allocation can guarantee better than 1/n approximation of a fair allocation when the entitlements are not necessarily equal. Furthermore, we devise a simple algorithm that ensures a 1/n approximation guarantee.Our second result is for a restricted version of the problem where the valuation of every agent for each good is bounded by the total value he wishes to receive in a fair allocation. Although this assumption might seem without loss of generality, we show it enables us to find a 1/2 approximation fair allocation via a greedy algorithm. Finally, we run some experiments on real-world data and show that, in practice, a fair allocation is likely to exist. We also support our experiments by showing positive results for two stochastic variants of the problem, namely stochastic agents and stochastic items.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {1–20},
numpages = {20}
}

@article{10.1613/jair.1.11270,
author = {Bachrach, Yoram and Elkind, Edith and Malizia, Enrico and Meir, Reshef and Pasechnik, Dmitrii and Rosenschein, Jeffrey S. and Rothe, J\"{o}rg and Zuckerman, Michael},
title = {Bounds on the Cost of Stabilizing a Cooperative Game},
year = {2018},
issue_date = {September 2018},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {63},
number = {1},
issn = {1076-9757},
url = {https://doi.org/10.1613/jair.1.11270},
doi = {10.1613/jair.1.11270},
abstract = {A key issue in cooperative game theory is coalitional stability, usually captured by the notion of the core--the set of outcomes that are resistant to group deviations. However, some coalitional games have empty cores, and any outcome in such a game is unstable. We investigate the possibility of stabilizing a coalitional game by using subsidies. We consider scenarios where an external party that is interested in having the players work together offers a supplemental payment to the grand coalition, or, more generally, a particular coalition structure. This payment is conditional on players not deviating from this coalition structure, and may be divided among the players in any way they wish. We define the cost of stability as the minimum external payment that stabilizes the game. We provide tight bounds on the cost of stability, both for games where the coalitional values are nonnegative (profit-sharing games) and for games where the coalitional values are nonpositive (cost-sharing games), under natural assumptions on the characteristic function, such as superadditivity, anonymity, or both. We also investigate the relationship between the cost of stability and several variants of the least core. Finally, we study the computational complexity of problems related to the cost of stability, with a focus on weighted voting games.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {987–1023},
numpages = {37}
}

@article{10.1613/jair.1.11268,
author = {Goldwaser, Adrian and Schutt, Andreas},
title = {Optimal Torpedo Scheduling},
year = {2018},
issue_date = {September 2018},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {63},
number = {1},
issn = {1076-9757},
url = {https://doi.org/10.1613/jair.1.11268},
doi = {10.1613/jair.1.11268},
abstract = {We consider the torpedo scheduling problem in steel production, which is concerned with the transport of hot metal from a blast furnace to an oxygen converter. A schedule must satisfy, amongst other considerations, resource capacity constraints along the path and the locations traversed as well as the sulfur level of the hot metal. The goal is first to minimize the number of torpedo cars used during the planning horizon and second to minimize the time spent desulfurizing the hot metal. We propose an exact solution method based on Logic-based Benders Decomposition using Mixed-Integer and Constraint Programming, which optimally solves and proves, for the first time, the optimality of all instances from the ACP Challenge 2016 within 10 minutes. In addition, we adapted our method to handle large-scale instances and instances with a more general rail network. This adaptation optimally solved all challenge instances within one minute and was able to solve instances of up to 100,000 hot metal pickups.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {955–986},
numpages = {32}
}

@article{10.1613/jair.1.11266,
author = {Zhang, Meishan and Zhang, Yue and Fu, Guohong},
title = {Transition-Based Neural Word Segmentation Using Word-Level Features},
year = {2018},
issue_date = {September 2018},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {63},
number = {1},
issn = {1076-9757},
url = {https://doi.org/10.1613/jair.1.11266},
doi = {10.1613/jair.1.11266},
abstract = {Character-based and word-based methods are two different solutions for Chinese word segmentation, the former exploiting sequence labeling models over characters and the latter using word-level features. Neural models have been exploited for character-based Chinese word segmentation, giving high accuracies by making use of external character embeddings, yet requiring less feature engineering. In this paper, we study a neural model for word-based Chinese word segmentation, by replacing the manually-designed discrete features with neural features in a transition-based word segmentation framework. Experimental results demonstrate that word features lead to comparable performance to the best systems in the literature, and a further combination of discrete and neural features obtains top accuracies on several benchmarks.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {923–953},
numpages = {31}
}

@article{10.1613/jair.1.11265,
author = {Marinescu, Radu and Lee, Junkyu and Dechter, Rina and Ihler, Alexander},
title = {AND/OR Search for Marginal MAP},
year = {2018},
issue_date = {September 2018},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {63},
number = {1},
issn = {1076-9757},
url = {https://doi.org/10.1613/jair.1.11265},
doi = {10.1613/jair.1.11265},
abstract = {Mixed inference such as the marginal MAP query (some variables marginalized by summation and others by maximization) is key to many prediction and decision models. It is known to be extremely hard; the problem is NPPP-complete while the decision problem for MAP is only NP-complete and the summation problem is #P-complete. Consequently, approximation anytime schemes are essential. In this paper, we show that the framework of heuristic AND/OR search, which exploits conditional independence in the graphical model, coupled with variational-based mini-bucket heuristics can be extended to this task and yield powerful state-of-the-art schemes. Specifically, we explore the complementary properties of best-first search for reducing the number of conditional sums and providing time-improving upper bounds, with depth-first search for rapidly generating and improving solutions and lower bounds. We show empirically that a class of solvers that interleaves depth-first with best-first schemes emerges as the most competitive anytime scheme.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {875–921},
numpages = {47}
}

@article{10.1613/jair.1.11263,
author = {Narasimhan, Karthik and Barzilay, Regina and Jaakkola, Tommi},
title = {Grounding Language for Transfer in Deep Reinforcement Learning},
year = {2018},
issue_date = {September 2018},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {63},
number = {1},
issn = {1076-9757},
url = {https://doi.org/10.1613/jair.1.11263},
doi = {10.1613/jair.1.11263},
abstract = {In this paper, we explore the utilization of natural language to drive transfer for reinforcement learning (RL). Despite the wide-spread application of deep RL techniques, learning generalized policy representations that work across domains remains a challenging problem. We demonstrate that textual descriptions of environments provide a compact intermediate channel to facilitate effective policy transfer. Specifically, by learning to ground the meaning of text to the dynamics of the environment such as transitions and rewards, an autonomous agent can effectively bootstrap policy learning on a new domain given its description. We employ a model-based RL approach consisting of a differentiable planning module, a model-free component and a factorized state representation to effectively use entity descriptions. Our model outperforms prior work on both transfer and multi-task scenarios in a variety of different environments. For instance, we achieve up to 14% and 11.5% absolute improvement over previously existing models in terms of average and initial rewards, respectively.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {849–874},
numpages = {26}
}

@article{10.1613/jair.1.11261,
author = {L\"{u}dtke, Stefan and Schr\"{o}der, Max and Kr\"{u}ger, Frank and Bader, Sebastian and Kirste, Thomas},
title = {State-Space Abstractions for Probabilistic Inference: A Systematic Review},
year = {2018},
issue_date = {September 2018},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {63},
number = {1},
issn = {1076-9757},
url = {https://doi.org/10.1613/jair.1.11261},
doi = {10.1613/jair.1.11261},
abstract = {Tasks such as social network analysis, human behavior recognition, or modeling biochemical reactions, can be solved elegantly by using the probabilistic inference framework. However, standard probabilistic inference algorithms work at a propositional level, and thus cannot capture the symmetries and redundancies that are present in these tasks.Algorithms that exploit those symmetries have been devised in different research fields, for example by the lifted inference-, multiple object tracking-, and modeling and simulation-communities. The common idea, that we call state space abstraction, is to perform inference over compact representations of sets of symmetric states. Although they are concerned with a similar topic, the relationship between these approaches has not been investigated systematically.This survey provides the following contributions. We perform a systematic literature review to outline the state of the art in probabilistic inference methods exploiting symmetries. From an initial set of more than 4,000 papers, we identify 116 relevant papers. Furthermore, we provide new high-level categories that classify the approaches, based on common properties of the approaches. The research areas underlying each of the categories are introduced concisely. Researchers from different fields that are confronted with a state space explosion problem in a probabilistic system can use this classification to identify possible solutions. Finally, based on this conceptualization, we identify potentials for future research, as some relevant application domains are not addressed by current approaches.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {789–848},
numpages = {60}
}

@article{10.1613/jair.1.11259,
author = {Camacho-Collados, Jose and Pilehvar, Mohammad Taher},
title = {From Word to Sense Embeddings: A Survey on Vector Representations of Meaning},
year = {2018},
issue_date = {September 2018},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {63},
number = {1},
issn = {1076-9757},
url = {https://doi.org/10.1613/jair.1.11259},
doi = {10.1613/jair.1.11259},
abstract = {Over the past years, distributed semantic representations have proved to be effective and flexible keepers of prior knowledge to be integrated into downstream applications. This survey focuses on the representation of meaning. We start from the theoretical background behind word vector space models and highlight one of their major limitations: the meaning conflation deficiency, which arises from representing a word with all its possible meanings as a single vector. Then, we explain how this deficiency can be addressed through a transition from the word level to the more fine-grained level of word senses (in its broader acceptation) as a method for modelling unambiguous lexical meaning. We present a comprehensive overview of the wide range of techniques in the two main branches of sense representation, i.e., unsupervised and knowledge-based. Finally, this survey covers the main evaluation procedures and applications for this type of representation, and provides an analysis of four of its important aspects: interpretability, sense granularity, adaptability to different domains and compositionality.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {743–788},
numpages = {46}
}

@article{10.1613/jair.1.11258,
author = {Banaee, Hadi and Schaffernicht, Erik and Loutfi, Amy},
title = {Data-Driven Conceptual Spaces: Creating Semantic Representations for Linguistic Descriptions of Numerical Data},
year = {2018},
issue_date = {September 2018},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {63},
number = {1},
issn = {1076-9757},
url = {https://doi.org/10.1613/jair.1.11258},
doi = {10.1613/jair.1.11258},
abstract = {There is an increasing need to derive semantics from real-world observations to facilitate natural information sharing between machine and human. Conceptual spaces theory is a possible approach and has been proposed as mid-level representation between symbolic and sub-symbolic representations, whereby concepts are represented in a geometrical space that is characterised by a number of quality dimensions. Currently, much of the work has demonstrated how conceptual spaces are created in a knowledge-driven manner, relying on prior knowledge to form concepts and identify quality dimensions. This paper presents a method to create semantic representations using data-driven conceptual spaces which are then used to derive linguistic descriptions of numerical data. Our contribution is a principled approach to automatically construct a conceptual space from a set of known observations wherein the quality dimensions and domains are not known a priori. This novelty of the approach is the ability to select and group semantic features to discriminate between concepts in a data-driven manner while preserving the semantic interpretation that is needed to infer linguistic descriptions for interaction with humans. Two data sets representing leaf images and time series signals are used to evaluate the method. An empirical evaluation for each case study assesses how well linguistic descriptions generated from the conceptual spaces identify unknown observations. Furthermore, comparisons are made with descriptions derived on alternative approaches for generating semantic models.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {691–742},
numpages = {52}
}

@article{10.1613/jair.1.11257,
author = {Bate, Andrew and Motik, Boris and Grau, Bernardo Cuenca and Cucala, David Tena and Siman\v{c}\'{\i}k, Franti\v{s}ek and Horrocks, Ian},
title = {Consequence-Based Reasoning for Description Logics with Disjunctions and Number Restrictions},
year = {2018},
issue_date = {September 2018},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {63},
number = {1},
issn = {1076-9757},
url = {https://doi.org/10.1613/jair.1.11257},
doi = {10.1613/jair.1.11257},
abstract = {Classification of description logic (DL) ontologies is a key computational problem in modern data management applications, so considerable effort has been devoted to the development and optimisation of practical reasoning calculi. Consequence-based calculi combine ideas from hypertableau and resolution in a way that has proved very effective in practice. However, existing consequence-based calculi can handle either Horn DLs (which do not support disjunction) or DLs without number restrictions. In this paper, we overcome this important limitation and present the first consequence-based calculus for deciding concept subsumption in the DL ALCHIQ+. Our calculus runs in exponential time assuming unary coding of numbers, and on ELH ontologies it runs in polynomial time. The extension to disjunctions and number restrictions is technically involved: we capture the relevant consequences using first-order clauses, and our inference rules adapt paramodulation techniques from first-order theorem proving. By using a well-known preprocessing step, the calculus can also decide concept subsumptions in SRIQ--a rich DL that covers all features of OWL 2 DL apart from nominals and datatypes. We have implemented our calculus in a new reasoner called Sequoia. We present the architecture of our reasoner and discuss several novel and important implementation techniques such as clause indexing and redundancy elimination. Finally, we present the results of an extensive performance evaluation, which revealed Sequoia to be competitive with existing reasoners. Thus, the calculus and the techniques we present in this paper provide an important addition to the repertoire of practical implementation techniques for description logic reasoning.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {625–690},
numpages = {66}
}

@article{10.1613/jair.1.11256,
author = {Fionda, Valeria and Greco, Gianluigi},
title = {LTL on Finite and Process Traces: Complexity Results and a Practical Reasoner},
year = {2018},
issue_date = {September 2018},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {63},
number = {1},
issn = {1076-9757},
url = {https://doi.org/10.1613/jair.1.11256},
doi = {10.1613/jair.1.11256},
abstract = {Linear temporal logic (LTL) is a modal logic where formulas are built over temporal operators relating events happening in different time instants. According to the standard semantics, LTL formulas are interpreted on traces spanning over an infinite timeline. However, applications related to the specification and verification of business processes have recently pointed out the need for defining and reasoning about a variant of LTL, which we name LTLp, whose semantics is defined over process traces, that is, over finite traces such that, at each time instant, precisely one propositional variable (standing for the execution of some given activity) evaluates true.The paper investigates the theoretical underpinnings of LTLp and of a related logic formalism, named LTLf, which had already attracted attention in the literature and where formulas have the same syntax as in LTLp and are evaluated over finite traces, but without any constraint on the number of variables simultaneously evaluating true. The two formalisms are comparatively analyzed, by pointing out similarities and differences. In addition, a thorough complexity analysis has been conducted for reasoning problems about LTLp and LTLf, by considering arbitrary formulas as well as classes of formulas defined in terms of restrictions on the temporal operators that are allowed. Finally, based on the theoretical findings of the paper, a practical reasoner specifically tailored for LTLp and LTLf has been developed by leveraging state-of-the-art SAT solvers. The behavior of the reasoner has been experimentally compared with other systems available in the literature.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {557–623},
numpages = {67}
}

@article{10.1613/jair.1.11254,
author = {Fujita, Etsushi and Lesca, Julien and Sonoda, Akihisa and Todo, Taiki and Yokoo, Makoto},
title = {A Complexity Approach for Core-Selecting Exchange under Conditionally Lexicographic Preferences},
year = {2018},
issue_date = {September 2018},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {63},
number = {1},
issn = {1076-9757},
url = {https://doi.org/10.1613/jair.1.11254},
doi = {10.1613/jair.1.11254},
abstract = {Core-selection is a crucial property of rules in the literature of resource allocation. It is also desirable, from the perspective of mechanism design, to address the incentive of agents to cheat by misreporting their preferences. This paper investigates the exchange problem where (i) each agent is initially endowed with (possibly multiple) indivisible goods, (ii) agents' preferences are assumed to be conditionally lexicographic, and (iii) side payments are prohibited. We propose an exchange rule called augmented top-trading-cycles (ATTC), based on the original TTC procedure. We first show that ATTC is core-selecting and runs in polynomial time with respect to the number of goods. We then show that finding a beneficial misreport under ATTC is NP-hard. We finally clarify relationship of misreporting with splitting and hiding, two different types of manipulations, under ATTC.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {515–555},
numpages = {41}
}

@article{10.1613/jair.1.11253,
author = {Cygan, Marek and Kowalik, undefinedukasz and Soca\l{}a, Arkadiusz and Sornat, Krzysztof},
title = {Approximation and Parameterized Complexity of Minimax Approval Voting},
year = {2018},
issue_date = {September 2018},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {63},
number = {1},
issn = {1076-9757},
url = {https://doi.org/10.1613/jair.1.11253},
doi = {10.1613/jair.1.11253},
abstract = {We present three results on the complexity of MINNIMAX APPROVAL VOTING. First, we study MINNIMAX APPROVAL VOTING parameterized by the Hamming distance d from the solution to the votes. We show MINNIMAX APPROVAL VOTING admits no algorithm running in time O*(2o(d log d)), unless the Exponential Time Hypothesis (ETH) fails. This means that the O*(d2d) algorithm of Misra, Nabeel and Singh is essentially optimal. Motivated by this, we then show a parameterized approximation scheme, running in time O*((3/ε)2d), which is essentially tight assuming ETH. Finally, we get a new polynomial-time randomized approximation scheme for MINNIMAX APPROVAL VOTING, which runs in time nO(1/ε2·log(1/ε)) · poly(m), where n is a number of voters and m is a number of alternatives. It almost matches the running time of the fastest known PTAS for Closest String due to Ma and Sun.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {495–513},
numpages = {19}
}

@article{10.1613/jair.1.11251,
author = {Liu, Bo and Gemp, Ian and Ghavamzadeh, Mohammad and Liu, Ji and Mahadevan, Sridhar and Petrik, Marek},
title = {Proximal Gradient Temporal Difference Learning: Stable Reinforcement Learning with Polynomial Sample Complexity},
year = {2018},
issue_date = {September 2018},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {63},
number = {1},
issn = {1076-9757},
url = {https://doi.org/10.1613/jair.1.11251},
doi = {10.1613/jair.1.11251},
abstract = {In this paper, we introduce proximal gradient temporal difference learning, which provides a principled way of designing and analyzing true stochastic gradient temporal difference learning algorithms. We show how gradient TD (GTD) reinforcement learning methods can be formally derived, not by starting from their original objective functions, as previously attempted, but rather from a primal-dual saddle-point objective function. We also conduct a saddle-point error analysis to obtain finite-sample bounds on their performance. Previous analyses of this class of algorithms use stochastic approximation techniques to prove asymptotic convergence, and do not provide any finite-sample analysis. We also propose an accelerated algorithm, called GTD2-MP, that uses proximal "mirror maps" to yield an improved convergence rate. The results of our theoretical analysis imply that the GTD family of algorithms are comparable and may indeed be preferred over existing least squares TD methods for off-policy learning, due to their linear complexity. We provide experimental results showing the improved performance of our accelerated gradient TD methods.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {461–494},
numpages = {34}
}

@article{10.1613/jair.1.11249,
author = {Laskey, Kathryn Blackmond and Sun, Wei and Hanson, Robin and Twardy, Charles and Matsumoto, Shou and Goldfedder, Brandon},
title = {Graphical Model Market Maker for Combinatorial Prediction Markets},
year = {2018},
issue_date = {September 2018},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {63},
number = {1},
issn = {1076-9757},
url = {https://doi.org/10.1613/jair.1.11249},
doi = {10.1613/jair.1.11249},
abstract = {We describe algorithms for use by prediction markets in forming a crowd consensus joint probability distribution over thousands of related events. Equivalently, we describe market mechanisms to efficiently crowdsource both structure and parameters of a Bayesian network. Prediction markets are among the most accurate methods to combine forecasts; forecasters form a consensus probability distribution by trading contingent securities. A combinatorial prediction market forms a consensus joint distribution over many related events by allowing conditional trades or trades on Boolean combinations of events. Explicitly representing the joint distribution is infeasible, but standard inference algorithms for graphical probability models render it tractable for large numbers of base events. We show how to adapt these algorithms to compute expected assets conditional on a prospective trade, and to find the conditional state where a trader has minimum assets, allowing full asset reuse. We compare the performance of three algorithms: the straightforward algorithm from the DAGGRE (Decomposition-Based Aggregation) prediction market for geopolitical events, the simple block-merge model from the SciCast market for science and technology forecasting, and a more sophisticated algorithm we developed for future markets.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {421–460},
numpages = {40}
}

@article{10.1613/jair.1.11248,
author = {Landeiro, Virgile and Culotta, Aron},
title = {Robust Text Classification under Confounding Shift},
year = {2018},
issue_date = {September 2018},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {63},
number = {1},
issn = {1076-9757},
url = {https://doi.org/10.1613/jair.1.11248},
doi = {10.1613/jair.1.11248},
abstract = {As statistical classifiers become integrated into real-world applications, it is important to consider not only their accuracy but also their robustness to changes in the data distribution. Although identifying and controlling for confounding variables Z-correlated with both the input X of a classifier and its output Y-has been assiduously studied in empirical social science, it is often neglected in text classification. This can be understood by the fact that, if we assume that the impact of confounding variables does not change between the time we fit a model and the time we use it, then prediction accuracy should only be slightly affected. We show in this paper that this assumption often does not hold and that when the influence of a confounding variable changes from training time to prediction time (i.e. under confounding shift), the classifier accuracy can degrade rapidly. We use Pearl's back-door adjustment as a predictive framework to develop a model robust to confounding shift under the condition that Z is observed at training time. Our approach does not make any causal conclusions but by experimenting on 6 datasets, we show that our approach is able to outperform baselines 1) in controlled cases where confounding shift is manually injected between fitting time and prediction time 2) in natural experiments where confounding shift appears either abruptly or gradually 3) in cases where there is one or multiple confounders. Finally, we discuss multiple issues we encountered during this research such as the effect of noise in the observation of Z and the importance of only controlling for confounding variables.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {391–419},
numpages = {29}
}

@article{10.1613/jair.1.11244,
author = {Le, Duong and Plaku, Erion},
title = {Cooperative, Dynamics-Based and Abstraction-Guided Multi-Robot Motion Planning},
year = {2018},
issue_date = {September 2018},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {63},
number = {1},
issn = {1076-9757},
url = {https://doi.org/10.1613/jair.1.11244},
doi = {10.1613/jair.1.11244},
abstract = {This paper presents an effective, cooperative, and probabilistically-complete multirobot motion planner that enables each robot to move to a desired location while avoiding collisions with obstacles and other robots. The approach takes into account not only the geometric constraints arising from collision avoidance, but also the differential constraints imposed by the motion dynamics of each robot. This makes it possible to generate collision-free and dynamically-feasible trajectories that can be executed in the physical world.The salient aspect of the approach is the coupling of sampling-based motion planning to handle the complexity arising from the obstacles and robot dynamics with multi-agent search to find solutions over a suitable discrete abstraction. The discrete abstraction is obtained by constructing roadmaps to solve a relaxed problem that accounts for the obstacles but not the dynamics. Sampling-based motion planning expands a motion tree in the composite state space of all the robots by adding collision-free and dynamically-feasible trajectories as branches. Efficiency is obtained by using multi-agent search to find non-conflicting routes over the discrete abstraction which serve as heuristics to guide the motion-tree expansion. When little or no progress is made, the routes are penalized and the multi-agent search is invoked again to find alternative routes. This synergistic coupling makes it possible to effectively plan collision-free and dynamically-feasible motions that enable each robot to reach its goal. Experiments using vehicle models with nonlinear dynamics operating in complex environments, where cooperation among robots is required, show significant speedups over related work.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {361–390},
numpages = {30}
}

@article{10.1613/jair.1.11243,
author = {Levine, Steven J. and Williams, Brian C.},
title = {Watching and Acting Together: Concurrent Plan Recognition and Adaptation for Human-Robot Teams},
year = {2018},
issue_date = {September 2018},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {63},
number = {1},
issn = {1076-9757},
url = {https://doi.org/10.1613/jair.1.11243},
doi = {10.1613/jair.1.11243},
abstract = {There is huge demand for robots to work alongside humans in heterogeneous teams. To achieve a high degree of fluidity, robots must be able to (1) recognize their human co-worker's intent, and (2) adapt to this intent accordingly, providing useful aid as a teammate. The literature to date has made great progress in these two areas-recognition and adaptation-but largely as separate research activities. In this work, we present a unified approach to these two problems, in which recognition and adaptation occur concurrently and holistically within the same framework. We introduce Pike, an executive for human-robot teams, that allows the robot to continuously and concurrently reason about what a human is doing as execution proceeds, as well as adapt appropriately. The result is a mixed-initiative execution where humans and robots interact fluidly to complete task goals.Key to our approach is our task model: a contingent, temporally-flexible team-plan with explicit choices for both the human and robot. This allows a single set of algorithms to find implicit constraints between sets of choices for the human and robot (as determined via causal link analysis and temporal reasoning), narrowing the possible decisions a rational human would take (hence achieving intent recognition) as well as the possible actions a robot could consistently take (hence achieving adaptation). Pike makes choices based on the preconditions of actions in the plan, temporal constraints, unanticipated disturbances, and choices made previously (by either agent).Innovations of this work include (1) a framework for concurrent intent recognition and adaptation for contingent, temporally-flexible plans, (2) the generalization of causal links for contingent, temporally-flexible plans along with related extraction algorithms, and (3) extensions to a state-of-the-art dynamic execution system to utilize these causal links for decision making.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {281–359},
numpages = {79}
}

@article{10.1613/jair.1.11242,
author = {Hellerstein, Lisa and Kletenik, Devorah},
title = {Revisiting the Approximation Bound for Stochastic Submodular Cover},
year = {2018},
issue_date = {September 2018},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {63},
number = {1},
issn = {1076-9757},
url = {https://doi.org/10.1613/jair.1.11242},
doi = {10.1613/jair.1.11242},
abstract = {Deshpande et al. presented a k(ln R+1) approximation bound for Stochastic Submodular Cover, where k is the state set size, R is the maximum utility of a single item, and the utility function is integer-valued. This bound is similar to the (ln Q/η + 1) bound given by Golovin and Krause, whose analysis was recently found to have an error. Here Q ≥ R is the goal utility and η is the minimum gap between Q and any attainable utility Q′ < Q. We revisit the proof of the k(ln R+1) bound of Deshpande et al., fill in the details of the proof of a key lemma, and prove two bounds for real-valued utility functions: k(ln R1 +1) and (ln RE+1). Here R1 equals the maximum ratio between the largest increase in utility attainable from a single item, and the smallest non-zero increase attainable from that same item (in the same state). The quantity RE equals the maximum ratio between the largest expected increase in utility from a single item, and the smallest non-zero expected increase in utility from that same item. Our bounds apply only to the stochastic setting with independent states.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {265–279},
numpages = {15}
}

@article{10.1613/jair.1.11240,
author = {Amarilli, Antone and Benedikt, Michael and Bourhis, Pierre and Boom, Michael Vanden},
title = {Query Answering with Transitive and Linear-Ordered Data},
year = {2018},
issue_date = {September 2018},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {63},
number = {1},
issn = {1076-9757},
url = {https://doi.org/10.1613/jair.1.11240},
doi = {10.1613/jair.1.11240},
abstract = {We consider entailment problems involving powerful constraint languages such as frontier-guarded existential rules in which we impose additional semantic restrictions on a set of distinguished relations. We consider restricting a relation to be transitive, restricting a relation to be the transitive closure of another relation, and restricting a relation to be a linear order. We give some natural variants of guardedness that allow inference to be decidable in each case, and isolate the complexity of the corresponding decision problems. Finally we show that slight changes in these conditions lead to undecidability.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {191–264},
numpages = {74}
}

@article{10.1613/jair.1.11239,
author = {Tarkowski, Mateusz K. and Szczepa\'{n}ski, Piotr L. and Michalak, Tomasz P. and Harrenstein, Paul and Wooldridge, Michael},
title = {Efficient Computation of Semivalues for Game-Theoretic Network Centrality},
year = {2018},
issue_date = {September 2018},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {63},
number = {1},
issn = {1076-9757},
url = {https://doi.org/10.1613/jair.1.11239},
doi = {10.1613/jair.1.11239},
abstract = {Some game-theoretic solution concepts such as the Shapley value and the Banzhaf index have recently gained popularity as measures of node centrality in networks. While this direction of research is promising, the computational problems that surround it are challenging and have largely been left open. To date there are only a few positive results in the literature, which show that some game-theoretic extensions of degree-, closeness- and betweenness-centrality measures are computable in polynomial time, i.e., without the need to enumerate the exponential number of all possible coalitions. In this article, we show that these results can be extended to a much larger class of centrality measures that are based on a family of solution concepts known as semivalues. The family of semivalues includes, among others, the Shapley value and the Banzhaf index. To this end, we present a generic framework for defining game-theoretic network centralities and prove that all centrality measures that can be expressed in this framework are computable in polynomial time. Using our framework, we present a number of new and polynomial-time computable game-theoretic centrality measures.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {145–189},
numpages = {45}
}

@article{10.1613/jair.1.11238,
author = {Liberatore, Paolo},
title = {Belief Integration and Source Reliability Assessment},
year = {2018},
issue_date = {September 2018},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {63},
number = {1},
issn = {1076-9757},
url = {https://doi.org/10.1613/jair.1.11238},
doi = {10.1613/jair.1.11238},
abstract = {Merging beliefs requires the plausibility of the sources of the information to be merged. They are typically assumed equally reliable when nothing suggests otherwise. A recent line of research has spun from the idea of deriving this information from the revision process itself. In particular, the history of previous revisions and previous merging examples provide information for performing subsequent merging operations.Yet, no examples or previous revisions may be available. In spite of the apparent lack of information, something can still be inferred by a try-and-check approach: a relative reliability ordering is assumed, the sources are integrated according to it and the result is compared with the original information. The final check may contradict the original ordering, like when the result of merging implies the negation of a formula coming from a source initially assumed reliable, or it implies a formula coming from a source assumed unreliable. In such cases, the reliability ordering assumed in the first place can be excluded from consideration.Such a scenario is proved real under the classifications of source reliability and definitions of belief integration considered in this article: sources divided in two, three or multiple reliability classes; integration is mostly by maximal consistent subsets but also weighted distance is considered. Other results mainly concern the integration by maximal consistent subsets and partitions of two and three reliability classes.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {87–143},
numpages = {57}
}

@article{10.1613/jair.1.11236,
author = {Saldanha, Emmanuelle-Anna Dietz and H\"{o}lldobler, Steffen and Ramli, Carroline Dewi Puspa Kencana and Medinacelli, Luis Palacios},
title = {A Core Method for the Weak Completion Semantics with Skeptical Abduction},
year = {2018},
issue_date = {September 2018},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {63},
number = {1},
issn = {1076-9757},
url = {https://doi.org/10.1613/jair.1.11236},
doi = {10.1613/jair.1.11236},
abstract = {The Weak Completion Semantics is a novel cognitive theory which has been successfully applied to the suppression task, the selection task, syllogistic reasoning, the belief bias effect, spatial reasoning as well as reasoning with conditionals. It is based on logic programming with skeptical abduction. Each program admits a least model under the three-valued undefinedukasiewicz logic, which can be computed as the least fixed point of an appropriate semantic operator. The semantic operator can be represented by a three-layer feed-forward network using the CORE method. Its least fixed point is the unique stable state of a recursive network which is obtained from the three-layer feed-forward core by mapping the activation of the output layer back to the input layer. The recursive network is embedded into a novel network to compute skeptical abduction. This paper presents a fully connectionist realization of the Weak Completion Semantics.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {51–86},
numpages = {36}
}

@article{10.1613/jair.1.11233,
author = {Gombolay, Matthew and Jensen, Reed and Stigile, Jessica and Golen, Toni and Shah, Neel and Son, Sung-Hyun and Shah, Julie},
title = {Human-Machine Collaborative Optimization via Apprenticeship Scheduling},
year = {2018},
issue_date = {September 2018},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {63},
number = {1},
issn = {1076-9757},
url = {https://doi.org/10.1613/jair.1.11233},
doi = {10.1613/jair.1.11233},
abstract = {Coordinating agents to complete a set of tasks with intercoupled temporal and resource constraints is computationally challenging, yet human domain experts can solve these difficult scheduling problems using paradigms learned through years of apprenticeship. A process for manually codifying this domain knowledge within a computational framework is necessary to scale beyond the "single-expert, single-trainee" apprenticeship model. However, human domain experts often have difficulty describing their decision-making processes. We propose a new approach for capturing this decision-making process through counterfactual reasoning in pairwise comparisons. Our approach is model-free and does not require iterating through the state space. We demonstrate that this approach accurately learns multifaceted heuristics on a synthetic and real world data sets. We also demonstrate that policies learned from human scheduling demonstration via apprenticeship learning can substantially improve the efficiency of schedule optimization. We employ this human-machine collaborative optimization technique on a variant of the weapon-to-target assignment problem. We demonstrate that this technique generates optimal solutions up to 9.5 times faster than a state-of-the-art optimization algorithm.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {1–49},
numpages = {49}
}

@article{10.1613/jair.1.11229,
author = {Brandt, Sebastian and Kalayci, Elem G\"{u}zel and Ryzhikov, Vladislav and Xiao, Guohui and Zakharyaschev, Michael},
title = {Querying Log Data with Metric Temporal Logic},
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.11229},
doi = {10.1613/jair.1.11229},
abstract = {We propose a novel framework for ontology-based access to temporal log data using a datalog extension datalogMTL of the Horn fragment of the metric temporal logic MTL. We show that datalogMTL is EXPSPACE-complete even with punctual intervals, in which case full MTL is known to be undecidable. We also prove that nonrecursive datalogMTL is PSPACE-complete for combined complexity and in AC0 for data complexity. We demonstrate by two real-world use cases that nonrecursive datalogMTL programs can express complex temporal concepts from typical user queries and thereby facilitate access to temporal log data. Our experiments with Siemens turbine data and MesoWest weather data show that datalogMTL ontology-mediated queries are efficient and scale on large datasets.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {829–877},
numpages = {49}
}

@article{10.1613/jair.1.11228,
author = {Salmer\'{o}n, Antonio and Rum\'{\i}, Rafael and Langseth, Helge and Nielsen, Thomas D. and Madsen, Anders L.},
title = {A Review of Inference Algorithms for Hybrid Bayesian Networks},
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.11228},
doi = {10.1613/jair.1.11228},
abstract = {Hybrid Bayesian networks have received an increasing attention during the last years. The difference with respect to standard Bayesian networks is that they can host discrete and continuous variables simultaneously, which extends the applicability of the Bayesian network framework in general. However, this extra feature also comes at a cost: inference in these types of models is computationally more challenging and the underlying models and updating procedures may not even support closed-form solutions. In this paper we provide an overview of the main trends and principled approaches for performing inference in hybrid Bayesian networks. The methods covered in the paper are organized and discussed according to their methodological basis. We consider how the methods have been extended and adapted to also include (hybrid) dynamic Bayesian networks, and we end with an overview of established software systems supporting inference in these types of models.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {799–828},
numpages = {30}
}

@article{10.1613/jair.1.11227,
author = {Segovia-Aguas, Javier and Jim\'{e}nez, Sergio and Jonsson, Anders},
title = {Computing Hierarchical Finite State Controllers with Classical Planning},
year = {20

license_type: permissive

branch_name: refs/heads/main

extension: bib