text:
of canonical formulas, we reformulate the situation calculus and the event calculus in the general theory of stable models. We also present a translation that turns the reformulations further into answer set programs, so that efficient answer set solvers can be applied to compute the situation calculus and the event calculus.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {571–620},
numpages = {50}
}

@article{10.5555/2387915.2387929,
author = {Hern\'{a}ndez, Carlos and Baier, Jorge A.},
title = {Avoiding and Escaping Depressions in Real-Time Heuristic Search},
year = {2012},
issue_date = {January 2012},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {43},
number = {1},
issn = {1076-9757},
abstract = {Heuristics used for solving hard real-time search problems have regions with depressions. Such regions are bounded areas of the search space in which the heuristic function is inaccurate compared to the actual cost to reach a solution. Early real-time search algorithms, like LRTA*, easily become trapped in those regions since the heuristic values of their states may need to be updated multiple times, which results in costly solutions. State-of-the-art real-time search algorithms, like LSS-LRTA* or LRTA*(k), improve LRTA*'s mechanism to update the heuristic, resulting in improved performance. Those algorithms, however, do not guide search towards avoiding depressed regions. This paper presents depression avoidance, a simple real-time search principle to guide search towards avoiding states that have been marked as part of a heuristic depression. We propose two ways in which depression avoidance can be implemented: mark-and-avoid and move-to-border. We implement these strategies on top of LSS-LRTA* and RTAA*, producing 4 new real-time heuristic search algorithms: aLSS-LRTA*, daLSS-LRTA*, aRTAA*, and daRTAA*. When the objective is to find a single solution by running the real-time search algorithm once, we show that daLSS-LRTA* and daRTAA* outperform their predecessors sometimes by one order of magnitude. Of the four new algorithms, daRTAA* produces the best solutions given a fixed deadline on the average time allowed per planning episode. We prove all our algorithms have good theoretical properties: in finite search spaces, they find a solution if one exists, and converge to an optimal after a number of trials.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {523–570},
numpages = {48}
}

@article{10.5555/2387915.2387928,
author = {Baum, Ji\v{r}\'{\i} and Nicholson, Ann E. and Dix, Trevor I.},
title = {Proximity-Based Non-Uniform Abstractions for Approximate Planning},
year = {2012},
issue_date = {January 2012},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {43},
number = {1},
issn = {1076-9757},
abstract = {In a deterministic world, a planning agent can be certain of the consequences of its planned sequence of actions. Not so, however, in dynamic, stochastic domains where Markov decision processes are commonly used. Unfortunately these suffer from the 'curse of dimensionality': if the state space is a Cartesian product of many small sets ('dimensions'), planning is exponential in the number of those dimensions.Our new technique exploits the intuitive strategy of selectively ignoring various dimensions in different parts of the state space. The resulting non-uniformity has strong implications, since the approximation is no longer Markovian, requiring the use of a modified planner. We also use a spatial and temporal proximity measure, which responds to continued planning as well as movement of the agent through the state space, to dynamically adapt the abstraction as planning progresses.We present qualitative and quantitative results across a range of experimental domains showing that an agent exploiting this novel approximation method successfully finds solutions to the planning problem using much less than the full state space. We assess and analyse the features of domains which our method can exploit.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {477–522},
numpages = {46}
}

@article{10.5555/2387915.2387927,
author = {Grau, Bernardo Cuenca and Motik, Boris and Stoilos, Giorgos and Horrocks, Ian},
title = {Completeness Guarantees for Incomplete Ontology Reasoners: Theory and Practice},
year = {2012},
issue_date = {January 2012},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {43},
number = {1},
issn = {1076-9757},
abstract = {To achieve scalability of query answering, the developers of Semantic Web applications are often forced to use incomplete OWL 2 reasoners, which fail to derive all answers for at least one query, ontology, and data set. The lack of completeness guarantees, however, may be unacceptable for applications in areas such as health care and defence, where missing answers can adversely affect the application's functionality. Furthermore, even if an application can tolerate some level of incompleteness, it is often advantageous to estimate how many and what kind of answers are being lost.In this paper, we present a novel logic-based framework that allows one to check whether a reasoner is complete for a given query Q and ontology T -- that is, whether the reasoner is guaranteed to compute all answers to Q w.r.t. T and an arbitrary data set A. Since ontologies and typical queries are often fixed at application design time, our approach allows application developers to check whether a reasoner known to be incomplete in general is actually complete for the kinds of input relevant for the application.We also present a technique that, given a query Q, an ontology T, and reasoners R1 and R2 that satisfy certain assumptions, can be used to determine whether, for each data set A, reasoner R1 computes more answers to Q w.r.t. T and A than reasoner R2. This allows application developers to select the reasoner that provides the highest degree of completeness for Q and T that is compatible with the application's scalability requirements.Our results thus provide a theoretical and practical foundation for the design of future ontology-based information systems that maximise scalability while minimising or even eliminating incompleteness of query answers.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {419–476},
numpages = {58}
}

@article{10.5555/2387915.2387926,
author = {S\'{a}nchez-Mart\'{\i}nez, Felipe and Carrasco, Rafael C. and Mart\'{\i}nez-Prieto, Miguel A. and Adiego, Joaqu\'{\i}n},
title = {Generalized Biwords for Bitext Compression and Translation Spotting},
year = {2012},
issue_date = {January 2012},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {43},
number = {1},
issn = {1076-9757},
abstract = {Large bilingual parallel texts (also known as bitexts) are usually stored in a compressed form, and previous work has shown that they can be more efficiently compressed if the fact that the two texts are mutual translations is exploited. For example, a bitext can be seen as a sequence of biwords --pairs of parallel words with a high probability of cooccurrence-- that can be used as an intermediate representation in the compression process. However, the simple biword approach described in the literature can only exploit one-to-one word alignments and cannot tackle the reordering of words. We therefore introduce a generalization of biwords which can describe multi-word expressions and reorderings. We also describe some methods for the binary compression of generalized biword sequences, and compare their performance when different schemes are applied to the extraction of the biword sequence. In addition, we show that this generalization of biwords allows for the implementation of an efficient algorithm to look on the compressed bitext for words or text segments in one of the texts and retrieve their counterpart translations in the other text --an application usually referred to as translation spotting-- with only some minor modifications in the compression algorithm.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {389–418},
numpages = {30}
}

@article{10.5555/2387915.2387925,
author = {Planken, L\'{e}on and de Weerdt, Mathijs and van der Krogt, Roman},
title = {Computing All-Pairs Shortest Paths by Leveraging Low Treewidth},
year = {2012},
issue_date = {January 2012},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {43},
number = {1},
issn = {1076-9757},
abstract = {We present two new and efficient algorithms for computing all-pairs shortest paths. The algorithms operate on directed graphs with real (possibly negative) weights. They make use of directed path consistency along a vertex ordering d. Both algorithms run in O(n2wd) time, where wd is the graph width induced by this vertex ordering. For graphs of constant treewidth, this yields O(n2) time, which is optimal. On chordal graphs, the algorithms run in O(nm) time. In addition, we present a variant that exploits graph separators to arrive at a run time of O(nw2d + n2sd) on general graphs, where sd ≤ wd is the size of the largest minimal separator induced by the vertex ordering d. We show empirically that on both constructed and realistic benchmarks, in many cases the algorithms outperform Floyd-Warshall's as well as Johnson's algorithm, which represent the current state of the art with a run time of O(n3) and O(nm + n2 log n), respectively. Our algorithms can be used for spatial and temporal reasoning, such as for the Simple Temporal Problem, which underlines their relevance to the planning and scheduling community.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {353–388},
numpages = {36}
}

@article{10.5555/2387915.2387924,
author = {Jeavons, Peter and Petke, Justyna},
title = {Local Consistency and SAT-Solvers},
year = {2012},
issue_date = {January 2012},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {43},
number = {1},
issn = {1076-9757},
abstract = {Local consistency techniques such as k-consistency are a key component of specialised solvers for constraint satisfaction problems. In this paper we show that the power of using k-consistency techniques on a constraint satisfaction problem is precisely captured by using a particular inference rule, which we call negative-hyper-resolution, on the standard direct encoding of the problem into Boolean clauses. We also show that current clauselearning SAT-solvers will discover in expected polynomial time any inconsistency that can be deduced from a given set of clauses using negative-hyper-resolvents of a fixed size. We combine these two results to show that, without being explicitly designed to do so, current clause-learning SAT-solvers efficiently simulate k-consistency techniques, for all fixed values of k. We then give some experimental results to show that this feature allows clause-learning SAT-solvers to efficiently solve certain families of constraint problems which are challenging for conventional constraint-programming solvers.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {329–351},
numpages = {23}
}

@article{10.5555/2387915.2387923,
author = {Huang, Ruoyun and Chen, Yixin and Zhang, Weixiong},
title = {SAS+ Planning as Satisfiability},
year = {2012},
issue_date = {January 2012},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {43},
number = {1},
issn = {1076-9757},
abstract = {Planning as satisfiability is a principal approach to planning with many eminent advantages. The existing planning as satisfiability techniques usually use encodings compiled from STRIPS. We introduce a novel SAT encoding scheme (SASE) based on the SAS+ formalism. The new scheme exploits the structural information in SAS+, resulting in an encoding that is both more compact and efficient for planning. We prove the correctness of the new encoding by establishing an isomorphism between the solution plans of SASE and that of STRIPS based encodings. We further analyze the transition variables newly introduced in SASE to explain why it accommodates modern SAT solving algorithms and improves performance. We give empirical statistical results to support our analysis. We also develop a number of techniques to further reduce the encoding size of SASE, and conduct experimental studies to show the strength of each individual technique. Finally, we report extensive experimental results to demonstrate significant improvements of SASE over the state-of-the-art STRIPS based encoding schemes in terms of both time and memory efficiency.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {293–328},
numpages = {36}
}

@article{10.5555/2387915.2387922,
author = {Lee, J. H. M. and Leung, K. L.},
title = {Consistency Techniques for Flow-Based Projection-Safe Global Cost Functions in Weighted Constraint Satisfaction},
year = {2012},
issue_date = {January 2012},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {43},
number = {1},
issn = {1076-9757},
abstract = {Many combinatorial problems deal with preferences and violations, the goal of which is to find solutions with the minimum cost. Weighted constraint satisfaction is a framework for modeling such problems, which consists of a set of cost functions to measure the degree of violation or preferences of different combinations of variable assignments. Typical solution methods for weighted constraint satisfaction problems (WCSPs) are based on branch-and-bound search, which are made practical through the use of powerful consistency techniques such as AC*, FDAC*, EDAC* to deduce hidden cost information and value pruning during search. These techniques, however, are designed to be efficient only on binary and ternary cost functions which are represented in table form. In tackling many real-life problems, high arity (or global) cost functions are required. We investigate efficient representation scheme and algorithms to bring the benefits of the consistency techniques to also high arity cost functions, which are often derived from hard global constraints from classical constraint satisfaction.The literature suggests some global cost functions can be represented as flow networks, and the minimum cost flow algorithm can be used to compute the minimum costs of such networks in polynomial time. We show that naive adoption of this flow-based algorithmic method for global cost functions can result in a stronger form of ?-inverse consistency. We further show how the method can be modified to handle cost projections and extensions to maintain generalized versions of AC* and FDAC* for cost functions with more than two variables. Similar generalization for the stronger EDAC* is less straightforward. We reveal the oscillation problem when enforcing EDAC* on cost functions sharing more than one variable. To avoid oscillation, we propose a weak version of EDAC* and generalize it to weak EDGAC* for non-binary cost functions. Using various benchmarks involving the soft variants of hard global constraints ALLDIFFERENT, GCC, SAME, and REGULAR, empirical results demonstrate that our proposal gives improvements of up to an order of magnitude when compared with the traditional constraint optimization approach, both in terms of time and pruning.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {257–292},
numpages = {36}
}

@article{10.5555/2387915.2387921,
author = {Zeng, Yifeng and Doshi, Prashant},
title = {Exploiting Model Equivalences for Solving Interactive Dynamic Influence Diagrams},
year = {2012},
issue_date = {January 2012},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {43},
number = {1},
issn = {1076-9757},
abstract = {We focus on the problem of sequential decision making in partially observable environments shared with other agents of uncertain types having similar or conflicting objectives. This problem has been previously formalized by multiple frameworks one of which is the interactive dynamic influence diagram (I-DID), which generalizes the well-known influence diagram to the multiagent setting. I-DIDs are graphical models and may be used to compute the policy of an agent given its belief over the physical state and others' models, which changes as the agent acts and observes in the multiagent setting.As we may expect, solving I-DIDs is computationally hard. This is predominantly due to the large space of candidate models ascribed to the other agents and its exponential growth over time. We present two methods for reducing the size of the model space and stemming its exponential growth. Both these methods involve aggregating individual models into equivalence classes. Our first method groups together behaviorally equivalent models and selects only those models for updating which will result in predictive behaviors that are distinct from others in the updated model space. The second method further compacts the model space by focusing on portions of the behavioral predictions. Specifically, we cluster actionally equivalent models that prescribe identical actions at a single time step. Exactly identifying the equivalences would require us to solve all models in the initial set. We avoid this by selectively solving some of the models, thereby introducing an approximation. We discuss the error introduced by the approximation, and empirically demonstrate the improved efficiency in solving I-DIDs due to the equivalences.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {211–255},
numpages = {45}
}

@article{10.5555/2387915.2387920,
author = {Pesant, Gilles and Quimper, Claude-Guy and Zanarini, Alessandro},
title = {Counting-Based Search: Branching Heuristics for Constraint Satisfaction Problems},
year = {2012},
issue_date = {January 2012},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {43},
number = {1},
issn = {1076-9757},
abstract = {Designing a search heuristic for constraint programming that is reliable across problem domains has been an important research topic in recent years. This paper concentrates on one family of candidates: counting-based search. Such heuristics seek to make branching decisions that preserve most of the solutions by determining what proportion of solutions to each individual constraint agree with that decision. Whereas most generic search heuristics in constraint programming rely on local information at the level of the individual variable, our search heuristics are based on more global information at the constraint level. We design several algorithms that are used to count the number of solutions to specific families of constraints and propose some search heuristics exploiting such information. The experimental part of the paper considers eight problem domains ranging from well-established benchmark puzzles to rostering and sport scheduling. An initial empirical analysis identifies heuristic maxSD as a robust candidate among our proposals. We then evaluate the latter against the state of the art, including the latest generic search heuristics, restarts, and discrepancy-based tree traversals. Experimental results show that counting-based search generally outperforms other generic heuristics.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {173–210},
numpages = {38}
}

@article{10.5555/2387915.2387919,
author = {Flati, Tiziano and Navigli, Roberto},
title = {The CQC Algorithm: Cycling in Graphs to Semantically Enrich and Enhance a Bilingual Dictionary},
year = {2012},
issue_date = {January 2012},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {43},
number = {1},
issn = {1076-9757},
abstract = {Bilingual machine-readable dictionaries are knowledge resources useful in many automatic tasks. However, compared to monolingual computational lexicons like WordNet, bilingual dictionaries typically provide a lower amount of structured information such as lexical and semantic relations, and often do not cover the entire range of possible translations for a word of interest. In this paper we present Cycles and Quasi-Cycles (CQC), a novel algorithm for the automated disambiguation of ambiguous translations in the lexical entries of a bilingual machine-readable dictionary. The dictionary is represented as a graph, and cyclic patterns are sought in this graph to assign an appropriate sense tag to each translation in a lexical entry. Further, we use the algorithm's output to improve the quality of the dictionary itself, by suggesting accurate solutions to structural problems such as misalignments, partial alignments and missing entries. Finally, we successfully apply CQC to the task of synonym extraction.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {135–171},
numpages = {37}
}

@article{10.5555/2387915.2387918,
author = {Sadilek, Adam and Kautz, Henry},
title = {Location-Based Reasoning about Complex Multi-Agent Behavior},
year = {2012},
issue_date = {January 2012},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {43},
number = {1},
issn = {1076-9757},
abstract = {Recent research has shown that surprisingly rich models of human activity can be learned from GPS (positional) data. However, most effort to date has concentrated on modeling single individuals or statistical properties of groups of people. Moreover, prior work focused solely on modeling actual successful executions (and not failed or attempted executions) of the activities of interest. We, in contrast, take on the task of understanding human interactions, attempted interactions, and intentions from noisy sensor data in a fully relational multi-agent setting. We use a real-world game of capture the flag to illustrate our approach in a well-defined domain that involves many distinct cooperative and competitive joint activities. We model the domain using Markov logic, a statistical-relational language, and learn a theory that jointly denoises the data and infers occurrences of high-level activities, such as a player capturing an enemy. Our unified model combines constraints imposed by the geometry of the game area, the motion model of the players, and by the rules and dynamics of the game in a probabilistically and logically sound fashion. We show that while it may be impossible to directly detect a multi-agent activity due to sensor noise or malfunction, the occurrence of the activity can still be inferred by considering both its impact on the future behaviors of the people involved as well as the events that could have preceded it. Further, we show that given a model of successfully performed multi-agent activities, along with a set of examples of failed attempts at the same activities, our system automatically learns an augmented model that is capable of recognizing success and failure, as well as goals of people's actions with high accuracy. We compare our approach with other alternatives and show that our unified model, which takes into account not only relationships among individual players, but also relationships among activities over the entire length of a game, although more computationally costly, is significantly more accurate. Finally, we demonstrate that explicitly modeling unsuccessful attempts boosts performance on other important recognition tasks.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {87–133},
numpages = {47}
}

@article{10.5555/2387915.2387917,
author = {Fu, Na and Lau, Hoong Chuin and Varakantham, Pradeep and Xiao, Fei},
title = {Robust Local Search for Solving RCPSP/Max with Durational Uncertainty},
year = {2012},
issue_date = {January 2012},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {43},
number = {1},
issn = {1076-9757},
abstract = {Scheduling problems in manufacturing, logistics and project management have frequently been modeled using the framework of Resource Constrained Project Scheduling Problems with minimum and maximum time lags (RCPSP/max). Due to the importance of these problems, providing scalable solution schedules for RCPSP/max problems is a topic of extensive research. However, all existing methods for solving RCPSP/max assume that durations of activities are known with certainty, an assumption that does not hold in real world scheduling problems where unexpected external events such as manpower availability, weather changes, etc. lead to delays or advances in completion of activities. Thus, in this paper, our focus is on providing a scalable method for solving RCPSP/max problems with durational uncertainty. To that end, we introduce the robust local search method consisting of three key ideas: (a) Introducing and studying the properties of two decision rule approximations used to compute start times of activities with respect to dynamic realizations of the durational uncertainty; (b) Deriving the expression for robust makespan of an execution strategy based on decision rule approximations; and (c) A robust local search mechanism to efficiently compute activity execution strategies that are robust against durational uncertainty. Furthermore, we also provide enhancements to local search that exploit temporal dependencies between activities. Our experimental results illustrate that robust local search is able to provide robust execution strategies efficiently.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {43–86},
numpages = {44}
}

@article{10.5555/2387915.2387916,
author = {Stulp, Freek and Fedrizzi, Andreas and M\"{o}senlechner, Lorenz and Beetz, Michael},
title = {Learning and Reasoning with Action-Related Places for Robust Mobile Manipulation},
year = {2012},
issue_date = {January 2012},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {43},
number = {1},
issn = {1076-9757},
abstract = {We propose the concept of Action-Related Place (ARPLACE) as a powerful and flexible representation of task-related place in the context of mobile manipulation. ARPlace represents robot base locations not as a single position, but rather as a collection of positions, each with an associated probability that the manipulation action will succeed when located there. ARPLACES are generated using a predictive model that is acquired through experience-based learning, and take into account the uncertainty the robot has about its own location and the location of the object to be manipulated.When executing the task, rather than choosing one specific goal position based only on the initial knowledge about the task context, the robot instantiates an ARPLACE, and bases its decisions on this ARPLACE, which is updated as new information about the task becomes available. To show the advantages of this least-commitment approach, we present a transformational planner that reasons about ARPLACE in order to optimize symbolic plans. Our empirical evaluation demonstrates that using ARPLACE leads to more robust and efficient mobile manipulation in the face of state estimation uncertainty on our simulated robot.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {1–42},
numpages = {42}
}

@article{10.5555/2208436.2208460,
author = {Gabbay, Dov and Pearce, David and Valverde, Agust\'{\i}n},
title = {Interpolable Formulas in Equilibrium Logic and Answer Set Programming},
year = {2011},
issue_date = {September 2011},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {42},
number = {1},
issn = {1076-9757},
abstract = {Interpolation is an important property of classical and many non-classical logics that has been shown to have interesting applications in computer science and AI. Here we study the Interpolation Property for the the non-monotonic system of equilibrium logic, establishing weaker or stronger forms of interpolation depending on the precise interpretation of the inference relation. These results also yield a form of interpolation for ground logic programs under the answer sets semantics. For disjunctive logic programs we also study the property of uniform interpolation that is closely related to the concept of variable forgetting. The first-order version of equilibrium logic has analogous Interpolation properties whenever the collection of equilibrium models is (first-order) definable. Since this is the case for so-called safe programs and theories, it applies to the usual situations that arise in practical answer set programming.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {917–943},
numpages = {27}
}

@article{10.5555/2208436.2208459,
author = {Agmon, Noa and Kaminka, Gal A and Kraus, Sarit},
title = {Multi-Robot Adversarial Patrolling: Facing a Full-Knowledge Opponent},
year = {2011},
issue_date = {September 2011},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {42},
number = {1},
issn = {1076-9757},
abstract = {The problem of adversarial multi-robot patrol has gained interest in recent years, mainly due to its immediate relevance to various security applications. In this problem, robots are required to repeatedly visit a target area in a way that maximizes their chances of detecting an adversary trying to penetrate through the patrol path. When facing a strong adversary that knows the patrol strategy of the robots, if the robots use a deterministic patrol algorithm, then in many cases it is easy for the adversary to penetrate undetected (in fact, in some of those cases the adversary can guarantee penetration). Therefore this paper presents a non-deterministic patrol framework for the robots. Assuming that the strong adversary will take advantage of its knowledge and try to penetrate through the patrol's weakest spot, hence an optimal algorithm is one that maximizes the chances of detection in that point. We therefore present a polynomial-time algorithm for determining an optimal patrol under the Markovian strategy assumption for the robots, such that the probability of detecting the adversary in the patrol's weakest spot is maximized. We build upon this framework and describe an optimal patrol strategy for several robotic models based on their movement abilities (directed or undirected) and sensing abilities (perfect or imperfect), and in different environment models - either patrol around a perimeter (closed polygon) or an open fence (open polyline).},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {887–916},
numpages = {30}
}

@article{10.5555/2208436.2208458,
author = {Ginsberg, Matthew L.},
title = {DR.FILL: Crosswords and an Implemented Solver for Singly Weighted CSPs},
year = {2011},
issue_date = {September 2011},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {42},
number = {1},
issn = {1076-9757},
abstract = {We describe Dr. Fill, a program that solves American-style crossword puzzles. From a technical perspective, Dr. Fill works by converting crosswords to weighted csps, and then using a variety of novel techniques to find a solution. These techniques include generally applicable heuristics for variable and value selection, a variant of limited discrepancy search, and postprocessing and partitioning ideas. Branch and bound is not used, as it was incompatible with postprocessing and was determined experimentally to be of little practical value. Dr. Fill's performance on crosswords from the American Crossword Puzzle Tournament suggests that it ranks among the top fifty or so crossword solvers in the world.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {851–886},
numpages = {36}
}

@article{10.5555/2208436.2208457,
author = {Wu, Jia-Hong and Kalyanam, Rajesh and Givan, Robert},
title = {Stochastic Enforced Hill-Climbing},
year = {2011},
issue_date = {September 2011},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {42},
number = {1},
issn = {1076-9757},
abstract = {Enforced hill-climbing is an effective deterministic hill-climbing technique that deals with local optima using breadth-first search (a process called "basin flooding"). We propose and evaluate a stochastic generalization of enforced hill-climbing for online use in goal-oriented probabilistic planning problems. We assume a provided heuristic function estimating expected cost to the goal with flaws such as local optima and plateaus that thwart straightforward greedy action choice. While breadth-first search is effective in exploring basins around local optima in deterministic problems, for stochastic problems we dynamically build and solve a heuristic-based Markov decision process (MDP) model of the basin in order to find a good escape policy exiting the local optimum. We note that building this model involves integrating the heuristic into the MDP problem because the local goal is to improve the heuristic.We evaluate our proposal in twenty-four recent probabilistic planning-competition benchmark domains and twelve probabilistically interesting problems from recent literature. For evaluation, we show that stochastic enforced hill-climbing (SEH) produces better policies than greedy heuristic following for value/cost functions derived in two very different ways: one type derived by using deterministic heuristics on a deterministic relaxation and a second type derived by automatic learning of Bellman-error features from domain-specific experience. Using the first type of heuristic, SEH is shown to generally outperform all planners from the first three international probabilistic planning competitions.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {815–850},
numpages = {36}
}

@article{10.5555/2208436.2208456,
author = {Vytelingum, Perukrishnen and Voice, Thomas D. and Ramchurn, Sarvapali D. and Rogers, Alex and Jennings, Nicholas R.},
title = {Theoretical and Practical Foundations of Large-Scale Agent-Based Micro-Storage in the Smart Grid},
year = {2011},
issue_date = {September 2011},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {42},
number = {1},
issn = {1076-9757},
abstract = {In this paper, we present a novel decentralised management technique that allows electricity micro-storage devices, deployed within individual homes as part of a smart electricity grid, to converge to profitable and efficient behaviours. Specifically, we propose the use of software agents, residing on the users' smart meters, to automate and optimise the charging cycle of micro-storage devices in the home to minimise its costs, and we present a study of both the theoretical underpinnings and the implications of a practical solution, of using software agents for such micro-storage management. First, by formalising the strategic choice each agent makes in deciding when to charge its battery, we develop a game-theoretic framework within which we can analyse the competitive equilibria of an electricity grid populated by such agents and hence predict the best consumption profile for that population given their battery properties and individual load profiles. Our framework also allows us to compute theoretical bounds on the amount of storage that will be adopted by the population. Second, to analyse the practical implications of micro-storage deployments in the grid, we present a novel algorithm that each agent can use to optimise its battery storage profile in order to minimise its owner's costs. This algorithm uses a learning strategy that allows it to adapt as the price of electricity changes in real-time, and we show that the adoption of these strategies results in the system converging to the theoretical equilibria. Finally, we empirically evaluate the adoption of our micro-storage management technique within a complex setting, based on the UK electricity market, where agents may have widely varying load profiles, battery types, and learning rates. In this case, our approach yields savings of up to 14% in energy cost for an average consumer using a storage device with a capacity of less than 4.5 kWh and up to a 7% reduction in carbon emissions resulting from electricity generation (with only domestic consumers adopting micro-storage and, commercial and industrial consumers not changing their demand). Moreover, corroborating our theoretical bound, an equilibrium is shown to exist where no more than 48% of households would wish to own storage devices and where social welfare would also be improved (yielding overall annual savings of nearly £1.5B).},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {765–813},
numpages = {49}
}

@article{10.5555/2208436.2208455,
author = {Bonatti, Piero A. and Faella, Marco and Sauro, Luigi},
title = {Defeasible Inclusions in Low-Complexity DLs},
year = {2011},
issue_date = {September 2011},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {42},
number = {1},
issn = {1076-9757},
abstract = {Some of the applications of OWL and RDF (e.g. biomedical knowledge representation and semantic policy formulation) call for extensions of these languages with nonmonotonic constructs such as inheritance with overriding. Nonmonotonic description logics have been studied for many years, however no practical such knowledge representation languages exist, due to a combination of semantic difficulties and high computational complexity. Independently, low-complexity description logics such as DL-lite and EL have been introduced and incorporated in the OWL standard. Therefore, it is interesting to see whether the syntactic restrictions characterizing DL-lite and EL bring computational benefits to their nonmonotonic versions, too. In this paper we extensively investigate the computational complexity of Circumscription when knowledge bases are formulated in DL-liteR, EL, and fragments thereof. We identify fragments whose complexity ranges from P to the second level of the polynomial hierarchy, as well as fragments whose complexity raises to PSPACE and beyond.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {719–764},
numpages = {46}
}

@article{10.5555/2208436.2208454,
author = {Amig\'{o}, Enrique and Gonzalo, Julio and Artiles, Javier and Verdejo, Felisa},
title = {Combining Evaluation Metrics via the Unanimous Improvement Ratio and Its Application to Clustering Tasks},
year = {2011},
issue_date = {September 2011},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {42},
number = {1},
issn = {1076-9757},
abstract = {Many Artificial Intelligence tasks cannot be evaluated with a single quality criterion and some sort of weighted combination is needed to provide system rankings. A problem of weighted combination measures is that slight changes in the relative weights may produce substantial changes in the system rankings. This paper introduces the Unanimous Improvement Ratio (UIR), a measure that complements standard metric combination criteria (such as van Rijsbergen's F-measure) and indicates how robust the measured differences are to changes in the relative weights of the individual metrics. UIR is meant to elucidate whether a perceived difference between two systems is an artifact of how individual metrics are weighted.Besides discussing the theoretical foundations of UIR, this paper presents empirical results that confirm the validity and usefulness of the metric for the Text Clustering problem, where there is a tradeoff between precision and recall based metrics and results are particularly sensitive to the weighting scheme used to combine them. Remarkably, our experiments show that UIR can be used as a predictor of how well differences between systems measured on a given test bed will also hold in a different test bed.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {689–718},
numpages = {30}
}

@article{10.5555/2208436.2208453,
author = {Pe\~{n}a, Jose M.},
title = {Finding Consensus Bayesian Network Structures},
year = {2011},
issue_date = {September 2011},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {42},
number = {1},
issn = {1076-9757},
abstract = {Suppose that multiple experts (or learning algorithms) provide us with alternative Bayesian network (BN) structures over a domain, and that we are interested in combining them into a single consensus BN structure. Specifically, we are interested in that the consensus BN structure only represents independences all the given BN structures agree upon and that it has as few parameters associated as possible. In this paper, we prove that there may exist several non-equivalent consensus BN structures and that finding one of them is NP-hard. Thus, we decide to resort to heuristics to find an approximated consensus BN structure. In this paper, we consider the heuristic proposed by Matzkevich and Abramson, which builds upon two algorithms, called Methods A and B, for efficiently deriving the minimal directed independence map of a BN structure relative to a given node ordering. Methods A and B are claimed to be correct although no proof is provided (a proof is just sketched). In this paper, we show that Methods A and B are not correct and propose a correction of them.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {661–687},
numpages = {27}
}

@article{10.5555/2208436.2208452,
author = {Conrad, Patrick R. and Williams, Brian C.},
title = {Drake: An Efficient Executive for Temporal Plans with Choice},
year = {2011},
issue_date = {September 2011},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {42},
number = {1},
issn = {1076-9757},
abstract = {This work presents Drake, a dynamic executive for temporal plans with choice. Dynamic plan execution strategies allow an autonomous agent to react quickly to unfolding events, improving the robustness of the agent. Prior work developed methods for dynamically dispatching Simple Temporal Networks, and further research enriched the expressiveness of the plans executives could handle, including discrete choices, which are the focus of this work. However, in some approaches to date, these additional choices induce significant storage or latency requirements to make flexible execution possible.Drake is designed to leverage the low latency made possible by a preprocessing step called compilation, while avoiding high memory costs through a compact representation. We leverage the concepts of labels and environments, taken from prior work in Assumption-based Truth Maintenance Systems (ATMS), to concisely record the implications of the discrete choices, exploiting the structure of the plan to avoid redundant reasoning or storage. Our labeling and maintenance scheme, called the Labeled Value Set Maintenance System, is distinguished by its focus on properties fundamental to temporal problems, and, more generally, weighted graph algorithms. In particular, the maintenance system focuses on maintaining a minimal representation of non-dominated constraints. We benchmark Drake's performance on random structured problems, and find that Drake reduces the size of the compiled representation by a factor of over 500 for large problems, while incurring only a modest increase in run-time latency, compared to prior work in compiled executives for temporal plans with discrete choices.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {607–659},
numpages = {53}
}

@article{10.5555/2208436.2208451,
author = {Ponsen, Marc and de Jong, Steven and Lanctot, Marc},
title = {Computing Approximate Nash Equilibria and Robust Best-Responses Using Sampling},
year = {2011},
issue_date = {September 2011},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {42},
number = {1},
issn = {1076-9757},
abstract = {This article discusses two contributions to decision-making in complex partially observable stochastic games. First, we apply two state-of-the-art search techniques that use Monte-Carlo sampling to the task of approximating a Nash-Equilibrium (NE) in such games, namely Monte-Carlo Tree Search (MCTS) and Monte-Carlo Counterfactual Regret Minimization (MCCFR). MCTS has been proven to approximate a NE in perfect-information games. We show that the algorithm quickly finds a reasonably strong strategy (but not a NE) in a complex imperfect information game, i.e. Poker. MCCFR on the other hand has theoretical NE convergence guarantees in such a game. We apply MCCFR for the first time in Poker. Based on our experiments, we may conclude that MCTS is a valid approach if one wants to learn reasonably strong strategies fast, whereas MCCFR is the better choice if the quality of the strategy is most important.Our second contribution relates to the observation that a NE is not a best response against players that are not playing a NE. We present Monte-Carlo Restricted Nash Response (MCRNR), a sample-based algorithm for the computation of restricted Nash strategies. These are robust bestresponse strategies that (1) exploit non-NE opponents more than playing a NE and (2) are not (overly) exploitable by other strategies. We combine the advantages of two state-of-the-art algorithms, i.e. MCCFR and Restricted Nash Response (RNR). MCRNR samples only relevant parts of the game tree. We show that MCRNR learns quicker than standard RNR in smaller games. Also we show in Poker that MCRNR learns robust best-response strategies fast, and that these strategies exploit opponents more than playing a NE does.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {575–605},
numpages = {31}
}

@article{10.5555/2208436.2208450,
author = {Elkind, Edith and Faliszewski, Piotr and Slinko, Arkadii},
title = {Cloning in Elections: Finding the Possible Winners},
year = {2011},
issue_date = {September 2011},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {42},
number = {1},
issn = {1076-9757},
abstract = {We consider the problem of manipulating elections by cloning candidates. In our model, a manipulator can replace each candidate c by several clones, i.e., new candidates that are so similar to c that each voter simply replaces c in his vote with a block of these new candidates, ranked consecutively. The outcome of the resulting election may then depend on the number of clones as well as on how each voter orders the clones within the block. We formalize what it means for a cloning manipulation to be successful (which turns out to be a surprisingly delicate issue), and, for a number of common voting rules, characterize the preference profiles for which a successful cloning manipulation exists. We also consider the model where there is a cost associated with producing each clone, and study the complexity of finding a minimum-cost cloning manipulation. Finally, we compare cloning with two related problems: the problem of control by adding candidates and the problem of possible (co)winners when new alternatives can join.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {529–573},
numpages = {45}
}

@article{10.5555/2208436.2208449,
author = {Alviano, Mario and Calimeri, Francesco and Faber, Wolfgang and Leone, Nicola and Perri, Simona},
title = {Unfounded Sets and Well-Founded Semantics of Answer Set Programs with Aggregates},
year = {2011},
issue_date = {September 2011},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {42},
number = {1},
issn = {1076-9757},
abstract = {Logic programs with aggregates (LPA) are one of the major linguistic extensions to Logic Programming (LP). In this work, we propose a generalization of the notions of unfounded set and well-founded semantics for programs with monotone and antimonotone aggregates (LPm,aA programs). In particular, we present a new notion of unfounded set for LPm,aA programs, which is a sound generalization of the original definition for standard (aggregate-free) LP. On this basis, we define a well-founded operator for LPm,aA programs, the fixpoint of which is called well-founded model (or well-founded semantics) for LPm,aA programs. The most important properties of unfounded sets and the well-founded semantics for standard LP are retained by this generalization, notably existence and uniqueness of the well-founded model, together with a strong relationship to the answer set semantics for LPm,aA programs. We show that one of the D-well-founded semantics, defined by Pelov, Denecker, and Bruynooghe for a broader class of aggregates using approximating operators, coincides with the well-founded model as defined in this work on LPm,aA programs. We also discuss some complexity issues, most importantly we give a formal proof of tractable computation of the well-founded model for LPm,aA programs. Moreover, we prove that for general LPA programs, which may contain aggregates that are neither monotone nor antimonotone, deciding satisfaction of aggregate expressions with respect to partial interpretations is coNP-complete. As a consequence, a well-founded semantics for general LPA programs that allows for tractable computation is unlikely to exist, which justifies the restriction on LPm,aA programs. Finally, we present a prototype system extending DLV, which supports the well-founded semantics for LPm,aA programs, at the time of writing the only implemented system that does so. Experiments with this prototype show significant computational advantages of aggregate constructs over equivalent aggregate-free encodings.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {487–527},
numpages = {41}
}

@article{10.5555/2208436.2208448,
author = {Golovin, Daniel and Krause, Andreas},
title = {Adaptive Submodularity: Theory and Applications in Active Learning and Stochastic Optimization},
year = {2011},
issue_date = {September 2011},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {42},
number = {1},
issn = {1076-9757},
abstract = {Many problems in artificial intelligence require adaptively making a sequence of decisions with uncertain outcomes under partial observability. Solving such stochastic optimization problems is a fundamental but notoriously difficult challenge. In this paper, we introduce the concept of adaptive submodularity, generalizing submodular set functions to adaptive policies. We prove that if a problem satisfies this property, a simple adaptive greedy algorithm is guaranteed to be competitive with the optimal policy. In addition to providing performance guarantees for both stochastic maximization and coverage, adaptive submodularity can be exploited to drastically speed up the greedy algorithm by using lazy evaluations. We illustrate the usefulness of the concept by giving several examples of adaptive submodular objectives arising in diverse AI applications including management of sensing resources, viral marketing and active learning. Proving adaptive submodularity for these problems allows us to recover existing results in these applications as special cases, improve approximation guarantees and handle natural generalizations.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {427–486},
numpages = {60}
}

@article{10.5555/2208436.2208447,
author = {Gr\"{u}nwald, Peter D. and Halpern, Joseph Y.},
title = {Making Decisions Using Sets of Probabilities: Updating, Time Consistency, and Calibration},
year = {2011},
issue_date = {September 2011},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {42},
number = {1},
issn = {1076-9757},
abstract = {We consider how an agent should update her beliefs when her beliefs are represented by a set P of probability distributions, given that the agent makes decisions using the minimax criterion, perhaps the best-studied and most commonly-used criterion in the literature. We adopt a game-theoretic framework, where the agent plays against a bookie, who chooses some distribution from P. We consider two reasonable games that differ in what the bookie knows when he makes his choice. Anomalies that have been observed before, like time inconsistency, can be understood as arising because different games are being played, against bookies with different information. We characterize the important special cases in which the optimal decision rules according to the minimax criterion amount to either conditioning or simply ignoring the information. Finally, we consider the relationship between updating and calibration when uncertainty is described by sets of probabilities. Our results emphasize the key role of the rectangularity condition of Epstein and Schneider.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {393–426},
numpages = {34}
}

@article{10.5555/2208436.2208446,
author = {Talvitie, Erik and Singh, Satinder},
title = {Learning to Make Predictions in Partially Observable Environments without a Generative Model},
year = {2011},
issue_date = {September 2011},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {42},
number = {1},
issn = {1076-9757},
abstract = {When faced with the problem of learning a model of a high-dimensional environment, a common approach is to limit the model to make only a restricted set of predictions, thereby simplifying the learning problem. These partial models may be directly useful for making decisions or may be combined together to form a more complete, structured model. However, in partially observable (non-Markov) environments, standard model-learning methods learn generative models, i.e. models that provide a probability distribution over all possible futures (such as POMDPs). It is not straightforward to restrict such models to make only certain predictions, and doing so does not always simplify the learning problem. In this paper we present prediction profile models: non-generative partial models for partially observable systems that make only a given set of predictions, and are therefore far simpler than generative models in some cases. We formalize the problem of learning a prediction profile model as a transformation of the original model-learning problem, and show empirically that one can learn prediction profile models that make a small set of important predictions even in systems that are too complex for standard generative models.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {353–392},
numpages = {40}
}

@article{10.5555/2208436.2208445,
author = {Yuan, Changhe and Lim, Heejin and Lu, Tsai-Ching},
title = {Most Relevant Explanation in Bayesian Networks},
year = {2011},
issue_date = {September 2011},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {42},
number = {1},
issn = {1076-9757},
abstract = {A major inference task in Bayesian networks is explaining why some variables are observed in their particular states using a set of target variables. Existing methods for solving this problem often generate explanations that are either too simple (underspecified) or too complex (overspecified). In this paper, we introduce a method called Most Relevant Explanation (MRE) which finds a partial instantiation of the target variables that maximizes the generalized Bayes factor (GBF) as the best explanation for the given evidence. Our study shows that GBF has several theoretical properties that enable MRE to automatically identify the most relevant target variables in forming its explanation. In particular, conditional Bayes factor (CBF), defined as the GBF of a new explanation conditioned on an existing explanation, provides a soft measure on the degree of relevance of the variables in the new explanation in explaining the evidence given the existing explanation. As a result, MRE is able to automatically prune less relevant variables from its explanation. We also show that CBF is able to capture well the explaining-away phenomenon that is often represented in Bayesian networks. Moreover, we define two dominance relations between the candidate solutions and use the relations to generalize MRE to find a set of top explanations that is both diverse and representative. Case studies on several benchmark diagnostic Bayesian networks show that MRE is often able to find explanatory hypotheses that are not only precise but also concise.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {309–352},
numpages = {44}
}

@article{10.5555/2208436.2208444,
author = {Ribeiro, Ricardo and de Matos, David Martins},
title = {Revisiting Centrality-as-Relevance: Support Sets and Similarity as Geometric Proximity},
year = {2011},
issue_date = {September 2011},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {42},
number = {1},
issn = {1076-9757},
abstract = {In automatic summarization, centrality-as-relevance means that the most important content of an information source, or a collection of information sources, corresponds to the most central passages, considering a representation where such notion makes sense (graph, spatial, etc.). We assess the main paradigms, and introduce a new centrality-based relevance model for automatic summarization that relies on the use of support sets to better estimate the relevant content. Geometric proximity is used to compute semantic relatedness. Centrality (relevance) is determined by considering the whole input source (and not only local information), and by taking into account the existence of minor topics or lateral subjects in the information sources to be summarized. The method consists in creating, for each passage of the input source, a support set consisting only of the most semantically related passages. Then, the determination of the most relevant content is achieved by selecting the passages that occur in the largest number of support sets. This model produces extractive summaries that are generic, and language- and domainindependent. Thorough automatic evaluation shows that the method achieves state-of-the art performance, both in written text, and automatically transcribed speech summarization, including when compared to considerably more complex approaches.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {275–308},
numpages = {34}
}

@article{10.5555/2208436.2208443,
author = {Santhanam, Ganesh Ram and Basu, Samik and Honavar, Vasant},
title = {Representing and Reasoning with Qualitative Preferences for Compositional Systems},
year = {2011},
issue_date = {September 2011},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {42},
number = {1},
issn = {1076-9757},
abstract = {Many applications, e.g., Web service composition, complex system design, team formation, etc., rely on methods for identifying collections of objects or entities satisfying some functional requirement. Among the collections that satisfy the functional requirement, it is often necessary to identify one or more collections that are optimal with respect to user preferences over a set of attributes that describe the non-functional properties of the collection.We develop a formalism that lets users express the relative importance among attributes and qualitative preferences over the valuations of each attribute. We define a dominance relation that allows us to compare collections of objects in terms of preferences over attributes of the objects that make up the collection. We establish some key properties of the dominance relation. In particular, we show that the dominance relation is a strict partial order when the intra-attribute preference relations are strict partial orders and the relative importance preference relation is an interval order.We provide algorithms that use this dominance relation to identify the set of most preferred collections. We show that under certain conditions, the algorithms are guaranteed to return only (sound), all (complete), or at least one (weakly complete) of the most preferred collections. We present results of simulation experiments comparing the proposed algorithms with respect to (a) the quality of solutions (number of most preferred solutions) produced by the algorithms, and (b) their performance and efficiency. We also explore some interesting conjectures suggested by the results of our experiments that relate the properties of the user preferences, the dominance relation, and the algorithms.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {211–274},
numpages = {64}
}

@article{10.5555/2208436.2208442,
author = {Dai, Peng and Mausam and Weld, Daniel S. and Goldsmith, Judy},
title = {Topological Value Iteration Algorithms},
year = {2011},
issue_date = {September 2011},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {42},
number = {1},
issn = {1076-9757},
abstract = {Value iteration is a powerful yet inefficient algorithm for Markov decision processes (MDPs) because it puts the majority of its effort into backing up the entire state space, which turns out to be unnecessary in many cases. In order to overcome this problem, many approaches have been proposed. Among them, ILAO* and variants of RTDP are state-of-the-art ones. These methods use reachability analysis and heuristic search to avoid some unnecessary backups. However, none of these approaches build the graphical structure of the state transitions in a pre-processing step or use the structural information to systematically decompose a problem, whereby generating an intelligent backup sequence of the state space. In this paper, we present two optimal MDP algorithms. The first algorithm, topological value iteration (TVI), detects the structure of MDPs and backs up states based on topological sequences. It (1) divides an MDP into strongly-connected components (SCCs), and (2) solves these components sequentially. TVI outperforms VI and other state-of-the-art algorithms vastly when an MDP has multiple, close-to-equal-sized SCCs. The second algorithm, focused topological value iteration (FTVI), is an extension of TVI. FTVI restricts its attention to connected components that are relevant for solving the MDP. Specifically, it uses a small amount of heuristic search to eliminate provably sub-optimal actions; this pruning allows FTVI to find smaller connected components, thus running faster. We demonstrate that FTVI outperforms TVI by an order of magnitude, averaged across several domains. Surprisingly, FTVI also significantly outperforms popular 'heuristically-informed' MDP algorithms such as ILAO*, LRTDP, BRTDP and Bayesian-RTDP in many domains, sometimes by as much as two orders of magnitude. Finally, we characterize the type of domains where FTVI excels -- suggesting a way to an informed choice of solver.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {181–209},
numpages = {29}
}

@article{10.5555/2208436.2208441,
author = {Lee, Joohyung and Meng, Yunsong},
title = {First-Order Stable Model Semantics and First-Order Loop Formulas},
year = {2011},
issue_date = {September 2011},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {42},
number = {1},
issn = {1076-9757},
abstract = {Lin and Zhao's theorem on loop formulas states that in the propositional case the stable model semantics of a logic program can be completely characterized by propositional loop formulas, but this result does not fully carry over to the first-order case. We investigate the precise relationship between the first-order stable model semantics and first-order loop formulas, and study conditions under which the former can be represented by the latter. In order to facilitate the comparison, we extend the definition of a first-order loop formula which was limited to a nondisjunctive program, to a disjunctive program and to an arbitrary first-order theory. Based on the studied relationship we extend the syntax of a logic program with explicit quantifiers, which allows us to do reasoning involving non-Herbrand stable models using first-order reasoners. Such programs can be viewed as a special class of first-order theories under the stable model semantics, which yields more succinct loop formulas than the general language due to their restricted syntax.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {125–180},
numpages = {56}
}

@article{10.5555/2208436.2208440,
author = {Hoshino, Richard and Kawarabayashi, Ken-ichi},
title = {Scheduling Bipartite Tournaments to Minimize Total Travel Distance},
year = {2011},
issue_date = {September 2011},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {42},
number = {1},
issn = {1076-9757},
abstract = {In many professional sports leagues, teams from opposing leagues/conferences compete against one another, playing inter-league games. This is an example of a bipartite tournament. In this paper, we consider the problem of reducing the total travel distance of bipartite tournaments, by analyzing inter-league scheduling from the perspective of discrete optimization. This research has natural applications to sports scheduling, especially for leagues such as the National Basketball Association (NBA) where teams must travel long distances across North America to play all their games, thus consuming much time, money, and greenhouse gas emissions.We introduce the Bipartite Traveling Tournament Problem (BTTP), the interleague variant of the well-studied Traveling Tournament Problem. We prove that the 2n-team BTTP is NP-complete, but for small values of n, a distance-optimal inter-league schedule can be generated from an algorithm based on minimum-weight 4-cycle-covers. We apply our theoretical results to the 12-team Nippon Professional Baseball (NPB) league in Japan, producing a provably-optimal schedule requiring 42950 kilometres of total team travel, a 16% reduction compared to the actual distance traveled by these teams during the 2010 NPB season. We also develop a nearly-optimal inter-league tournament for the 30-team NBA league, just 3.8% higher than the trivial theoretical lower bound.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {91–124},
numpages = {34}
}

@article{10.5555/2208436.2208439,
author = {Wang, Ko-Hsin Cindy and Botea, Adi},
title = {MAPP: A Scalable Multi-Agent Path Planning Algorithm with Tractability and Completeness Guarantees},
year = {2011},
issue_date = {September 2011},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {42},
number = {1},
issn = {1076-9757},
abstract = {Multi-agent path planning is a challenging problem with numerous real-life applications. Running a centralized search such as A* in the combined state space of all units is complete and cost-optimal, but scales poorly, as the state space size is exponential in the number of mobile units. Traditional decentralized approaches, such as FAR and WHCA*, are faster and more scalable, being based on problem decomposition. However, such methods are incomplete and provide no guarantees with respect to the running time or the solution quality. They are not necessarily able to tell in a reasonable time whether they would succeed in finding a solution to a given instance.We introduce MAPP, a tractable algorithm for multi-agent path planning on undirected graphs. We present a basic version and several extensions. They have low-polynomial worst-case upper bounds for the running time, the memory requirements, and the length of solutions. Even though all algorithmic versions are incomplete in the general case, each provides formal guarantees on problems it can solve. For each version, we discuss the algorithm's completeness with respect to clearly defined subclasses of instances.Experiments were run on realistic game grid maps. MAPP solved 99.86% of all mobile units, which is 18-22% better than the percentage of FAR and WHCA*. MAPP marked 98.82% of all units as provably solvable during the first stage of plan computation. Parts of MAPP's computation can be re-used across instances on the same map. Speed-wise, MAPP is competitive or significantly faster than WHCA*, depending on whether MAPP performs all computations from scratch. When data that MAPP can re-use are preprocessed offline and readily available, MAPP is slower than the very fast FAR algorithm by a factor of 2.18 on average. MAPP's solutions are on average 20% longer than FAR's solutions and 7-31% longer than WHCA*'s solutions.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {55–90},
numpages = {36}
}

@article{10.5555/2208436.2208438,
author = {Booth, Richard and Meyer, Thomas and Varzinczak, Ivan and Wassermann, Renata},
title = {On the Link between Partial Meet, Kernel, and Infra Contraction and Its Application to Horn Logic},
year = {2011},
issue_date = {September 2011},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {42},
number = {1},
issn = {1076-9757},
abstract = {Standard belief change assumes an underlying logic containing full classical propositional logic. However, there are good reasons for considering belief change in less expressive logics as well. In this paper we build on recent investigations by Delgrande on contraction for Horn logic. We show that the standard basic form of contraction, partial meet, is too strong in the Horn case. This result stands in contrast to Delgrande's conjecture that orderly maxichoice is the appropriate form of contraction for Horn logic. We then define a more appropriate notion of basic contraction for the Horn case, influenced by the convexity property holding for full propositional logic and which we refer to as infra contraction. The main contribution of this work is a result which shows that the construction method for Horn contraction for belief sets based on our infra remainder sets corresponds exactly to Hansson's classical kernel contraction for belief sets, when restricted to Horn logic. This result is obtained via a detour through contraction for belief bases. We prove that kernel contraction for belief bases produces precisely the same results as the belief base version of infra contraction. The use of belief bases to obtain this result provides evidence for the conjecture that Horn belief change is best viewed as a `hybrid' version of belief set change and belief base change. One of the consequences of the link with base contraction is the provision of a representation result for Horn contraction for belief sets in which a version of the Core-retainment postulate features.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {31–53},
numpages = {23}
}

@article{10.5555/2208436.2208437,
author = {Walsh, Toby},
title = {Where Are the Hard Manipulation Problems?},
year = {2011},
issue_date = {September 2011},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {42},
number = {1},
issn = {1076-9757},
abstract = {Voting is a simple mechanism to combine together the preferences of multiple agents. Unfortunately, agents may try to manipulate the result by mis-reporting their preferences. One barrier that might exist to such manipulation is computational complexity. In particular, it has been shown that it is NP-hard to compute how to manipulate a number of different voting rules. However, NP-hardness only bounds the worst-case complexity. Recent theoretical results suggest that manipulation may often be easy in practice. In this paper, we show that empirical studies are useful in improving our understanding of this issue. We consider two settings which represent the two types of complexity results that have been identified in this area: manipulation with unweighted votes by a single agent, and manipulation with weighted votes by a coalition of agents. In the first case, we consider Single Transferable Voting (STV), and in the second case, we consider veto voting. STV is one of the few voting rules used in practice where it is NP-hard to compute how a single agent can manipulate the result when votes are unweighted. It also appears one of the harder voting rules to manipulate since it involves multiple rounds. On the other hand, veto voting is one of the simplest representatives of voting rules where it is NP-hard to compute how a coalition of weighted agents can manipulate the result. In our experiments, we sample a number of distributions of votes including uniform, correlated and real world elections. In many of the elections in our experiments, it was easy to compute how to manipulate the result or to prove that manipulation was impossible. Even when we were able to identify a situation in which manipulation was hard to compute (e.g. when votes are highly correlated and the election is "hung"), we found that the computational difficulty of computing manipulations was somewhat precarious (e.g. with such "hung" elections, even a single uncorrelated voter was enough to make manipulation easy to compute).},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {1–29},
numpages = {29}
}

@article{10.5555/2051237.2051253,
author = {Gra\c{c}a, Jo\~{a}o V. and Ganchev, Kuzman and Coheur, Lu\'{\i}sa and Pereira, Fernando and Taskar, Ben},
title = {Controlling Complexity in Part-of-Speech Induction},
year = {2011},
issue_date = {May 2011},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {41},
number = {2},
issn = {1076-9757},
abstract = {We consider the problem of fully unsupervised learning of grammatical (part-of-speech) categories from unlabeled text. The standard maximum-likelihood hidden Markov model for this task performs poorly, because of its weak inductive bias and large model capacity. We address this problem by refining the model and modifying the learning objective to control its capacity via parametric and non-parametric constraints. Our approach enforces word-category association sparsity, adds morphological and orthographic features, and eliminates hard-to-estimate parameters for rare words. We develop an efficient learning algorithm that is not much more computationally intensive than standard training. We also provide an open-source implementation of the algorithm. Our experiments on five diverse languages (Bulgarian, Danish, English, Portuguese, Spanish) achieve significant improvements compared with previous methods for the same task.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {527–551},
numpages = {25}
}

@article{10.5555/2051237.2051252,
author = {Sturm, J\"{u}rgen and Stachniss, Cyrill and Burgard, Wolfram},
title = {A Probabilistic Framework for Learning Kinematic Models of Articulated Objects},
year = {2011},
issue_date = {May 2011},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {41},
number = {2},
issn = {1076-9757},
abstract = {Robots operating in domestic environments generally need to interact with articulated objects, such as doors, cabinets, dishwashers or fridges. In this work, we present a novel, probabilistic framework for modeling articulated objects as kinematic graphs. Vertices in this graph correspond to object parts, while edges between them model their kinematic relationship. In particular, we present a set of parametric and non-parametric edge models and how they can robustly be estimated from noisy pose observations. We furthermore describe how to estimate the kinematic structure and how to use the learned kinematic models for pose prediction and for robotic manipulation tasks. We finally present how the learned models can be generalized to new and previously unseen objects. In various experiments using real robots with different camera systems as well as in simulation, we show that our approach is valid, accurate and efficient. Further, we demonstrate that our approach has a broad set of applications, in particular for the emerging fields of mobile manipulation and service robotics.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {477–526},
numpages = {50}
}

@article{10.5555/2051237.2051251,
author = {Dvo\v{r}\'{a}k, Wolfgang and Woltran, Stefan},
title = {On the Intertranslatability of Argumentation Semantics},
year = {2011},
issue_date = {May 2011},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {41},
number = {2},
issn = {1076-9757},
abstract = {Translations between different nonmonotonic formalisms always have been an important topic in the field, in particular to understand the knowledge-representation capabilities those formalisms offer. We provide such an investigation in terms of different semantics proposed for abstract argumentation frameworks, a nonmonotonic yet simple formalism which received increasing interest within the last decade. Although the properties of these different semantics are nowadays well understood, there are no explicit results about intertranslatability. We provide such translations wrt. different properties and also give a few novel complexity results which underlie some negative results.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {445–475},
numpages = {31}
}

@article{10.5555/2051237.2051250,
author = {Gy\"{o}rgy, Andr\'{a}s and Kocsis, Levente},
title = {Efficient Multi-Start Strategies for Local Search Algorithms},
year = {2011},
issue_date = {May 2011},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {41},
number = {2},
issn = {1076-9757},
abstract = {Local search algorithms applied to optimization problems often suffer from getting trapped in a local optimum. The common solution for this deficiency is to restart the algorithm when no progress is observed. Alternatively, one can start multiple instances of a local search algorithm, and allocate computational resources (in particular, processing time) to the instances depending on their behavior. Hence, a multi-start strategy has to decide (dynamically) when to allocate additional resources to a particular instance and when to start new instances. In this paper we propose multi-start strategies motivated by works on multi-armed bandit problems and Lipschitz optimization with an unknown constant. The strategies continuously estimate the potential performance of each algorithm instance by supposing a convergence rate of the local search algorithm up to an unknown constant, and in every phase allocate resources to those instances that could converge to the optimum for a particular range of the constant. Asymptotic bounds are given on the performance of the strategies. In particular, we prove that at most a quadratic increase in the number of times the target function is evaluated is needed to achieve the performance of a local search algorithm started from the attraction region of the optimum. Experiments are provided using SPSA (Simultaneous Perturbation Stochastic Approximation) and kmeans as local search algorithms, and the results indicate that the proposed strategies work well in practice, and, in all cases studied, need only logarithmically more evaluations of the target function as opposed to the theoretically suggested quadratic increase.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {407–444},
numpages = {38}
}

@article{10.5555/2051237.2051249,
author = {Lu, Xiaosong and Schwartz, Howard M. and Givigi, Sidney N.},
title = {Policy Invariance under Reward Transformations for General-Sum Stochastic Games},
year = {2011},
issue_date = {May 2011},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {41},
number = {2},
issn = {1076-9757},
abstract = {We extend the potential-based shapingmethod fromMarkov decision processes to multiplayer general-sum stochastic games. We prove that the Nash equilibria in a stochastic game remains unchanged after potential-based shaping is applied to the environment. The property of policy invariance provides a possible way of speeding convergence when learning to play a stochastic game.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {397–406},
numpages = {10}
}

license_type: permissive

branch_name: refs/heads/main

extension: bib


text:
console.log(React);
console.log(ReactDOM);

const element =
Pierwszy element React

const element2 = React.createElement(
    "div",
    null,
    "Pierwszy element"
);

// zadziała
const element3 =

Tekst

// zadziała
const element4 = (

Tekst

)

// zadziała
const element5 =

Tekst

// nie zadziała, elementy nie są w elemencie nadrzędnym
// const element5 = (
//

//

// )

const element6 = (

)

const element7 = (
    <React.Fragment>

    </React.Fragment>
)

// zadziała tak samo jak <React.Fragment> ... </React.Fragment>
const element8 = (
    <>

    </>
)

license: MIT

url: https://raw.githubusercontent.com/Nowocinski/React-Nauka/8cad658b043d1f9d6e4a26321821e4675594fc33/2 - Obiekt React i ReactDOM, JSX/App.js

repository: Nowocinski/React-Nauka

repo_name: Nowocinski/React-Nauka

branch_name: refs/heads/master

extension: js


text:
@article{Serjeant2009,
 abstract = {Earlier reports on homozygous sickle cell (SS) disease have been biased by severely affected cases. The Jamaican clinic which seeks to avoid such bias has 102 patients surviving beyond 60 years. The objective of this study was to examine the features of elderly cases and assess factors determining survival and the behaviour of this disease with advancing age. A retrospective review of all cases and prospective assessment in survivors was conducted at The Sickle Cell Clinic at the University of the West Indies, Kingston, Jamaica previously operated by the MRC Laboratories. All patients with SS disease born prior to December 31, 1943 who would, by January 2004, have passed their 60th birthday were traced and their current status ascertained. The molecular and clinical features were assessed and observations on the clinical behaviour of the disease and of haematology and biochemistry are presented. Of the 102 patients, 58 had died, four had emigrated and 40 were alive, resident in Jamaica and aged 60-87 years. Survival was associated with female gender and higher foetal haemoglobin but not with alpha-thalassaemia or beta-globin haplotype. A tendency to familial clustering among elderly survivors did not reach statistical significance. Painful crises ameliorated with age and there was a benign course in pregnancy. Mean haemoglobin levels fell with age and were generally associated with rising creatinine levels indicating the importance of renal failure. Elderly survivors present some features of intrinsic mildness but also manifest age-related amelioration of painful crises and falling haemoglobin levels from progressive renal damage.},
 address = {England},
 article-pii = {CLH1089},
 author = {Serjeant, G. R. and Serjeant, B. E. and Mason, K. P. and Hambleton, I. R. and Fisher, C. and Higgs, D. R.},
 completed = {20100115},
 doi = {10.1111/j.1751-553X.2008.01089.x},
 electronic-issn = {1751-553X},
 electronic-publication = {20080717},
 grantno = {MC_U137961144/Medical Research Council/United Kingdom},
 history = {2008/07/23 09:00 [entrez]},
 issue = {6},
 journal = {International journal of laboratory hematology},
 keywords = {Aged, Aged, 80 and over, *Anemia, Sickle Cell/complications/genetics/mortality, Female, Fetal Hemoglobin, Homozygote, Humans, Jamaica/epidemiology, Longitudinal Studies, Male, Pregnancy, Pregnancy Complications, Hematologic, Retrospective Studies, beta-Globins/genetics},
 language = {eng},
 linking-issn = {1751-5521},
 location-id = {10.1111/j.1751-553X.2008.01089.x [doi]},
 month = {Dec},
 nlm-unique-id = {101300213},
 owner = {NLM},
 pages = {585-96},
 publication-status = {ppublish},
 registry-number = {9034-63-3 (Fetal Hemoglobin)},
 revised = {20170922},
 source = {Int J Lab Hematol. 2009 Dec;31(6):585-96. doi: 10.1111/j.1751-553X.2008.01089.x. Epub 2008 Jul 17.},
 status = {MEDLINE},
 subset = {IM},
 title = {The changing face of homozygous sickle cell disease: 102 patients over 60 years.},
 title-abbreviation = {Int J Lab Hematol},
 volume = {31},
 year = {2009}
}


text:
@misc{huang2021method,
 author = {Huang, Pengda and Chen, Hao and Tarver, Chance and Ng, Boon Loong and Chandrasekhar, Vikram and Zhang, Jianzhong},
 month = {June~8},
 note = {US Patent 11,032,717},
 title = {Method and apparatus for improving coexistence performance by measurements in wireless communication systems},
 year = {2021}
}


text:
BINLOCATION  = "${S}/gfx_rel_es3.x"
BINLOCATION_omap3  = "${S}/gfx_rel_es3.x"
BINLOCATION_ti816x = "${S}/gfx_rel_es6.x"

ES2LOCATION = "${S}/gfx_rel_es2.x"
ES3LOCATION = "${S}/gfx_rel_es3.x"
ES5LOCATION = "${S}/gfx_rel_es5.x"
ES6LOCATION = "${S}/gfx_rel_es6.x"

require libgles-omap3.inc

# download required binary distribution from:
# http://software-dl.ti.com/dsps/dsps_public_sw/sdo_sb/targetcontent/gfxsdk/latest/index_FDS.html
# see libgles-omap3.inc for detailed installation instructions

SGXPV = "4_03_00_02"
IMGPV = "1.6.16.3977"
SDKNAME = "Graphics_SDK_${SGXPV}"
BINFILE = "Graphics_SDK_setuplinux_${SGXPV}.bin"

SRC_URI += " file://fix-SGX-demos.patch;patch=0 "

SRC_URI[md5sum] = "ff8c1f2b8e4cb42f4ced6a613b081ada"
SRC_URI[sha256sum] = "cdb0bd3964e107733d632aa8224e0537b05c1ffac34befc036423458c8d75255"

repository: jjtt/OpenEmbedded-Archos

repo_name: jjtt/OpenEmbedded-Archos

extension: bb


text:
SUMMARY = "C/C++ port of the Sass CSS precompiler"
HOMEPAGE = "http://sass-lang.com/libsass"
LICENSE = "MIT"
LIC_FILES_CHKSUM = "file://COPYING;md5=8f34396ca205f5e119ee77aae91fa27d"

inherit autotools

SRC_URI = "git://github.com/sass/libsass.git;branch=master;protocol=https"
SRCREV = "f6afdbb9288d20d1257122e71d88e53348a53af3"
PV = "3.6.5"

S = "${WORKDIR}/git"

BBCLASSEXTEND = "native"

repository: openembedded/meta-openembedded

repo_name: openembedded/meta-openembedded

gha_license_id: MIT

gha_language: BitBake


text:
@article{zhu2018bayesian,
 author = {Zhu, Tingting and Johnson, Alistair E and Yang, Yang and Clifford, Gari D and Clifton, David A},
 author+an = {2=highlight},
 journal = {Physiological measurement},
 publisher = {IOP Publishing},
 title = {Bayesian fusion of physiological measurements using a signal quality extension},
 year = {2018}
}