bluuebunny/crossref_metadata_2025 huggingface dataset:
A Generalized Genetic Algorithm-Based Solver for Very Large Jigsaw Puzzles of Complex Types
Authors: Sholomon Dror , David Omid , Netanyahu Nathan
Published: June 2022

In this paper we introduce new types of square-piece jigsaw puzzles, where in addition to the unknown location and orientation of each piece, a piece might also need to be flipped. These puzzles, which are associated with a number of real world problems, are considerably harder, from a computational standpoint. Specifically, we present a novel generalized genetic algorithm (GA)-based solver that can handle puzzle pieces of unknown location and orientation (Type 2 puzzles) and (two-sided) puzzle pieces of unknown location, orientation, and face (Type 4 puzzles). To the best of our knowledge, our solver provides a new state-of-the-art, solving previously attempted puzzles faster and far more accurately, handling puzzle sizes that have never been attempted before, and assembling the newly introduced two-sided puzzles automatically and effectively. This paper also presents, among other results, the most extensive set of experimental results, compiled as of yet, on Type 2 puzzles.
Predictive Models for Determining If and When to Display Online Lead Forms
Authors: Chan Timothy
Published: June 2022

This paper will demonstrate a machine learning application for predicting positive lead conversion events on the Edmunds.com website, an American destination for car shopping. A positive conversion event occurs when a user fills out and submits a lead form interstitial. We used machine learning to identify which users might want to fill out lead forms, and where in their sessions to present the interstitials. There are several factors that make these predictions difficult, such as (a) far more negative than positive responses (b) seasonality effects due to car sales events near holidays, which require the model to be easily tunable and (c) the need for computationally fast predictions for real-time decision-making in order to minimize any impact on the website’s usability. Rather than develop a single highly complex model, we used an ensemble of three simple models: Naive Bayes, Markov Chain, and Vowpal Wabbit. The ensemble generated significant lift over random predictions and demonstrated comparable accuracy to an external consulting company’s model.
CiteSeerX: AI in a Digital Library Search Engine
Authors: Wu Jian , Kyle Williams Kyle Williams , Chen Hung-Hsuan , Khabsa Madian , Caragea Cornelia , Ororbia Alexander , Jordan Douglas , Giles C.
Published: June 2022

CiteSeerX is a digital library search engine that provides access to more than 4 million academic documents with nearly a million users and millions of hits per day. Artificial intelligence (AI) technologies are used in many components of CiteSeerX e.g. to accurately extract metadata, intelligently crawl the web, and ingest documents. We present key AI technologies used in the following components: document classification and deduplication, document and citation clustering, automatic metadata extraction and indexing, and author disambiguation. These AI technologies have been developed by CiteSeerX group members over the past 5–6 years. We also show the usage status, payoff, development challenges, main design concepts, and deployment and maintenance requirements. While it is challenging to rebuild a system like CiteSeerX from scratch, many of these AI technologies are transferable to other digital libraries and/or search engines.
AI-MIX: Using Automated Planning to Steer Human Workers Towards Better Crowdsourced Plans
Authors: Manikonda Lydia , Chakraborti Tathagata , De Sushovan , Talamadupula Kartik , Kambhampati Subbarao
Published: June 2022

One subclass of human computation applications are those directed at tasks that involve planning (e.g. tour planning) and scheduling (e.g. conference scheduling). Interestingly, work on these systems shows that even primitive forms of automated oversight on the human contributors helps in significantly improving the effectiveness of the humans/crowd. In this paper, we argue that the automated oversight used in these systems can be viewed as a primitive automated planner, and that there are several opportunities for more sophisticated automated planning in effectively steering the crowd. Straightforward adaptation of current planning technology is however hampered by the mismatch between the capabilities of human workers and automated planners. We identify and partially address two important challenges that need to be overcome before such adaptation of planning technology can occur: (i) interpreting inputs of the human workers (and the requester) and (ii) steering or critiquing plans produced by the human workers, armed only with incomplete domain and preference models. To these ends, we describe the implementation of AI-MIX, a tour plan generation system that uses automated checks and alerts to improve the quality of plans created by human workers; and present a preliminary evaluation of the effectiveness of steering provided by automated planning.
StrokeBank: Automating Personalized Chinese Handwriting Generation
Authors: Zong Alfred , Zhu Yuke
Published: June 2022

Machine learning techniques have been successfully applied to Chinese character recognition; nonetheless, automatic generation of stylized Chinese handwriting remains a challenge. In this paper, we propose StrokeBank, a novel approach to automating personalized Chinese handwriting generation. We use a semi-supervised algorithm to construct a dictionary of component mappings from a small seeding set. Unlike previous work, our approach does not require human supervision in stroke extraction or knowledge of the structure of Chinese characters. This dictionary is used to generate handwriting that preserves stylistic variations, including cursiveness and spatial layout of strokes. We demonstrate the effectiveness of our model by a survey-based evaluation. The results show that our generated characters are nearly indistinguishable from ground truth handwritings.
Are Features Equally Representative? A Feature-Centric Recommendation
Authors: Zhang Chenyi , Wang Ke , Lim Ee-peng , Xu Qinneng , Sun Jianling , Yu Hongkun
Published: June 2022

Typically a user prefers an item (e.g., a movie) because she likes certain features of the item (e.g., director, genre, producer). This observation motivates us to consider a feature-centric recommendation approach to item recommendation: instead of directly predicting the rating on items, we predict the rating on the features of items, and use such ratings to derive the rating on an item. This approach offers several advantages over the traditional item-centric approach: it incorporates more information about why a user chooses an item, it generalizes better due to the denser feature rating data, it explains the prediction of item ratings through the predicted feature ratings. Another contribution is turning a principled item-centric solution into a feature-centric solution, instead of inventing a new algorithm that is feature-centric. This approach maximally leverages previous research. We demonstrate this approach by turning the traditional item-centric latent factor model into a feature-centric solution and demonstrate its superiority over item-centric approaches.
VELDA: Relating an Image Tweet’s Text and Images
Authors: Chen Tao , SalahEldeen Hany , He Xiangnan , Kan Min-Yen , Lu Dongyuan
Published: June 2022

Image tweets are becoming a prevalent form of socialmedia, but little is known about their content — textualand visual — and the relationship between the two mediums.Our analysis of image tweets shows that while visualelements certainly play a large role in image-text relationships, other factors such as emotional elements, also factor into the relationship. We develop Visual-Emotional LDA (VELDA), a novel topic model to capturethe image-text correlation from multiple perspectives (namely, visual and emotional). Experiments on real-world image tweets in both Englishand Chinese and other user generated content, show that VELDA significantly outperforms existingmethods on cross-modality image retrieval. Even in other domains where emotion does not factor in imagechoice directly, our VELDA model demonstrates good generalization ability, achieving higher fidelity modeling of such multimedia documents.
Will You "Reconsume" the Near Past? Fast Prediction on Short-Term Reconsumption Behaviors
Authors: Chen Jun , Wang Chaokun , Wang Jianmin
Published: June 2022

The short-term reconsumption behaviors, i.e. “reconsume” the near past, account for a large proportion of people’s activities every day and everywhere. In this paper, we firstly derived four generic features which influence people’s short-term reconsumption behaviors. These features were extracted with respect to different roles in the process of reconsumption behaviors, i.e. users, items and interactions. Then, we brought forward two fast algorithms with the linear and the quadratic kernels to predict whether a user will perform a short-term reconsumption at a specific time given the context. The experimental results show that our proposed algorithms are more accurate in the prediction tasks compared with the baselines. Meanwhile, the time complexity of online prediction of our algorithms is O(1), which enables fast prediction in real-world scenarios. The prediction contributes to more intelligent decision-making, e.g. potential revisited customer identification, personalized recommendation, and information re-finding.
Effectively Predicting Whether and When a Topic Will Become Prevalent in a Social Network
Authors: Liu Weiwei , Deng Zhi-Hong , Gong Xiuwen , Jiang Frank , Tsang Ivor
Published: June 2022

Effective forecasting of future prevalent topics plays animportant role in social network business development.It involves two challenging aspects: predicting whethera topic will become prevalent, and when. This cannotbe directly handled by the existing algorithms in topicmodeling, item recommendation and action forecasting.The classic forecasting framework based on time seriesmodels may be able to predict a hot topic when a seriesof periodical changes to user-addressed frequency in asystematic way. However, the frequency of topics discussedby users often changes irregularly in social networks.In this paper, a generic probabilistic frameworkis proposed for hot topic prediction, and machine learningmethods are explored to predict hot topic patterns.Two effective models, PreWHether and PreWHen, areintroduced to predict whether and when a topic will becomeprevalent. In the PreWHether model, we simulatethe constructed features of previously observed frequencychanges for better prediction. In the PreWHen model,distributions of time intervals associated with the emergenceto prevalence of a topic are modeled. Extensiveexperiments on real datasets demonstrate that ourmethod outperforms the baselines and generates moreeffective predictions.
Modeling with Node Degree Preservation Can Accurately Find Communities
Authors: Jin Di , Chen Zheng , He Dongxiao , Zhang Weixiong
Published: June 2022

An important problem in analyzing complex networks is discovery of modular or community structures embedded in the networks. Although being promising for identifying network communities, the popular stochastic models often do not preserve node degrees, thus reducing their representation power and applicability to real-world networks. Here we address this critical problem. Instead of using a blockmodel, we adopted a random-graph null model to faithfully capture community structures by preserving in the model the expected node degrees. The new model, learned using nonnegative matrix factorization, is more accurate and robust in representing community structures than the existing methods. Our results from extensive experiments on synthetic benchmarks and real-world networks show the superior performance of the new method over the existing methods in detecting both disjoint and overlapping communities.
Efficient Computation of Semivalues for Game-Theoretic Network Centrality
Authors: Szczepański Piotr , Tarkowski Mateusz , Michalak Tomasz , Harrenstein Paul , Wooldridge Michael
Published: June 2022

Solution concepts from cooperative game theory, such as the Shapley value or the Banzhaf index, have recently been advocated as interesting extensions of standard measures of node centrality in networks. While this direction of research is promising, the computation of game-theoretic centrality can be challenging. In an attempt to address the computational issues of game-theoretic network centrality, we present a generic framework for constructing game-theoretic network centralities. We prove that all extensions that can be expressed in this framework are computable in polynomial time. Using our framework, we present the first game-theoretic extensions of weighted and normalized degree centralities, impact factor centrality,distance-scaled and normalized betweenness centrality,and closeness and normalized closeness centralities.
Influence-Driven Model for Time Series Prediction from Partial Observations
Authors: Aman Saima , Chelmis Charalampos , Prasanna Viktor
Published: June 2022

Applications in sustainability domains such as in energy, transportation, and natural resource and environment monitoring, increasingly use sensors for collecting data and sending it back to centrally located processing nodes. While data can usually be collected by the sensors at a very high speed, in many cases, it can not be sent back to central nodes at a frequency that is required for fast and real-time modeling and decision-making. This may be due to physical limitations of the transmission networks, or due to consumers limiting frequent transmission of data from sensors located at their premises for security and privacy concerns. We propose a novel solution to the problem of making short term predictions in absence of real-time data from sensors. A key implication of our work is that by using real-time data from only a small subset of influential sensors, we are able to make predictions for all sen- sors. We evaluated our approach with a large real-world electricity consumption data collected from smart meters in Los Angeles and the results show that between prediction horizons of 2 to 8 hours, despite lack of real time data, our influence model outperforms the baseline model that uses real-time data. Also, when using partial real-time data from only ≈ 7% influential smart meters, we witness prediction error increase by only ≈ 0.5% over the baseline, thus demonstrating the usefulness of our method for practical scenarios.
Risk Based Optimization for Improving Emergency Medical Systems
Authors: Saisubramanian Sandhya , Varakantham Pradeep , Lau Hoong Chuin
Published: June 2022

In emergency medical systems, arriving at the incident locationa few seconds early can save a human life. Thus, this paper is motivated by the need to reduce the response time– time taken to arrive at the incident location after receivingthe emergency call — of Emergency Response Vehicles, ERVs(ex: ambulances, fire rescue vehicles) for as many requests as possible. We expect to achieve this primarily by positioning the ”right” number of ERVs at the ”right” places and at the ”right” times. Given the exponentially large action space(with respect to number of ERVs and their placement) and the stochasticity in location and timing of emergency incidents,this problem is computationally challenging. To that end, ourcontributions building on existing data-driven approaches are three fold:1. Based on real world evaluation metrics, we provide a riskbased optimization criterion to learn from past incident data. Instead of minimizing expected response time, we minimize the largest value of response time such that the risk of finding requests that have a higher value is bounded(ex: Only 10% of requests should have a response time greater than 8 minutes).2. We develop a mixed integer linear optimization formulation to learn and compute an allocation from a set of inputrequests while considering the risk criterion.3. To allow for ”live” reallocation of ambulances, we provide a decomposition method based on Lagrangian Relaxation to significantly reduce the run-time of the optimization formulation.Finally, we provide an exhaustive evaluation on real-world datasets from two asian cities that demonstrates the improvement provided by our approach over current practice and the best known approach from literature.
Sharing Rides with Friends: A Coalition Formation Algorithm for Ridesharing
Authors: Bistaffa Filippo , Farinelli Alessandro , Ramchurn Sarvapali
Published: June 2022

We consider the Social Ridesharing (SR) problem, where a set of commuters, connected through a social network, arrange one-time rides at short notice. In particular, we focus on the associated optimisation problem of forming cars to minimise the travel cost of the overall system modelling such problem as a graph constrained coalition formation (GCCF) problem, where the set of feasible coalitions is restricted by a graph (i.e., the social network). Moreover, we significantly extend the state of the art algorithm for GCCF, i.e., the CFSS algorithm, to solve our GCCF model of the SR problem. Our empirical evaluation uses a real dataset for both spatial (GeoLife) and social data (Twitter), to validate the applicability of our approach in a realistic application scenario. Empirical results show that our approach computes optimal solutions for systems of medium scale (up to 100 agents) providing significant cost reductions (up to -36.22%). Moreover, we can provide approximate solutions for very large systems (i.e., up to 2000 agents) and good quality guarantees (i.e., with an approximation ratio of 1.41 in the worst case) within minutes (i.e., 100 seconds).
HVAC-Aware Occupancy Scheduling (Extended Abstract)
Authors: Lim Boon-Ping
Published: June 2022

My research focuses on developing innovative ways to control Heating, Ventilation, and Air Conditioning (HVAC) and schedule occupancy flows in smart buildings to reduce our ecological footprint (and energy bills). We look at the potential for integrating building operations with room booking and meeting scheduling. Specifically, we improve on the effectiveness of energy-aware room-booking and occupancy scheduling approaches, by allowing the scheduling decisions to rely on an explicit model of the building's occupancy-based HVAC control. From computational standpoint, this is a challenging topic as HVAC models are inherently non-linear non-convex, and occupancy scheduling models additionally introduce discrete variables capturing the time slot and location at which each activity is scheduled. The mechanism needs to tradeoff minimizing energy cost against addressing occupancy thermal comfort and control feasibility in a highly dynamic and uncertain system.
Multivariate Conditional Anomaly Detection and Its Clinical Application
Authors: Hong Charmgil , Hauskrecht Milos
Published: June 2022

This paper overviews the background, goals, past achievements and future directions of our research that aims to build a multivariate conditional anomaly detection framework for the clinical application.
The Network Data Repository with Interactive Graph Analytics and Visualization
Authors: Rossi Ryan , Ahmed Nesreen
Published: June 2022

NetworkRepository (NR) is the first interactive data repository with a web-based platform for visual interactive analytics. Unlike other data repositories (e.g., UCI ML Data Repository, and SNAP), the network data repository (networkrepository.com) allows users to not only download, but to interactively analyze and visualize such data using our web-based interactive graph analytics platform. Users can in real-time analyze, visualize, compare, and explore data along many different dimensions. The aim of NR is to make it easy to discover key insights into the data extremely fast with little effort while also providing a medium for users to share data, visualizations, and insights. Other key factors that differentiate NR from the current data repositories is the number of graph datasets, their size, and variety. While other data repositories are static, they also lack a means for users to collaboratively discuss a particular dataset, corrections, or challenges with using the data for certain applications. In contrast, NR incorporates many social and collaborative aspects that facilitate scientific research, e.g., users can discuss each graph, post observations, and visualizations.
Exploring Information Asymmetry in Two-Stage Security Games
Authors: Xu Haifeng , Rabinovich Zinovi , Dughmi Shaddin , Tambe Milind
Published: June 2022

Stackelberg security games have been widely deployed to protect real-word assets. The main solution concept there is the Strong Stackelberg Equilibrium (SSE), which optimizes the defender's random allocation of limited security resources. However, solely deploying the SSE mixed strategy has limitations. In the extreme case, there are security games where the defender is able to defend all the assets ``almost perfectly" at the SSE, but she still sustains significant loss. In this paper, we propose an approach for improving the defender's utility in such scenarios. Perhaps surprisingly, our approach is to strategically reveal to the attacker information about the sampled pure strategy. Specifically, we propose a two-stage security game model, where in the first stage the defender allocates resources and the attacker selects a target to attack, and in the second stage the defender strategically reveals local information about that target, potentially deterring the attacker's attack plan. We then study how the defender can play optimally in both stages. We show, theoretically and experimentally, that the two-stage security game model allows the defender to gain strictly better utility than SSE.
Incentives for Subjective Evaluations with Private Beliefs
Authors: Radanovic Goran , Faltings Boi
Published: June 2022

The modern web critically depends on aggregation of information from self-interested agents, for example opinion polls, product ratings, or crowdsourcing. We consider a setting where multiple objects (questions, products, tasks) are evaluated by a group of agents. We first construct a minimal peer prediction mechanism that elicits honest evaluations from a homogeneous population of agents with different private beliefs. Second, we show that it is impossible to strictly elicit honest evaluations from a heterogeneous group of agents with different private beliefs. Nevertheless, we provide a modified version of a divergence-based Bayesian Truth Serum that incentivizes agents to report consistently, making truthful reporting a weak equilibrium of the mechanism.
On a Competitive Secretary Problem
Authors: Karlin Anna , Lei Eric
Published: June 2022

Consider a scenario in which there are multiple employers competing to hire the best possible employee. How does the competition between the employers affect their hiring strategies or their ability to hire one of the best possible candidates? In this paper, we address this question by studying a generalization of the classical secretary problem from optimal stopping theory: a set of ranked employers compete to hire from the same random stream of employees, and each employer wishes to hire the best candidate in the bunch. We show how to derive subgame-perfect Nash equilibrium strategies in this game and analyze the impact the competition has on the quality of the hires as a function of the rank of the employer. We present numerical results from simulations of these strategies.
Security Games with Protection Externalities
Authors: Gan Jiarui , An Bo , Vorobeychik Yevgeniy
Published: June 2022

Stackelberg security games have been widely deployed in recent years to schedule security resources. An assumption in most existing security game models is that one security resource assigned to a target only protects that target. However, in many important real-world security scenarios, when a resource is assigned to a target, it exhibits protection externalities: that is, it also protects other “neighbouring” targets. We investigate such Security Games with Protection Externalities (SPEs). First, we demonstrate that computing a strong Stackelberg equilibrium for an SPE is NP-hard, in contrast with traditional Stackelberg security games which can be solved in polynomial time. On the positive side, we propose a novel column generation based approach—CLASPE—to solve SPEs. CLASPE features the following novelties: 1) a novel mixed-integer linear programming formulation for the slave problem; 2) an extended greedy approach with a constant-factor approximation ratio to speed up the slave problem; and 3) a linear-scale linear programming that efficiently calculates the upper bounds of target-defined subproblems for pruning. Our experimental evaluation demonstrates that CLASPE enable us to scale to realistic-sized SPE problem instances.
Novel Mechanisms for Online Crowdsourcing with Unreliable, Strategic Agents
Authors: Chandra Praphul , Narahari Yadati , Mandal Debmalya , Dey Prasenjit
Published: June 2022

Motivated by current day crowdsourcing platforms and emergence of online labor markets, this work addresses the problem of task allocation and payment decisions when unreliable and strategic workers arrive over time to work on tasks which must be completed within a deadline. We consider the following scenario: a requester has a set of tasks that must be completed before a deadline; agents (aka crowd workers) arrive over time and it is required to make sequential decisions regarding task allocation and pricing. Agents may have different costs for providing service and these costs are private information of the agents. We assume that agents are not strategic about their arrival times but could be strategic about their costs of service. In addition, agents could be unreliable in the sense of not being able to complete the assigned tasks within the allocated time; these tasks must then be reallocated to other agents to ensure ontime completion of the set of tasks by the deadline. For this setting, we propose two mechanisms: a DPM (DynamicPrice Mechanism) and an ABM (Auction Based Mechanism). Both mechanisms are dominant strategy incentive compatible, budget feasible, and also satisfy ex-post individual rationality for agents who complete the allocated tasks. These mechanisms can be implemented in current day crowdsourcing platforms with minimal changes to the current interaction model.
Recursive Best-First Search with Bounded Overhead
Authors: Hatem Matthew , Kiesel Scott , Ruml Wheeler
Published: June 2022

There are two major paradigms for linear-space heuristic search: iterative deepening (IDA*) and recursive best-first search (RBFS). While the node regeneration overhead of IDA* is easily characterized in terms of the heuristic branching factor, the overhead of RBFS depends on how widely the promising nodes are separated in the search tree, and is harder to anticipate. In this paper, we present two simple techniques for improving the performance of RBFS while maintaining its advantages over IDA*. While these techniques work well in practice, they do not provide any theoretical bounds on the amount of regeneration overhead. To this end, we introduce RBFScr, the first method for provably bounding the regeneration overhead of RBFS. We show empirically that this improves its performance in several domains, both for optimal and suboptimal search, and also yields a better linear-space anytime heuristic search. RBFScr is the first linear space best-first search robust enough to solve a variety of domains with varying operator costs.
Optimal Column Subset Selection by A-Star Search
Authors: Arai Hiromasa , Maung Crystal , Schweitzer Haim
Published: June 2022

Approximating a matrix by a small subset of its columns is a known problem in numerical linear algebra. Algorithms that address this problem have been used in areas which include, among others, sparse approximation, unsupervised feature selection, data mining, and knowledge representation. Such algorithms were investigated since the 1960's, with recent results that use randomization. The problem is believed to be NP-Hard, and to the best of our knowledge there are no previously published algorithms aimed at computing optimal solutions. We show how to model the problem as a graph search, and propose a heuristic based on eigenvalues of related matrices. Applying the A* search strategy with this heuristic is guaranteed to find the optimal solution. Experimental results on common datasets show that the proposed algorithm can effectively select columns from moderate size matrices, typically improving by orders of magnitude the run time of exhaustive search. We also show how to combine the proposed algorithm with other non-optimal (but much faster) algorithms in a ``two stage'' framework, which is guaranteed to improve the accuracy of the other algorithms.
Improved Local Search for Binary Matrix Factorization
Authors: Mirisaee Seyed Hamid , Gaussier Eric , Termier Alexandre
Published: June 2022

Rank K Binary Matrix Factorization (BMF) approximates a binary matrix by the product of two binary matrices of lower rank, K, using either L1 or L2 norm. In this paper, we first show that the BMF with L2 norm can be reformulated as an Unconstrained Binary Quadratic Programming (UBQP) problem. We then review several local search strategies that can be used to improve the BMF solutions obtained by previously proposed methods, before introducing a new local search dedicated to the BMF problem. We show in particular that the proposed solution is in general faster than the previously proposed ones. We then assess its behavior on several collections and methods and show that it significantly improves methods targeting the L2 norms on all the datasets considered; for the L1 norm, the improvement is also significant for real, structured datasets and for the BMF problem without the binary reconstruction constraint.
BDD-Constrained Search: A Unified Approach to Constrained Shortest Path Problems
Authors: Nishino Masaaki , Yasuda Norihito , Minato Shin-ichi , Nagata Masaaki
Published: June 2022

Dynamic programming (DP) is a fundamental tool used to obtain exact, optimal solutions for many combinatorial optimization problems. Among these problems, important ones including the knapsack problems and the computation of edit distances between string pairs can be solved with a kind of DP that corresponds to solving the shortest path problem on a directed acyclic graph (DAG). These problems can be solved efficiently with DP, however, in practical situations, we want to solve the customized problems made by adding logical constraints to the original problems. Developing an algorithm specifically for each combination of a problem and a constraint set is unrealistic. The proposed method, BDD-Constrained Search (BCS), exploits a Binary Decision Diagram (BDD) that represents the logical constraints in combination with the DAG that represents the problem. The BCS runs DP on the DAG while using the BDD to check the equivalence and the validity of intermediate solutions to efficiently solve the problem. The important feature of BCS is that it can be applied to problems with various types of logical constraints in a unified way once we represent the constraints as a BDD. We give a theoretical analysis on the time complexity of BCS and also conduct experiments to compare its performance to that of a state-of-the-art integer linear programming solver.
Toward Mobile Robots Reasoning Like Humans
Authors: Oh Jean , Suppé Arne , Duvallet Felix , Boularias Abdeslam , Navarro-Serment Luis , Hebert Martial , Stentz Anthony , Vinokurov Jerry , Romero Oscar , Lebiere Christian , Dean Robert
Published: June 2022

Robots are increasingly becoming key players in human-robot teams. To become effective teammates, robots must possess profound understanding of an environment, be able to reason about the desired commands and goals within a specific context, and be able to communicate with human teammates in a clear and natural way. To address these challenges, we have developed an intelligence architecture that combines cognitive components to carry out high-level cognitive tasks, semantic perception to label regions in the world, and a natural language component to reason about the command and its relationship to the objects in the world. This paper describes recent developments using this architecture on a fielded mobile robot platform operating in unknown urban environments. We report a summary of extensive outdoor experiments; the results suggest that a multidisciplinary approach to robotics has the potential to create competent human-robot teams.
CORPP: Commonsense Reasoning and Probabilistic Planning, as Applied to Dialog with a Mobile Robot
Authors: Zhang Shiqi , Stone Peter
Published: June 2022

In order to be fully robust and responsive to a dynamically changing real-world environment, intelligent robots will need to engage in a variety of simultaneous reasoning modalities. In particular, in this paper we consider their needs to i) reason with commonsense knowledge, ii) model their nondeterministic action outcomes and partial observability, and iii) plan toward maximizing long-term rewards. On one hand, Answer Set Programming (ASP) is good at representing and reasoning with commonsense and default knowledge, but is ill-equipped to plan under probabilistic uncertainty. On the other hand, Partially Observable Markov Decision Processes(POMDPs) are strong at planning under uncertainty toward maximizing long-term rewards, but are not designed to incorporate commonsense knowledge and inference. This paper introduces the CORPP algorithm which combines P-log,a probabilistic extension of ASP, with POMDPs to integrate commonsense reasoning with planning under uncertainty.Our approach is fully implemented and tested on a shopping request identification problem both in simulation and on a real robot. Compared with existing approaches using P-log or POMDPs individually, we observe significant improvements in both efficiency and accuracy.
Grounded Fixpoints
Authors: Bogaerts Bart , Vennekens Joost , Denecker Marc
Published: June 2022

Algebraical fixpoint theory is an invaluable instrument for studying semantics of logics. For example, all major semantics of logic programming, autoepistemic logic, default logic and more recently, abstract argumentation have been shown to be induced by the different types of fixpoints defined in approximation fixpoint theory (AFT). In this paper, we add a new type of fixpoint to AFT: a grounded fixpoint of lattice operator O : L → L is defined as a lattice element x ∈ L such that O(x) = x and for all v ∈ L such that O(v ∧ x) ≤ v, it holds that x ≤ v. On the algebraical level, we show that all grounded fixpoints are minimal fixpoints approximated by the well-founded fixpoint and that all stable fixpoints are grounded. On the logical level, grounded fixpoints provide a new mathematically simple and compact type of semantics for any logic with a (possibly non-monotone) semantic operator. We explain the intuition underlying this semantics in the context of logic programming by pointing out that grounded fixpoints of the immediate consequence operator are interpretations that have no non-trivial unfounded sets. We also analyse the complexity of the induced semantics. Summarised, grounded fixpoint semantics is a new, probably the simplest and most compact, element in the family of semantics that capture basic intuitions and principles of various non-monotonic logics.
Structured Embedding via Pairwise Relations and Long-Range Interactions in Knowledge Base
Authors: Wu Fei , Song Jun , Yang Yi , Li Xi , Zhang Zhongfei , Zhuang Yueting
Published: June 2022

We consider the problem of embedding entities and relations of knowledge bases into low-dimensional continuous vector spaces (distributed representations). Unlike most existing approaches, which are primarily efficient for modelling pairwise relations between entities, we attempt to explicitly model both pairwise relations and long-range interactions between entities, by interpreting them as linear operators on the low-dimensional embeddings of the entities. Therefore, in this paper we introduces Path-Ranking to capture the long-range interactions of knowledge graph and at the same time preserve the pairwise relations of knowledge graph; we call it 'structured embedding via pairwise relation and long-range interactions' (referred to as SePLi). Comparing with the-state-of-the-art models, SePLi achieves better performances of embeddings.
Towards Tractable and Practical ABox Abduction over Inconsistent Description Logic Ontologies
Authors: Du Jianfeng , Wang Kewen , Shen Yi-Dong
Published: June 2022

ABox abduction plays an important role in reasoning over description logic (DL) ontologies. However, it does not work with inconsistent DL ontologies. To tackle this problem while achieving tractability, we generalize ABox abduction from the classical semantics to an inconsistency-tolerant semantics, namely the Intersection ABox Repair (IAR) semantics, and propose the notion of IAR-explanations in inconsistent DL ontologies. We show that computing all minimal IAR-explanations is tractable in data complexity for first-order rewritable ontologies. However, the computational method may still not be practical due to a possibly large number of minimal IAR-explanations. Hence we propose to use preference information to reduce the number of explanations to be computed.
XPath for DL Ontologies
Authors: Kostylev Egor , Reutter Juan , Vrgoc Domagoj
Published: June 2022

Applications of description logics (DLs) such as ontology-based data access (OBDA) require understanding of how to pose database queries over DL knowledge bases. While there have been many studies regarding traditional relational query formalisms such as conjunctive queries and their extensions, little attention has been paid to graph database queries, despite the fact that graph databases have essentially the same structure as knowledge bases. In particular, not much is known about the interplay between DLs and XPath. The latter is a powerful formalism for querying semistructured data: it is in the core of most practical query languages for XML trees, and it is also gaining popularity in theory and practice of graph databases. In this paper we make a step towards coupling knowledge bases and graph databases by studying how to answer powerful XPath-style queries over simple DLs like DL-Lite and EL. We start with adapting the definition of XPath to the DL context, and then proceed to study the complexity of evaluating XPath queries over knowledge bases. Results show that, while query answering is undecidable for the full XPath, by carefully tuning the shape of negation allowed in the queries we can arrive at XPath fragments that have a potential to be used in practice.
A Syntax-Independent Approach to Forgetting in Disjunctive Logic Programs
Authors: Delgrande James , Wang Kewen
Published: June 2022

In this paper, we present an approach to forgetting in disjunctive logic programs, where forgetting an atom from a program amounts to a reduction in the signature of that program. Notably, the approach is syntax-independent, so that if two programs are strongly equivalent, then the result of forgetting a given atom in each program is also strongly equivalent. Our central definition of forgetting is abstract: forgetting an atom from program P is characterised by the set of those SE consequences of P that do not mention the atom to be forgotten. We provide an equivalent, syntactic, characterization in which forgetting an atom p is given by those rules in the program that do not mention p, together with rules obtained by a single inference step from those rules that do mention p. Forgetting is shown to have appropriate properties; in particular, answer sets are preserved in forgetting an atom. As well, forgetting an atom via the syntactic characterization results in a modest (at worst quadratic) blowup in the program size. Finally, we provide a prototype implementation of this approach to forgetting.
Existential Rule Languages with Finite Chase: Complexity and Expressiveness
Authors: Zhang Heng , Zhang Yan , You Jia-Huai
Published: June 2022

Finite chase, or alternatively chase termination, is an important condition to ensure the decidability of existential rule languages. In the past few years, a number of rule languages with finite chase have been studied. In this work, we propose a novel approach for classifying the rule languages with finite chase. Using this approach, a family of decidable rule languages, which extend the existing languages with the finite chase property, are naturally defined. We then study the complexity of these languages. Although all of them are tractable for data complexity, we show that their combined complexity can be arbitrarily high. Furthermore, we prove that all the rule languages with finite chase that extend the weakly acyclic language are of the same expressiveness as the weakly acyclic one, while rule languages with higher combined complexity are in general more succinct than those with lower combined complexity.
Incremental Update of Datalog Materialisation: the Backward/Forward Algorithm
Authors: Motik Boris , Nenov Yavor , Piro Robert , Horrocks Ian
Published: June 2022

Datalog-based systems often materialise all consequences of a datalog program and the data, allowing users' queries to be evaluated directly in the materialisation. This process, however, can be computationally intensive, so most systems update the materialisation incrementally when input data changes. We argue that existing solutions, such as the well-known Delete/Rederive (DRed) algorithm, can be inefficient in cases when facts have many alternate derivations. As a possible remedy, we propose a novel Backward/Forward (B/F) algorithm that tries to reduce the amount of work by a combination of backward and forward chaining. In our evaluation, the B/F algorithm was several orders of magnitude more efficient than the DRed algorithm on some inputs, and it was never significantly less efficient.
Pearl's Causality in a Logical Setting
Authors: Bochman Alexander , Lifschitz Vladimir
Published: June 2022

We provide a logical representation of Pearl's structural causal models in the causal calculus of McCain and Turner (1997) and its first-order generalization by Lifschitz. It will be shown that, under this representation, the nonmonotonic semantics of the causal calculus describes precisely the solutions of the structural equations (the causal worlds of the causal model), while the causal logic from Bochman (2004) is adequate for describing the behavior of causal models under interventions (forming submodels).
A Logic for Reasoning About Game Strategies
Authors: Zhang Dongmo , Thielscher Michael
Published: June 2022

This paper introduces a modal logic for reasoning about game strategies. The logic is based on a variant of the well-known game description language for describing game rules and further extends it with two modalities for reasoning about actions and strategies. We develop an axiomatic system and prove its soundness and completeness with respect to a specific semantics based on the state transition model of games. Interestingly, the completeness proof makes use of forgetting techniques that have been widely used in the KR&R literature. We demonstrate how general game-playing systems can apply the logic to develop game strategies.
How Many Diagnoses Do We Need?
Authors: Stern Roni , Kalech Meir , Rogov Shelly , Feldman Alexander
Published: June 2022

A known limitation of many diagnosis algorithms is that the number of diagnoses they return can be very large. This raises the question of how to use such a large set of diagnoses. For example, presenting hundreds of diagnoses to a human operator (charged with repairing the system) is meaningless. In various settings, including decision support for a human operator and automated troubleshooting processes, it is sufficient to be able to answer a basic diagnostic question: is a given component faulty? We propose a way to aggregate an arbitrarily large set of diagnoses to return an estimate of the likelihood of a given component to be faulty. The resulting mapping of components to their likelihood of being faulty is called the system's health state. We propose two metrics for evaluating the accuracy of a health state and show that an accurate health state can be found without finding all diagnoses. An empirical study explores the question of how many diagnoses are needed to obtain an accurate enough health state, and a simple online stopping criterion is proposed.
An Empirical Study on the Practical Impact of Prior Beliefs over Policy Types
Authors: Albrecht Stefano , Crandall Jacob , Ramamoorthy Subramanian
Published: June 2022

Many multiagent applications require an agent to learn quickly how to interact with previously unknown other agents. To address this problem, researchers have studied learning algorithms which compute posterior beliefs over a hypothesised set of policies, based on the observed actions of the other agents. The posterior belief is complemented by the prior belief, which specifies the subjective likelihood of policies before any actions are observed. In this paper, we present the first comprehensive empirical study on the practical impact of prior beliefs over policies in repeated interactions. We show that prior beliefs can have a significant impact on the long-term performance of such methods, and that the magnitude of the impact depends on the depth of the planning horizon. Moreover, our results demonstrate that automatic methods can be used to compute prior beliefs with consistent performance effects. This indicates that prior beliefs could be eliminated as a manual parameter and instead be computed automatically.
Scalable Planning and Learning for Multiagent POMDPs
Authors: Amato Christopher , Oliehoek Frans
Published: June 2022

Online, sample-based planning algorithms for POMDPs have shown great promise in scaling to problems with large state spaces, but they become intractable for large action and observation spaces. This is particularly problematic in multiagent POMDPs where the action and observation space grows exponentially with the number of agents. To combat this intractability, we propose a novel scalable approach based on sample-based planning and factored value functions that exploits structure present in many multiagent settings. This approach applies not only in the planning case, but also in the Bayesian reinforcement learning setting. Experimental results show that we are able to provide high quality solutions to large multiagent planning and learning problems.
Solving Games with Functional Regret Estimation
Authors: Waugh Kevin , Morrill Dustin , Bagnell James , Bowling Michael
Published: June 2022

We propose a novel online learning method for minimizing regret in large extensive-form games. The approach learns a function approximator online to estimate the regret for choosing a particular action. A no-regret algorithm uses these estimates in place of the true regrets to define a sequence of policies. We prove the approach sound by providing a bound relating the quality of the function approximation and regret of the algorithm. A corollary being that the method is guaranteed to converge to a Nash equilibrium in self-play so long as the regrets are ultimately realizable by the function approximator. Our technique can be understood as a principled generalization of existing work onabstraction in large games; in our work, both the abstraction as well as the equilibrium are learned during self-play. We demonstrate empirically the method achieves higher quality strategies than state-of-the-art abstraction techniques given the same resources.