bluuebunny/crossref_metadata_2025 huggingface dataset:
The Compressed Differential Heuristic
Authors: Goldenberg Meir , Sturtevant Nathan , Felner Ariel , Schaeffer Jonathan
Published: September 2022

The differential heuristic (DH) is an effective memory-based heuristic for explicit state spaces. In this paper we aim to improve its performance and memory usage. We introduce a compression method for DHs which stores only a portion of the original uncompressed DH, while preserving enough information to enable efficient search. Compressed DHs (CDH) are flexible and can be tuned to fit any size of memory, even smaller than the size of the state space. Furthermore, CDHs can be built without the need to create and store the entire uncompressed DH. Experimental results across different domains show that, for a given amount of memory, a CDH significantly outperforms an uncompressed DH.
Heuristic Search for Large Problems With Real Costs
Authors: Hatem Matthew , Burns Ethan , Ruml Wheeler
Published: September 2022

The memory requirements of basic best-first heuristic search algorithms like A* make them infeasible for solving large problems. External disk storage is cheap and plentiful com- pared to the cost of internal RAM. Unfortunately, state-of- the-art external memory search algorithms either rely on brute-force search techniques, such as breadth-first search, or they rely on all node values falling in a narrow range of in- tegers, and thus perform poorly on real-world domains with real-valued costs. We present a new general-purpose algo- rithm, PEDAL, that uses external memory and parallelism to perform a best-first heuristic search capable of solving large problems with real costs. We show theoretically that PEDAL is I/O efficient and empirically that it is both better on a stan- dard unit-cost benchmark, surpassing internal IDA* on the 15-puzzle, and gives far superior performance on problems with real costs.
Contextually-Based Utility: An Appraisal-Based Approach at Modeling Framing and Decisions
Authors: Ito Jonathan , Marsella Stacy
Published: September 2022

Creating accurate computational models of human decision making is a vital step towards the realization of socially intelligent systems capable of both predicting and simulating human behavior. In modeling human decision making, a key factor is the psychological phenomenon known as "framing", in which the preferences of a decision maker change in response to contextual changes in decision problems. Existing approaches treat framing as a one-dimensional contextual influence based on the perception of outcomes as either gains or losses. However, empirical studies have shown that framing effects are much more multifaceted than one-dimensional views of framing suggest. To address this limitation, we propose an integrative approach to modeling framing which combines the psychological principles of cognitive appraisal theories and decision-theoretic notions of utility and probability. We show that this approach allows for both the identification and computation of the salient contextual factors in a decision as well as modeling how they ultimately affect the decision process. Furthermore, we show that our multi-dimensional, appraisal-based approach can account for framing effects identified in the empirical literature which cannot be addressed by one-dimensional theories, thereby promising more accurate models of human behavior.
Deriving a Web-Scale Common Sense Fact Database
Authors: Tandon Niket , De Melo Gerard , Weikum Gerhard
Published: September 2022

The fact that birds have feathers and ice is cold seems trivially true. Yet, most machine-readable sources of knowledge either lack such common sense facts entirely or have only limited coverage. Prior work on automated knowledge base construction has largely focused on relations between named entities and on taxonomic knowledge, while disregarding common sense properties. In this paper, we show how to gather large amounts of common sense facts from Web n-gram data, using seeds from the ConceptNet collection. Our novel contributions include scalable methods for tapping onto Web-scale data and a new scoring model to determine which patterns and facts are most reliable. The experimental results show that this approach extends ConceptNet by many orders of magnitude at comparable levels of precision.
Bounded Forgetting
Authors: Zhou Yi , Zhang Yan
Published: September 2022

The result of forgetting some predicates in a first-order sentence may not exist in the sense that it might not be captured by any first-order sentences. This, indeed, severely restricts the usage of forgetting in applications. To address this issue, we propose a notion called $k$-forgetting, also called bounded forgetting in general, for any fixed number $k$. We present several equivalent characterizations of bounded forgetting and show that the result of bounded forgetting, on one hand, can always be captured by a single first-order sentence, and on the other hand, preserves the information that we are concerned with.
Preferred Explanations: Theory and Generation via Planning
Authors: Sohrabi Shirin , Baier Jorge , McIlraith Sheila
Published: September 2022

In this paper we examine the general problem of generating preferred explanations for observed behavior with respect to a model of the behavior of a dynamical system. This problem arises in a diversity of applications including diagnosis of dynamical systems and activity recognition. We provide a logical characterization of the notion of an explanation. To generate explanations we identify and exploit a correspondence between explanation generation and planning. The determination of good explanations requires additional domain-specific knowledge which we represent as preferences over explanations. The nature of explanations requires us to formulate preferences in a somewhat retrodictive fashion by utilizing Past Linear Temporal Logic. We propose methods for exploiting these somewhat unique preferences effectively within state-of-the-art planners and illustrate the feasibility of generating (preferred) explanations via planning.
Revisiting Semantics for Epistemic Extensions of Description Logics
Authors: Mehdi Anees , Rudolph Sebastian
Published: September 2022

Epistemic extensions of description logics (DLs) have been introduced several years ago in order to enhance expressivity and querying capabilities of these logics by knowledge base introspection. We argue that unintended effects occur when imposing the traditionally employed semantics on the very expressive DLs that underly the OWL 1 and OWL 2 standards. Consequently, we suggest a revised semantics that behaves more intuitively in these cases and coincides with the traditional semantics of less expressive DLs. Moreover, we introduce a way of answering epistemic queries to OWL knowledge bases by a reduction to standard OWL reasoning. We provide an implementation of our approach and present first evaluation results.
Transportability of Causal and Statistical Relations: A Formal Approach
Authors: Pearl Judea , Bareinboim Elias
Published: September 2022

We address the problem of transferring information learned from experiments to a different environment, in which only passive observations can be collected. We introduce a formal representation called "selection diagrams" for expressing knowledge about differences and commonalities between environments and, using this representation, we derive procedures for deciding whether effects in the target environment can be inferred from experiments conducted elsewhere. When the answer is affirmative, the procedures identify the set of experiments and observations that need be conducted to license the transport. We further discuss how transportability analysis can guide the transfer of knowledge in non-experimental learning to minimize re-measurement cost and improve prediction power.
Manipulation of Nanson's and Baldwin's Rules
Authors: Narodytska Nina , Walsh Toby , Xia Lirong
Published: September 2022

Nanson's and Baldwin's voting rules selecta winner by successively eliminatingcandidates with low Borda scores. We showthat these rules have a number of desirablecomputational properties. In particular,with unweighted votes, it isNP-hard to manipulate either rule with one manipulator, whilstwith weighted votes, it isNP-hard to manipulate either rule with a small number ofcandidates and a coalition of manipulators.As only a couple of other voting rulesare known to be NP-hard to manipulatewith a single manipulator, Nanson'sand Baldwin's rules appearto be particularly resistant to manipulation from a theoretical perspective.We also propose a number of approximation methodsfor manipulating these two rules.Experiments demonstrate that both rules areoften difficult to manipulate in practice.These results suggest that elimination stylevoting rules deserve further study.
Quick Polytope Approximation of All Correlated Equilibria in Stochastic Games
Authors: MacDermed Liam , Narayan Karthik , Isbell Charles , Weiss Lora
Published: September 2022

Stochastic or Markov games serve as reasonable models for a variety of domains from biology to computer security, and are appealing due to their versatility. In this paper we address the problem of finding the complete set of correlated equilibria for general-sum stochastic games with perfect information. We present QPACE — an algorithm orders of magnitude more efficient than previous approaches while maintaining a guarantee of convergence and bounded error. Finally, we validate our claims and demonstrate the limits of our algorithm with extensive empirical tests.
Parameterized Complexity of Problems in Coalitional Resource Games
Authors: Chitnis Rajesh , Hajiaghayi MohammadTaghi , Liaghat Vahid
Published: September 2022

Coalition formation is a key topic in multi-agent systems. Coalitions enable agents to achieve goals that they may nothave been able to achieve on their own. Previous work hasshown problems in coalition games to be computationally hard. Wooldridge and Dunne (Artifi. Intell. 2006) studied the classical computational complexity of several natural decision problems in Coalitional Resource Games (CRG) - games in which each agent is endowed with a set of resources and coalitions can bring about a set of goals if they are collectively endowed with the necessary amount of resources. The input of coalitional resource games bundles together several elements, e.g., the agent set Ag, the goal set G, the resource set R, etc. Shrot et al. (AAMAS 2009) examine coalition formation problems in the CRG model using the theory of Parameterized Complexity. Their refined analysis shows that not all parts of input act equal - some instances of the problem are indeed tractable while others still remain intractable.We answer an important question left open by Shrot, Aumann,and Kraus by showing that the SC Problem (checking whether a Coalition is Successful) is W[1]-hard when parameterized by the size of the coalition. Then via a single theme of reduction from SC, we are able to show that various problems related to resources, resource bounds, and resource conflicts introduced by Wooldridge et al. are (i) W[1]-hard or co-W[1]-hard w.r.t the size of the coalition; and (ii) Para-NP hard or co-Para-NP-hard w.r.t |R|. When parameterized by |G| or |R| + |Ag|, we give a general algorithm which proves that these problems are indeed tractable.
Incentive-Compatible Escrow Mechanisms
Authors: Witkowski Jens , Seuken Sven , Parkes David
Published: September 2022

The most prominent way to establish trust between buyers and sellers on online auction sites are reputation mechanisms. Two drawbacks of this approach are the reliance on the seller being long-lived and the susceptibility to whitewashing. In this paper, we introduce so-called escrow mechanisms that avoid these problems by installing a trusted intermediary which forwards the payment to the seller only if the buyer acknowledges that the good arrived in the promised condition. We address the incentive issues that arise and design an escrow mechanism that is incentive-compatible, efficient, interim individually rational and ex ante budget-balanced. In contrast to previous work on trust and reputation, our approach does not rely on knowing the sellers' cost functions or the distribution of buyer valuations.
Fast Newton-CG Method for Batch Learning of Conditional Random Fields
Authors: Tsuboi Yuta , Unno Yuya , Kashima Hisashi , Okazaki Naoaki
Published: September 2022

We propose a fast batch learning method for linear-chain Conditional Random Fields (CRFs) based on Newton-CG methods. Newton-CG methods are a variant of Newton method for high-dimensional problems. They only require the Hessian-vector products instead of the full Hessian matrices. To speed up Newton-CG methods for the CRF learning, we derive a novel dynamic programming procedure for the Hessian-vector products of the CRF objective function. The proposed procedure can reuse the byproducts of the time-consuming gradient computation for the Hessian-vector products to drastically reduce the total computation time of the Newton-CG methods. In experiments with tasks in natural language processing, the proposed method outperforms a conventional quasi-Newton method. Remarkably, the proposed method is competitive with online learning algorithms that are fast but unstable.
Adaptive Large Margin Training for Multilabel Classification
Authors: Guo Yuhong , Schuurmans Dale
Published: September 2022

Multilabel classification is a central problem in many areas of data analysis, including text and multimedia categorization, where individual data objects need to be assigned multiple labels. A key challenge in these tasks is to learn a classifier that can properly exploit label correlations without requiring exponential enumeration of label subsets during training or testing. We investigate novel loss functions for multilabel training within a large margin framework---identifying a simple alternative that yields improved generalization while still allowing efficient training. We furthermore show how covariances between the label models can be learned simultaneously with the classification model itself, in a jointly convex formulation, without compromising scalability. The resulting combination yields state of the art accuracy in multilabel webpage classification.
Efficiently Learning a Distance Metric for Large Margin Nearest Neighbor Classification
Authors: Park Kyoungup , Shen Chunhua , Hao Zhihui , Kim Junae
Published: September 2022

We concern the problem of learning a Mahalanobis distance metric for improving nearest neighbor classification. Our work is built upon the large margin nearest neighbor (LMNN) classification framework. Due to the semidefiniteness constraint in the optimization problem of LMNN, it is not scalable in terms of the dimensionality of the input data. The original LMNN solver partially alleviates this problem by adopting alternating projection methods instead of standard interior-point methods. Still, at each iteration, the computation complexity is at least O(D3) (D is the dimension of input data). In this work, we propose a column generation based algorithm to solve the LMNN optimization problem much more efficiently. Our algorithm is much more scalable in tha tat each iteration, it does not need full eigen-decomposition. Instead, we only need to find the leading eigen value and its corresponding eigen vector, which is of O(D2) complexity. Experiments show the efficiency and efficacy of our algorithms.
Markov Logic Sets: Towards Lifted Information Retrieval Using PageRank and Label Propagation
Authors: Neumann Marion , Ahmadi Babak , Kersting Kristian
Published: September 2022

Inspired by “GoogleTM Sets” and Bayesian sets, we consider the problem of retrieving complex objects and relations among them, i.e., ground atoms from a logical concept, given a query consisting of a few atoms from that concept. We formulate this as a within-network relational learning problem using few labels only and describe an algorithm that ranks atoms using a score based on random walks with restart (RWR): the probability that a random surfer hits an atom starting from the query atoms. Specifically, we compute an initial ranking using personalized PageRank. Then, we find paths of atoms that are connected via their arguments, variablize the ground atoms in each path, in order to create features for the query. These features are used to re-personalize the original RWR and to finally compute the set completion, based on Label Propagation. Moreover, we exploit that RWR techniques can naturally be lifted and show that lifted inference for label propagation is possible. We evaluate our algorithm on a realworld relational dataset by finding completions of sets of objects describing the Roman city of Pompeii. We compare to Bayesian sets and show that our approach gives very reasonable set completions.
A Generalised Solution to the Out-of-Sample Extension Problem in Manifold Learning
Authors: Strange Harry , Zwiggelaar Reyer
Published: September 2022

Manifold learning is a powerful tool for reducing the dimensionality of a dataset by finding a low-dimensional embedding that retains important geometric and topological features. In many applications it is desirable to add new samples to a previously learnt embedding, this process of adding new samples is known as the out-of-sample extension problem. Since many manifold learning algorithms do not naturally allow for new samples to be added we present an easy to implement generalized solution to the problem that can be used with any existing manifold learning algorithm. Our algorithm is based on simple geometric intuition about the local structure of a manifold and our results show that it can be effectively used to add new samples to a previously learnt embedding. We test our algorithm on both artificial and real world image data and show that our method significantly out performs existing out-of-sample extension strategies.
Learning a Kernel for Multi-Task Clustering
Authors: Gu Quanquan , Li Zhenhui , Han Jiawei
Published: September 2022

Multi-task learning has received increasing attention in the past decade. Many supervised multi-task learning methods have been proposed, while unsupervised multi-task learning is still a rarely studied problem. In this paper, we propose to learn a kernel for multi-task clustering. Our goal is to learn a Reproducing Kernel Hilbert Space, in which the geometric structure of the data in each task is preserved, while the data distributions of any two tasks are as close as possible. This is formulated as a unified kernel learning framework, under which we study two types of kernel learning: nonparametric kernel learning and spectral kernel design. Both types of kernel learning can be solved by linear programming. Experiments on several cross-domain text data sets demonstrate that kernel k-means on the learned kernel can achieve better clustering results than traditional single-task clustering methods. It also outperforms the newly proposed multi-task clustering method.
An Online Spectral Learning Algorithm for Partially Observable Nonlinear Dynamical Systems
Authors: Boots Byron , Gordon Geoffrey
Published: September 2022

Recently, a number of researchers have proposed spectral algorithms for learning models of dynamical systems — for example, Hidden Markov Models (HMMs), Partially Observable Markov Decision Processes (POMDPs), and Transformed Predictive State Representations (TPSRs). These algorithms are attractive since they are statistically consistent and not subject to local optima. However, they are batch methods: they need to store their entire training data set in memory at once and operate on it as a large matrix, and so they cannot scale to extremely large data sets (either many examples or many features per example). In turn, this restriction limits their ability to learn accurate models of complex systems. To overcome these limitations, we propose a new online spectral algorithm, which uses tricks such as incremental Singular Value Decomposition (SVD) and random projections to scale to much larger data sets and more complex systems than previous methods. We demonstrate the new method on an inertial measurement prediction task and a high-bandwidth video mapping task and we illustrate desirable behaviors such as "closing the loop," where the latent state representation changes suddenly as the learner recognizes that it has returned to a previously known place.
Scaling Up Reinforcement Learning through Targeted Exploration
Authors: Mann Timothy , Choe Yoonsuck
Published: September 2022

Recent Reinforcement Learning (RL) algorithms, such as R-MAX, make (with high probability) only a small number of poor decisions. In practice, these algorithms do not scale well as the number of states grows because the algorithms spend too much effort exploring. We introduce an RL algorithm State TArgeted R-MAX (STAR-MAX) that explores a subset of the state space, called the exploration envelope ξ. When ξ equals the total state space, STAR-MAX behaves identically to R-MAX. When ξ is a subset of the state space, to keep exploration within ξ, a recovery rule β is needed. We compared existing algorithms with our algorithm employing various exploration envelopes. With an appropriate choice of ξ, STAR-MAX scales far better than existing RL algorithms as the number of states increases. A possible drawback of our algorithm is its dependence on a good choice of ξ and β. However, we show that an effective recovery rule β can be learned on-line and ξ can be learned from demonstrations. We also find that even randomly sampled exploration envelopes can improve cumulative rewards compared to R-MAX. We expect these results to lead to more efficient methods for RL in large-scale problems.
Non-Parametric Approximate Linear Programming for MDPs
Authors: Pazis Jason , Parr Ronald
Published: September 2022

The Approximate Linear Programming (ALP) approach to value function approximation for MDPs is a parametric value function approximation method, in that it represents the value function as a linear combination of features which are chosen a priori. Choosing these features can be a difficult challenge in itself. One recent effort, Regularized Approximate Linear Programming (RALP), uses L1 regularization to address this issue by combining a large initial set of features with a regularization penalty that favors a smooth value function with few non-zero weights. Rather than using smoothness as a backhanded way of addressing the feature selection problem, this paper starts with smoothness and develops a non-parametric approach to ALP that is consistent with the smoothness assumption. We show that this new approach has some favorable practical and analytical properties in comparison to (R)ALP.
Optimal Rewards versus Leaf-Evaluation Heuristics in Planning Agents
Authors: Sorg Jonathan , Singh Satinder , Lewis Richard
Published: September 2022

Planning agents often lack the computational resources needed to build full planning trees for their environments. Agent designers commonly overcome this finite-horizon approximation by applying an evaluation function at the leaf-states of the planning tree. Recent work has proposed an alternative approach for overcoming computational constraints on agent design: modify the reward function. In this work, we compare this reward design approach to the common leaf-evaluation heuristic approach for improving planning agents. We show that in many agents, the reward design approach strictly subsumes the leaf-evaluation approach, i.e., there exists a reward function for every leaf-evaluation heuristic that leads to equivalent behavior, but the converse is not true. We demonstrate that this generality leads to improved performance when an agent makes approximations in addition to the finite-horizon approximation. As part of our contribution, we extend PGRD, an online reward design algorithm, to develop reward design algorithms for Sparse Sampling and UCT, two algorithms capable of planning in large state spaces.
Convex Sparse Coding, Subspace Learning, and Semi-Supervised Extensions
Authors: Zhang Xinhua , Yu Yaoliang , White Martha , Huang Ruitong , Schuurmans Dale
Published: September 2022

Automated feature discovery is a fundamental problem in machine learning. Although classical feature discovery methods do not guarantee optimal solutions in general, it has been recently noted that certain subspace learning and sparse coding problems can be solved efficiently, provided the number of features is not restricted a priori. We provide an extended characterization of this optimality result and describe the nature of the solutions under an expanded set of practical contexts. In particular, we apply the framework to a semi-supervised learning problem, and demonstrate that feature discovery can co-occur with input reconstruction and supervised training while still admitting globally optimal solutions. A comparison to existing semi-supervised feature discovery methods shows improved generalization and efficiency.
Comparing Agents' Success against People in Security Domains
Authors: Lin Raz , Kraus Sarit , Agmon Noa , Barrett Samuel , Stone Peter
Published: September 2022

The interaction of people with autonomous agents has become increasingly prevalent. Some of these settings include security domains, where people can be characterized as uncooperative, hostile, manipulative, and tending to take advantage of the situation for their own needs. This makes it challenging to design proficient agents to interact with people in such environments. Evaluating the success of the agents automatically before evaluating them with people or deploying them could alleviate this challenge and result in better designed agents. In this paper we show how Peer Designed Agents (PDAs) -- computer agents developed by human subjects -- can be used as a method for evaluating autonomous agents in security domains. Such evaluation can reduce the effort and costs involved in evaluating autonomous agents interacting with people to validate their efficacy. Our experiments included more than 70 human subjects and 40 PDAs developed by students. The study provides empirical support that PDAs can be used to compare the proficiency of autonomous agents when matched with people in security domains.
The Epistemic Logic Behind the Game Description Language
Authors: Ruan Ji , Thielscher Michael
Published: September 2022

A general game player automatically learns to play arbitrary new games solely by being told their rules. For this purpose games are specified in the game description language GDL, a variant of Datalog with function symbols and a few known keywords. In its latest version GDL allows to describe nondeterministic games with any number of players who may have imperfect, asymmetric information. We analyse the epistemic structure and expressiveness of this language in terms of epistemic modal logic and present two main results:The operational semantics of GDL entails that the situation at any stage of a game can be characterised by a multi-agent epistemic (i.e., S5-) model;(2) GDL is sufficiently expressive to model any situation that can be described by a (finite) multi-agent epistemic model.
Intrinsic Chess Ratings
Authors: Regan Kenneth , Haworth Guy
Published: September 2022

This paper develops and tests formulas for representing playing strength at chess by the quality of moves played, rather than by the results of games. Intrinsic quality is estimated via evaluations given by computer chess programs run to high depth, ideally so that their playing strength is sufficiently far ahead of the best human players as to be a `relatively omniscient' guide. Several formulas, each having intrinsic skill parameters s for `sensitivity' and c for `consistency', are argued theoretically and tested by regression on large sets of tournament games played by humans of varying strength as measured by the internationally standard Elo rating system. This establishes a correspondence between Elo rating and the parameters. A smooth correspondence is shown between statistical results and the century points on the Elo scale, and ratings are shown to have stayed quite constant over time. That is, there has been little or no `rating inflation'. The theory and empirical results are transferable to other rational-choice settings in which the alternatives have well-defined utilities, but in which complexity and bounded information constrain the perception of the utility values.
Integrating Clustering and Multi-Document Summarization by Bi-Mixture Probabilistic Latent Semantic Analysis (PLSA) with Sentence Bases
Authors: Shen Chao , Li Tao , Ding Chris
Published: September 2022

Probabilistic Latent Semantic Analysis (PLSA) has been popularly used in document analysis. However, as it is currently formulated, PLSA strictly requires the number of word latent classes to be equal to the number of document latent classes. In this paper, we propose Bi-mixture PLSA, a new formulation of PLSA that allows the number of latent word classes to be different from the number of latent document classes. We further extend Bi-mixture PLSA to incorporate the sentence information, and propose Bi-mixture PLSA with sentence bases (Bi-PLSAS) to simultaneously cluster and summarize the documents utilizing the mutual influence of the document clustering and summarization procedures. Experiments on real-world datasets demonstrate the effectiveness of our proposed methods.
Recognizing Text Through Sound Alone
Authors: Li Wenzhe , Hammond Tracy
Published: September 2022

This paper presents an acoustic sound recognizer to recognize what people are writing on a table or wall by utilizing the sound signal information generated from a key, pen, or fingernail moving along a textured surface. Sketching provides a natural modality to interact with text, and sound is an effective modality for distinguishing text. However, limited research has been conducted in this area. Our system uses a dynamic time- warping approach to recognize 26 hand-sketched characters (A-Z) solely through their acoustic signal. Our initial prototype system is user-dependent and relies on fixed stroke ordering. Our algorithm relied mainly on two features: mean amplitude and MFCCs (Mel-frequency cepstral coefficients). Our results showed over 80% recognition accuracy.
Complete Information Pursuit Evasion in Polygonal Environments
Authors: Klein Kyle , Suri Subhash
Published: September 2022

Suppose an unpredictable evader is free to move around in a polygonal environment of arbitrary complexity that is under full camera surveillance. How many pursuers, each with the same maximum speed as the evader, are necessary and sufficient to guarantee a successful capture of the evader? The pursuers always know the evader's current position through the camera network, but need to physically reach the evader to capture it. We allow the evader the knowledge of the current positions of all the pursuers as well---this accords with the standard worst-case analysis model, but also models a practical situation where the evader has ``hacked'' into the surveillance system. Our main result is to prove that three pursuers are always sufficient and sometimes necessary to capture the evader. The bound is independent of the number of vertices or holes in the polygonal environment.
Optimal Route Planning for Electric Vehicles in Large Networks
Authors: Eisner Jochen , Funke Stefan , Storandt Sabine
Published: September 2022

We consider the problem of routing electric vehicles (EV) in the most energy-efficient way within a road network taking into account both their limited energy supply as well as their ability to recuperate energy. Employing a classical result by Johnson and an observation about Dijkstra under non-constant edge costs we obtain O(n log n +m) query time after a O(nm) preprocessing phase for any road network graph whose edge costs represent energy consumption or recuperation.If the energy recuperation is height induced in a very natural way,the preprocessing phase can even be omitted. We then adapt a technique for speeding-up (unconstrained) shortest path queries to our scenario to achieve a speed-up of another factor of around 20. Our results drastically improve upon the recent results in (Artmeier et al. 2010) and allow for route planning of EVs in an instant even on large networks.
A Novel Technique for Avoiding Plateaus of Greedy Best-First Search in Satisﬁcing Planning
Authors: Imai Tatsuya , Kishimoto Akihiro
Published: September 2022

Greedy best-ﬁrst search (GBFS) is a popular and effective algorithm in satisﬁcing planning and is incorporated into high-performance planners. GBFS in planning decides its search direction with automatically generated heuristic functions. However, if the heuristic functions evaluate nodes inaccurately, GBFS may be misled into a valueless search direction, thus resulting in performance degradation. This paper presents a simple but effective algorithm considering a diversity of search directions to avoid the errors of heuristic information. Experimental results in solving a variety of planning problems show that our approach is successful.
Improving Cost-Optimal Domain-Independent Symbolic Planning
Authors: Kissmann Peter , Edelkamp Stefan
Published: September 2022

Symbolic search with BDDs has shown remarkable performance for cost-optimal deterministic planning by exploiting a succinct representation and exploration of state sets. In this paper we enhance BDD-based planning by applying a combination of domain-independent search techniques: the optimization of the variable ordering in the BDD by approximating the linear arrangement problem, pattern selection for improved construction of search heuristics in form of symbolic partial pattern databases, and a decision procedure for the amount of bidirection in the symbolic search process.
Exploiting Problem Symmetries in State-Based Planners
Authors: Pochter Nir , Zohar Aviv , Rosenschein Jeffrey
Published: September 2022

Previous research in Artificial Intelligence has identified the possibility of simplifying planning problems via the identification and exploitation of symmetries. We advance the state of the art in algorithms that exploit symmetry in planning problems by generalizing previous approaches, and applying symmetry reductions to state-based planners. We suggest several algorithms for symmetry exploitation in state-based search, but also provide a comprehensive view through which additional algorithms can be developed and fine-tuned. We evaluate our approach to symmetry exploitation on instances from previous planning competitions, and demonstrate that our algorithms significantly improve the solution time of instances with symmetries.
Conjunctive Representations in Contingent Planning: Prime Implicates Versus Minimal CNF Formula
Authors: To Son , Son Tran , Pontelli Enrico
Published: September 2022

This paper compares in depth the effectiveness of two conjunctive belief state representations in contingent planning: prime implicates and minimal CNF, a compact form of CNF formulae, which were initially proposed in conformant planning research (To et al. 2010a; 2010b). Similar to the development of the contingent planner CNFct for minimal CNF (To et al. 2011b), the present paper extends the progression function for the prime implicate representation in (To et al. 2010b) for computing successor belief states in the presence of incomplete information to handle non-deterministic and sensing actions required in contingent planning. The idea was instantiated in a new contingent planner, called PIct, using the same AND/OR search algorithm and heuristic function as those for CNFct. The experiments show that, like CNFct, PIct performs very well in a wide range of benchmarks. The study investigates the advantages and disadvantages of the two planners and identifies the properties of each representation method that affect the performance.
Coarse-to-Fine Inference and Learning for First-Order Probabilistic Models
Authors: Kiddon Chloe , Domingos Pedro
Published: September 2022

Coarse-to-fine approaches use sequences of increasingly fine approximations to control the complexity of inference and learning. These techniques are often used in NLP and vision applications. However, no coarse-to-fine inference or learning methods have been developed for general first-order probabilistic domains, where the potential gains are even higher. We present our Coarse-to-Fine Probabilistic Inference (CFPI) framework for general coarse-to-fine inference for first-order probabilistic models, which leverages a given or induced type hierarchy over objects in the domain. Starting by considering the inference problem at the coarsest type level, our approach performs inference at successively finer grains, pruning high- and low-probability atoms before refining. CFPI can be applied with any probabilistic inference method and can be used in both propositional and relational domains. CFPI provides theoretical guarantees on the errors incurred, and these guarantees can be tightened when CFPI is applied to specific inference algorithms. We also show how to learn parameters in a coarse-to-fine manner to maximize the efficiency of CFPI. We evaluate CFPI with the lifted belief propagation algorithm on social network link prediction and biomolecular event prediction tasks. These experiments show CFPI can greatly speed up inference without sacrificing accuracy.
Online Updating the Generalized Inverse of Centered Matrices
Authors: Wang Qing , Zhang Liang
Published: September 2022

In this paper, we present the exact online updating formulae for the generalized inverse of centered matrices. The computational cost is O(mn) for matrices of size m × n. Experimental results validate the proposed method’s accuracy and efficiency.
Optimal Subset Selection for Active Learning
Authors: Fu Yifan , Zhu Xingquan
Published: September 2022

Active learning traditionally relies on instance based utility measures to rank and select instances for labeling, which may result in labeling redundancy. To address this issue, we explore instance utility from two dimensions: individual uncertainty and instance disparity, using a correlation matrix. The active learning is transformed to a semi-definite programming problem to select an optimal subset with maximum utility value. Experiments demonstrate the algorithm performance in comparison with baseline approaches.
Evolution of Node Behavior in Link Prediction
Authors: Qiu Baojun , He Qi , Yen John
Published: September 2022

Link prediction is one of central tasks in the study of social network evolution and has many applications. In this paper, we use time series to describe node behavior, extract temporal features from the time series to characterize behavior evolution of nodes, and use the temporal features for link prediction. Our experimental results on several real datasets suggest that including the temporal features developed in the paper significantly improve link prediction performance.
Using Neural Networks for Evaluation in Heuristic Search Algorithm
Authors: Chen Hung-Che , Wei Jyh-Da
Published: September 2022

A major difficulty in a search-based problem-solving process is the task of searching the potentially huge search space resulting from the exponential growth of states. State explosion rapidly occupies memory and increases computation time. Although various heuristic search algorithms have been developed to solve problems in a reasonable time, there is no efficient method to construct heuristic functions. In this work, we propose a method by which a neural network can be iteratively trained to form an efficient heuristic function. An adaptive heuristic search procedure is involved in the training iterations. This procedure reduces the evaluation values of the states that are involved in the currently known best solution paths. By doing so, the promising states are continuously moved forward. The adapted heuristic values are fed back to neural networks; thus, a well-trained network function can find the near-best solutions quickly. To demonstrate this method, we solved the fifteen-puzzle problem. Experimental results showed that the solutions obtained by our method were very close to the shortest path, and both the number of explored nodes and the search time were significantly reduced.
Assessing Quality in the Web of Linked Sensor Data
Authors: Baillie Chris , Edwards Peter , Pignotti Edoardo
Published: September 2022

Assessing the quality of sensor data available on the Web is essential in order to identify reliable information for decision-making. This paper discusses how provenance of sensor observations and previous quality ratings can influence quality assessment decisions.
NMR-BASED EXPERIMENTAL RESEARCH ON THE CHARACTERISTICS OF ROCK FRAGMENTATION BY BLASTING BASED ON POROSITY CHANGE
Authors: Wang Yanbing , Wu Houwei , Li Yangyang , Liu Jiaye
Published: September 2022

In this paper, the nuclear magnetic resonance detection technology is introduced to quantitatively identify the range of damage on the rock samples under different blasting conditions. This was accomplished by examining the rock breaking and the damage caused by the dynamic effect of explosive stress wave and the quasi-static effect of detonation gas. Two experimental conditions were undertaken: 1) blocked blasthole under the combined action of explosive stress wave and detonation gas; 2) non-blocked blasthole under the single action of explosive stress wave-with rock porosity and transverse relaxation time, T2, spectrum among other parameters used as the criteria. Nuclear magnetic resonance (NMR) detection technology intuitively was also used. The results of nuclear magnetic resonance were compared and verified with ultrasonic test, rock strength measurement, and numerical simulation tests of fluid-solid coupling. Results show that the range of damage under the combined action of explosive stress wave and detonation gas is larger than that under the single action of explosive stress wave. The quasi-static action of the explosive gas plays an important role in the process of rock breaking.
Centrifuge modelling of the effect of base slab stiffness on long-term heave and swell pressure
Authors: Chan Deryck , Madabhushi Gopal , Viggiani Giulia , Williamson Michael , Hsu Yu Sheng
Published: September 2022

Long-term heave of basement slabs is a significant problem in cities with overconsolidated clay, such as London. There is a dearth of data to calibrate the methods commonly used by designers to predict heave displacement and swell pressure. This paper presents results from two centrifuge tests aimed at reproducing the phenomenon of long-term basement heave. Reduced scale models of rectangular basements with different slab thicknesses underlain by overconsolidated clay were tested, to investigate the effect of base slab stiffness on heave behaviour. The centrifuge tests provided measurements of the profiles of vertical displacement, bending moments in the slab and contact pressure at the slab–soil interface. This is the first geotechnical centrifuge study to provide simultaneous measurements of vertical displacement and swell pressures during long-term basement heave. Whereas the flexible basement underwent significant differential heave and almost complete relaxation of swell pressures, the stiff basement generated large swell pressures and consequently large bending stresses. These results confirm that the prediction of high heave pressures is a self-fulfilling prophecy: a basement slab with high stiffness will beget large swell pressures. The experimental measurements of swell pressure and heave were compared to predictions by a simplified non-linear method of heave calculation. The simplified non-linear method produced acceptable predictions of total heave.
Anatomía macroscópica del encéfalo dirigida a estudiantes de Psicología
Authors:   Universidad Cooperativa de Colombia, Parada Durán Silvia Inés
Published: September 2022

Las prácticas de laboratorio en el curso “Psicobiología para psicólogos” es una actividad complementaria al trabajo práctico de la conceptualización teórica desarrollada en el aula. Se incorporan recursos didácticos para el desarrollo de competencias generales y específicas para un proceso académico significativo que permite a los estudiantes participar activamente en la construcción de su propio conocimiento, en un contexto experiencial y de descubrimiento. Las prácticas en ambientes prácticos de aprendizaje motivan al estudiante a la investigación científica y potencian habilidades de observación, identificación, comparación, análisis y discusión. En esta guía, se incluyen contenidos teóricos que le facilitan al estudiante la preparación del conocimiento para el desarrollo práctico de su proceso de aprendizaje. Adicionalmente, esta guía dispone de actividades de estudio dinámicas para mejorar su comprensión e incluye parámetros claves para la presentación de informe del desarrollo de la actividad práctica. La guía corresponde a uno de los componentes desarrollados en el curso “Psicobiología para psicólogos” para los estudiantes de primer semestre de Psicología.
Desarrollo de brigadas de salud mental en instituciones educativas basada en la experiencia
Authors:   Universidad Cooperativa de Colombia, Barboza Peralta Mónica del Carmen , Mercado Salgado Dianys María , Blanquicett Romero Julio César , Ruiz Arias Viviana María
Published: September 2022

La presente guía se propone como una herramienta de apoyo para el desarrollo de brigadas de salud mental en instituciones educativas, con el fin de proporcionar las fases requeridas para la planeación, la ejecución y la valoración del impacto generado en la población. Las brigadas de salud mental constituyen una de las estrategias principales de intervención en el marco de la Proyección Social de la Universidad Cooperativa de Colombia. Así mismo, la experiencia adquirida por los autores en su desarrollo para el programa de Psicología y la Facultad de Ciencias Sociales y Humanas de la sede Montería se materializa ofreciendo un derrotero para el uso de estudiantes y profesores con un enfoque solidario.
Real-time monitoring of physiological parameters in the study of Escherichia coli early response to peroxide stress
Authors:   Institute of Ecology and Genetics of Microorganisms, Ural Branch of RAS, Tyulenev Aleksey V. , Smirnova Galina V. ,   Institute of Ecology and Genetics of Microorganisms, Ural Branch of RAS, Gabova Anna O. ,   Perm National Research Polytechnic University, Triandafilova Galina A. ,   Institute of Ecology and Genetics of Microorganisms, Ural Branch of RAS, Oktyabrsky Oleg N. ,   Institute of Ecology and Genetics of Microorganisms, Ural Branch of RAS
Published: September 2022

The response of aerobically growing Escherichia coli cultures to peroxide stress was studied using synchronous real-time monitoring of parameters pO2 (oxygen partial pressure), pH, Eh (redox potential of the culture), extracellular levels of K+ and S2-, in combination with traditional physiological, biochemical and genetic methods. A sharp increase in pO2 level in the medium caused by the destruction of H2O2 by endogenous catalases was observed in the early response to peroxide stress. The addition of 100 µM H2O2 provoked a reversible decrease in the specific growth rate, accompanied by an increase of extra- and intracellular glutathione and a short-term increase in sulfide production. Treatment with a high dose of H2O2 (10 mM) led to growth inhibition and a CFU loss, most pronounced in glutathione synthesis mutants. Simultaneously, in 8% of cells, the membrane potential decreased, a part of potassium was released into the medium, and the expression of the sulA gene, which is part of the SOS-regulon, increased. Application of an integrated approach to the study of stress revealed a close relationship between growth parameters (specific growth rate and survival), respiratory activity, sulfide production, and the ability of E. coli cells to maintain the membrane potential and K+ gradient.