bluuebunny/crossref_metadata_2025 huggingface dataset:
ASP-Based Time-Bounded Planning for Logistics Robots
Authors: Schäpers Björn , Niemueller Tim , Lakemeyer Gerhard , Gebser Martin , Schaub Torsten
Published: September 2022

Manufacturing industries are undergoing a major paradigm shift towards more autonomy. Automated planning and scheduling then becomes a necessity. The Planning and Execution Competition for Logistics Robots in Simulation held at ICAPS is based on this scenario and provides an interesting testbed. However, the posed problem is challenging as also demonstrated by the somewhat weak results in 2017. The domain requires temporal reasoning and dealing with uncertainty. We propose a novel planning system based on Answer Set Programming and the Clingo solver to tackle these problems and incentivize robot cooperation. Our results show a significant performance improvement, both, in terms of lowering computational requirements and better game metrics.
Efficiently Exploring Ordering Problems through Conflict-Directed Search
Authors: Chen Jingkai , Fang Cheng , Wang David , Wang Andrew , Williams Brian
Published: September 2022

In planning and scheduling, solving problems with both state and temporal constraints is hard since these constraints may be highly coupled. Judicious orderings of events enable solvers to efficiently make decisions over sequences of actions to satisfy complex hybrid specifications. The ordering problem is thus fundamental to planning. Promising recent works have explored the ordering problem as search, incorporating a special tree structure for efficiency. However, such approaches only reason over partial order specifications. Having observed that an ordering is inconsistent with respect to underlying constraints, prior works do not exploit the tree structure to efficiently generate orderings that resolve the inconsistency. In this paper, we present Conflict-directed Incremental Total Ordering (CDITO), a conflict-directed search method to incrementally and systematically generate event total orders given ordering relations and conflicts returned by sub-solvers. Due to its ability to reason over conflicts, CDITO is much more efficient than Incremental Total Ordering. We demonstrate this by benchmarking on temporal network configuration problems that involve routing network flows and allocating bandwidth resources over time.
Cutting the Size of Compressed Path Databases with Wildcards and Redundant Symbols
Authors: Chiari Mattia , Zhao Shizhe , Botea Adi , Gerevini Alfonso E. , Harabor Daniel , Saetti Alessandro , Salvetti Matteo , Stuckey Peter J.
Published: September 2022

Path planning on gridmaps is a common problem in AI and a popular topic in application areas such as computer games. Compressed Path Databases (CPDs) represent a state-of-theart approach to the problem, in terms of the speed of computing full optimal paths and also individual optimal moves. Despite significant improvements in recent years, the memory required to store a CPD can still be a bottleneck for large game maps. In this work we present a new compression approach that can reduce the size of CPDs. Our approach uses an extended notion of wildcards and a novel concept called a redundant symbol. We implement our ideas on top of a state-of-the-art CPD system and, in a range of experiments, we demonstrate a substantial reduction in the size of CPDs.
An Empirical Study of Perfect Potential Heuristics
Authors: Correa Augusto B. , Pommerening Florian
Published: September 2022

Potential heuristics are weighted functions over state features of a planning task. A recent study defines the complexity of a task as the minimum required feature complexity for a potential heuristic that makes a search backtrack-free. This gives an indication of how complex potential heuristics need to be to achieve good results in satisficing planning. However, these results do not directly transfer to optimal planning.In this paper, we empirically study how complex potential heuristics must be to represent the perfect heuristic and how close to perfect heuristics can get with a limited number of features. We aim to identify the practical trade-offs between size, complexity and time for the quality of potential heuristics. Our results show that, even for simple planning tasks, finding perfect potential heuristics might be harder than expected.
Mixed Discrete Continuous Non-Linear Planning through Piecewise Linear Approximation
Authors: Denenberg Elad , Coles Amanda
Published: September 2022

Reasoning with continuously changing numeric quantities is vital to applying planners in many real-world scenarios. Several planners capable of doing this have been developed recently. Scalability remains a challenge for such planners, especially those that reason with non-linear continuous change. In this paper, we present a novel approach to reasoning with non-linear domains. Bounding the problem using linear over and under-estimators, allows us to use scalable planners that handle linear change to find plans for non-linear domains. We compare the performance of our approach to existing planners on several domains and demonstrate that our planner can achieve state-of-the-art performance in non-linear planning.
Using Bi-Directional Information Exchange to Improve Decentralized Schedule-Driven Traffic Control
Authors: Hu Hsu-Chieh , Smith Stephen F.
Published: September 2022

Recent work in decentralized, schedule-driven traffic control has demonstrated the ability to improve the efficiency of traffic flow in complex urban road networks. In this approach, a scheduling agent is associated with each intersection. Each agent senses the traffic approaching its intersection and in real-time constructs a schedule that minimizes the cumulative wait time of vehicles approaching the intersection over the current look-ahead horizon. In order to achieve network level coordination in a scalable manner, scheduling agents communicate only with their direct neighbors. Each time an agent generates a new intersection schedule it communicates its expected outflows to its downstream neighbors as a prediction of future demand and these outflows are appended to the downstream agent’s locally perceived demand. In this paper, we extend this basic coordination algorithm to additionally incorporate the complementary flow of information reflective of an intersection’s current congestion level to its upstream neighbors. We present an asynchronous decentralized algorithm for updating intersection schedules and congestion level estimates based on these bi-directional information flows. By relating this algorithm to the self-optimized decision making of the basic operation, we are able to approach network-wide optimality and reduce inefficiency due to strictly self-interested intersection control decisions.
Planning with Global State Constraints and State-Dependent Action Costs
Authors: Ivankovic Franc , Gordon Dan , Haslum Patrik
Published: September 2022

Planning with global state constraints is an extension of classical planning in which some properties of each state are derived via a set of equations, rules or constraints. This extension enables more elegant modelling of networked physical systems such as power grids. So far, research in this setting focused on domains where action costs are constant, rather than a function of a state in which the action is applied. This limitation prevents us from accurately specifying the objective in some real-world domains, leading to generation of suboptimal plans. For example, when reconfiguring a power network, we often need to temporarily leave some users without electricity for a certain amount of time, and in such circumstances it is desirable to reduce the unsupplied load over the total time span. This preference can be expressed using statedependent action costs. We extend planning with global state constraints to include state-dependent action costs, adapt abstraction heuristics to this setting, and show improved performance on a set of problems.
Eliminating Redundant Actions in Partially Ordered Plans — A Complexity Analysis
Authors: Olz Conny , Bercher Pascal
Published: September 2022

In this paper we study the computational complexity of postoptimizing partially ordered plans, i.e., we investigate the problem that is concerned with detecting and deleting unnecessary actions. For totally ordered plans it can easily be tested in polynomial time whether a single action can be removed without violating executability. Identifying an executable subplan, i.e., asking whether k plan steps can be removed, is known to be NP-complete. We investigate the same questions for partially ordered input plans, as they are created by many search algorithms or used by real-world applications – in particular time-critical ones that exploit parallelism of non-conflicting actions. More formally, we investigate the computational complexity of removing an action from a partially ordered solution plan in which every linearization is a solution in the classical sense while allowing ordering insertions afterwards to repair arising executability issues. It turns out that this problem is NP-complete – even if just a single action is removed – and thereby show that this reasoning task is harder than for totally ordered plans. Moreover, we identify the structural properties responsible for this hardness by providing a fixed-parameter tractability (FPT) result.
Finding Centroids and Minimum Covering States in Planning
Authors: Pozanco Alberto , E-Martín Yolanda , Fernández Susana , Borrajo Daniel
Published: September 2022

In automated planning, the most common task consists of finding a plan that achieves a set of goals. In this paper, we focus on a different task; that of finding states that minimize some goal-related metric. First, we present some domains for which that task is useful. Second, we propose two of such types of states: (1) centroid states, which minimize the distance to all the goals in the problem; and (2) minimum covering states, which minimize the maximum distance to any of the goals. Third, we define optimal and suboptimal algorithms to find such states. Finally, we show some experimental results in planning instances from different domains.
Symbolic Planning with Axioms
Authors: Speck David , Geißer Florian , Mattmüller Robert , Torralba Álvaro
Published: September 2022

Axioms are an extension for classical planning models that allow for modeling complex preconditions and goals exponentially more compactly. Although axioms were introduced in planning more than a decade ago, modern planning techniques rarely support axioms, especially in cost-optimal planning. Symbolic search is a popular and competitive optimal planning technique based on the manipulation of sets of states. In this work, we extend symbolic search algorithms to support axioms natively. We analyze different ways of encoding derived variables and axiom rules to evaluate them in a symbolic representation. We prove that all encodings are sound and complete, and empirically show that the presented approach outperforms the previous state of the art in costoptimal classical planning with axioms.
Unsupervised Grounding of Plannable First-Order Logic Representation from Images
Authors: Asai Masataro
Published: September 2022

Recently, there is an increasing interest in obtaining the relational structures of the environment in the Reinforcement Learning community. However, the resulting “relations” are not the discrete, logical predicates compatible with the symbolic reasoning such as classical planning or goal recognition. Meanwhile, Latplan (Asai and Fukunaga 2018) bridged the gap between deep-learning perceptual systems and symbolic classical planners. One key component of the system is a Neural Network called State AutoEncoder (SAE), which encodes an image-based input into a propositional representation compatible with classical planning. To get the best of both worlds, we propose First-Order State AutoEncoder, an unsupervised architecture for grounding the first-order logic predicates and facts. Each predicate models a relationship between objects by taking the interpretable arguments and returning a propositional value. In the experiment using 8Puzzle and a photo-realistic Blocksworld environment, we show that (1) the resulting predicates capture the interpretable relations (e.g., spatial), (2) they help to obtain the compact, abstract model of the environment, and finally, (3) the resulting model is compatible with symbolic classical planning.
Entropy Based Independent Learning in Anonymous Multi-Agent Settings
Authors: Verma Tanvi , Varakantham Pradeep , Lau Hoong Chuin
Published: September 2022

Efficient sequential matching of supply and demand is a problem of interest in many online to offline services. For instance, Uber, Lyft, Grab for matching taxis to customers; Ubereats, Deliveroo, FoodPanda etc for matching restaurants to customers. In these online to offline service problems, individuals who are responsible for supply (e.g., taxi drivers, delivery bikes or delivery van drivers) earn more by being at the ”right” place at the ”right” time. We are interested in developing approaches that learn to guide individuals to be in the ”right” place at the ”right” time (to maximize revenue) in the presence of other similar ”learning” individuals and only local aggregated observation of other agents states (e.g., only number of other taxis in same zone as current agent).
Observation Decoding with Sensor Models: Recognition Tasks via Classical Planning
Authors: Aineto Diego , Jimenez Sergio , Onaindia Eva
Published: September 2022

Observation decoding aims at discovering the underlying state trajectory of an acting agent from a sequence of observations. This task is at the core of various recognition activities that exploit planning as resolution method but there is a general lack of formal approaches that reason about the partial information received by the observer or leverage the distribution of the observations emitted by the sensors. In this paper, we formalize the observation decoding task exploiting a probabilistic sensor model to build more accurate hypothesis about the behaviour of the acting agent. Our proposal extends the expressiveness of former recognition approaches by accepting observation sequences where one observation of the sequence can represent the reading of more than one variable, thus enabling observations over actions and partially observable states simultaneously. We formulate the probability distribution of the observations perceived when the agent performs an action or visits a state as a classical cost planning task that is solved with an optimal planner. The experiments will show that exploiting a sensor model increases the accuracy of predicting the agent behaviour in four different contexts.
Multiple-Environment Markov Decision Processes: Efficient Analysis and Applications
Authors: Chatterjee Krishnendu , Chmelík Martin , Karkhanis Deep , Novotný Petr , Royer Amélie
Published: September 2022

Multiple-environment Markov decision processes (MEMDPs) are MDPs equipped with not one, but multiple probabilistic transition functions, which represent the various possible unknown environments. While the previous research on MEMDPs focused on theoretical properties for long-run average payoff, we study them with discounted-sum payoff and focus on their practical advantages and applications. MEMDPs can be viewed as a special case of Partially observable and Mixed observability MDPs: the state of the system is perfectly observable, but not the environment. We show that the specific structure of MEMDPs allows for more efficient algorithmic analysis, in particular for faster belief updates. We demonstrate the applicability of MEMDPs in several domains. In particular, we formalize the sequential decision-making approach to contextual recommendation systems as MEMDPs and substantially improve over the previous MDP approach.
Solving the Longest Simple Path Problem with Heuristic Search
Authors: Cohen Yossi , Stern Roni , Felner Ariel
Published: September 2022

Prior approaches for finding the longest simple path (LSP) in a graph used constraints solvers and genetic algorithms. In this work, we solve the LSP problem with heuristic search. We first introduce several methods for pruning dominated path prefixes. Then, we propose several admissible heuristic functions for this problem. Experimental results demonstrate the large impact of the proposed heuristics and pruning rules.
Algorithm Selection for Optimal Multi-Agent Pathfinding
Authors: Kaduri Omri , Boyarski Eli , Stern Roni
Published: September 2022

The challenge of finding an optimal solution to a multi-agent path finding (MAPF) problem has attracted significant academic and industrial interest in recent years. While the problem is NP-Hard, modern optimal MAPF algorithms can scale to solve problems with hundreds of agents. Nevertheless, no single optimal MAPF algorithm dominates all benchmarks problems, and there are no clear, provable, guidelines for when each algorithm should be used. To address this, we present the first successful Algorithm Selection (AS) model for optimal MAPF. We propose two approaches for learning an AS model. The first approach uses a standard supervised learning algorithm with a set of handcrafted MAPF-specific features. The second approach, casts a MAPF problem to an image and applies a deep Convolutional Neural Network to classify it. We evaluate both approaches over a large dataset and show that using an AS model to select which algorithm to use for each instance results in solving more problems and in a shorter runtime compared to the state of the art.
Solving the Watchman Route Problem on a Grid with Heuristic Search
Authors: Seiref Shawn , Jaffey Tamir , Lopatin Margarita , Felner Ariel
Published: September 2022

In this paper we optimally solve the Watchman Route Problem (WRP) on a grid. We are given a grid map with obstacles and the task is to (offline) find a (shortest) path through the grid such that all cells in the map can be visually seen by at least one cell on the path. We formalize WRP as a heuristic search problem and solve it with an A*-based algorithm. We develop a series of admissible heuristics with increasing difficulty and accuracy. In particular, our heuristics abstract the problem into line-of-sight clusters graph. Then, solutions for the minimum spanning tree (MST) and the traveling salesman problem (TSP) on this graph are used as admissible heuristics for WRP. We theoretically and experimentally study these heuristics and show that we can optimally and suboptimally solve problems of increasing difficulties.
Computing Close to Optimal Weighted Shortest Paths in Practice
Authors: Tran Nguyet , Dinneen Michael J. , Linz Simone
Published: September 2022

This paper proposes a new practical method for the weighted region problem (WRP). The objective of WRP is to find a minimum cost path between two vertices among different regions where each region incurs a traversal cost per unit distance. Currently, there is no practical algorithm that solves this problem exactly. Among the approximation methods that solve instances of WRP, there is a limited number of algorithms that compute paths whose lengths are close to optimal, which we call very-close optimum paths. However, they are considered as theoretical methods. On the other hand, algorithms for solving WRP that can be applied to practical data sets (using decomposition ideas or heuristics) are not guaranteed to find a very-close optimum path within an acceptable amount of time. In this paper, we consider an alternative method for solving WRP that exploits Snell's law of physical refraction. We compare the performance of our new algorithm with that of two existing algorithms, using at least 500 test cases for each such comparison. The experimental results show that our algorithm returns a very-close optimum weighted shortest path in reasonable time.
Dynamic Controllability and (J,K)-Resiliency in Generalized Constraint Networks with Uncertainty
Authors: Zavatteri Matteo , Rizzi Romeo , Villa Tiziano
Published: September 2022

A number of formal models have been proposed to address temporal and resource allocation problems under uncertainty. Such models are typically shipped with an embedded notion of dynamic controllability, enclosing the ability to always make the right decisions, during execution, according to the observed uncontrollable events that always happen. In the business process management community, resource allocation was recently studied to deal with uncontrollable choices, whereas in the security community it was studied to face the uncontrollable availability of resources. The latter is a kind of dynamic controllability known as resiliency where uncontrollable events might also not happen. To the best of our knowledge, approaches handling resiliency on top of dynamic controllability still remain unexplored. To bridge this gap, we propose Generalized Constraint Networks with Uncertainty (GCNUs), a model that we devised to address resource controllability more widely, boosting expressiveness while considering several sources of uncertainty simultaneously. We define dynamic controllability and (J, K)-resiliency of GCNUs. We reason on the structure of these problems, carry out a complexity analysis and provide algorithms to solve them.
Exploring Context-Free Languages via Planning: The Case for Automating Machine Learning
Authors: Katz Michael , Ram Parikshit , Sohrabi Shirin , Udrea Octavian
Published: September 2022

While Machine Learning has achieved considerable success in recent years, this success crucially relies on human experts to select appropriate features, workflows, algorithms with their hyper-parameters, etc. Automating the role of the human expert has seen some attention from the Machine Learning community, with a dedicated workshop running since 2014 at one of the top Machine Learning conferences. % In this work, we propose to exploit multiple AI Planning tools for automating the human expert, generating Machine Learning pipelines automatically. We start from a knowledge about possible valid pipelines encoded as Context-Free Grammar, translate the problem of generating the corresponding language into Hierarchical Task Network (HTN) Planning model, further translate the HTN Planning model into a classical planning model. We use existing planners to produce multiple plans for the classical planning task, translate these plans into Machine Learning pipelines, train and evaluate these pipelines. Based on pipelines' accuracy feedback we update the classical planning model to improve the quality of pipelines obtained in next iterations. Using planning tools allows us to exploit the flexibility of model update instead of solution modification. We present an application that helps users to focus pipelines' exploration process by allowing to encode additional constraints on desired pipelines. Our experimental evaluation shows the feasibility of using planning techniques in this context.
Real Time Crowd Navigation from First Principles of Probability Theory
Authors: Trautman Peter , Patel Karankumar
Published: September 2022

Constructing realistic and real time human-robot interaction models is a core challenge in crowd navigation. In this paper we derive a robot-agent interaction density from first principles of probability theory; we call our approach “first order interacting Gaussian processes” (foIGP). Furthermore, we compute locally optimal solutions—with respect to multi-faceted agent “intent” and “flexibility”—in near real time on a laptop CPU. We test on challenging scenarios from the ETH crowd dataset and show that the safety and efficiency statistics of foIGP is competitive with human safety and efficiency statistics. Further, we compute the safety and efficiency statistics of dynamic window avoidance, a physics based model variant of foIGP, a Monte Carlo inference based approach, and the best performing deep reinforcement learning algorithm; foIGP outperforms all of them.
– D3WA+ – A Case Study of XAIP in a Model Acquisition Task for Dialogue Planning
Authors: Sreedharan Sarath , Chakraborti Tathagata , Muise Christian , Khazaeni Yasaman , Kambhampati Subbarao
Published: September 2022

Recently, the D3WA system was proposed as a paradigm shift in how complex goal-oriented dialogue agents can be specified by taking a declarative view of design. However, it turns out actual users of the system have a hard time evolving their mental model and grasping the imperative consequences of declarative design. In this paper, we adopt ideas from existing works in the field of Explainable AI Planning (XAIP) to provide guidance to the dialogue designer during the model acquisition process. We will highlight in the course of this discussion how the setting presents unique challenges to the XAIP setting, including having to deal with the user persona of a domain modeler rather than the end-user of the system, and consequently having to deal with the unsolvability of models in addition to explaining generated plans.Quickview http://ibm.biz/d3wa-xaip
Joint Inference of Reward Machines and Policies for Reinforcement Learning
Authors: Xu Zhe , Gavran Ivan , Ahmad Yousef , Majumdar Rupak , Neider Daniel , Topcu Ufuk , Wu Bo
Published: September 2022

Incorporating high-level knowledge is an effective way to expedite reinforcement learning (RL), especially for complex tasks with sparse rewards. We investigate an RL problem where the high-level knowledge is in the form of reward machines, a type of Mealy machines that encode non-Markovian reward functions. We focus on a setting in which this knowledge is a priori not available to the learning agent. We develop an iterative algorithm that performs joint inference of reward machines and policies for RL (more specifically, q-learning). In each iteration, the algorithm maintains a hypothesis reward machine and a sample of RL episodes. It uses a separate q-function defined for each state of the current hypothesis reward machine to determine the policy and performs RL to update the q-functions. While performing RL, the algorithm updates the sample by adding RL episodes along which the obtained rewards are inconsistent with the rewards based on the current hypothesis reward machine. In the next iteration, the algorithm infers a new hypothesis reward machine from the updated sample. Based on an equivalence relation between states of reward machines, we transfer the q-functions between the hypothesis reward machines in consecutive iterations. We prove that the proposed algorithm converges almost surely to an optimal policy in the limit. The experiments show that learning high-level knowledge in the form of reward machines leads to fast convergence to optimal policies in RL, while the baseline RL methods fail to converge to optimal policies after a substantial number of training steps.
Improving AlphaZero Using Monte-Carlo Graph Search
Authors: Czech Johannes , Korus Patrick , Kersting Kristian
Published: September 2022

The AlphaZero algorithm has been successfully applied in a range of discrete domains, most notably board games. It utilizes a neural network that learns a value and policy function to guide the exploration in a Monte-Carlo Tree Search. Although many search improvements such as graph search have been proposed for Monte-Carlo Tree Search in the past, most of them refer to an older variant of the Upper Confidence bounds for Trees algorithm that does not use a policy for planning. We improve the search algorithm for AlphaZero by generalizing the search tree to a directed acyclic graph. This enables information flow across different subtrees and greatly reduces memory consumption. Along with Monte-Carlo Graph Search, we propose a number of further extensions, such as the inclusion of Epsilon-Greedy exploration, a revised terminal solver and the integration of domain knowledge as constraints. In our empirical evaluations, we use the CrazyAra engine on chess and crazyhouse as examples to show that these changes bring significant improvements to AlphaZero.
Scalable Rail Planning and Replanning: Winning the 2020 Flatland Challenge
Authors: Li Jiaoyang , Chen Zhe , Zheng Yi , Chan Shao-Hung , Harabor Daniel , Stuckey Peter J. , Ma Hang , Koenig Sven
Published: September 2022

Multi-Agent Path Finding (MAPF) is the combinatorial problem of finding collision-free paths for multiple agents on a graph. This paper describes MAPF-based software for solving train planning and replanning problems on large-scale rail networks under uncertainty. The software recently won the 2020 Flatland Challenge, a NeurIPS competition trying to determine how to efficiently manage dense traffic on rail networks. The software incorporates many state-of-the-art MAPF or, in general, optimization technologies, such as prioritized planning, large neighborhood search, safe interval path planning, minimum communication policies, parallel computing, and simulated annealing. It can plan collision-free paths for thousands of trains within a few minutes and deliver deadlock-free actions in real-time during execution.
Learning Heuristic Selection with Dynamic Algorithm Configuration
Authors: Speck David , Biedenkapp André , Hutter Frank , Mattmüller Robert , Lindauer Marius
Published: September 2022

A key challenge in satisficing planning is to use multiple heuristics within one heuristic search. An aggregation of multiple heuristic estimates, for example by taking the maximum, has the disadvantage that bad estimates of a single heuristic can negatively affect the whole search. Since the performance of a heuristic varies from instance to instance, approaches such as algorithm selection can be successfully applied. In addition, alternating between multiple heuristics during the search makes it possible to use all heuristics equally and improve performance. However, all these approaches ignore the internal search dynamics of a planning system, which can help to select the most useful heuristics for the current expansion step. We show that dynamic algorithm configuration can be used for dynamic heuristic selection which takes into account the internal search dynamics of a planning system. Furthermore, we prove that this approach generalizes over existing approaches and that it can exponentially improve the performance of the heuristic search. To learn dynamic heuristic selection, we propose an approach based on reinforcement learning and show empirically that domain-wise learned policies, which take the internal search dynamics of a planning system into account, can exceed existing approaches.
Best-First Width Search for Lifted Classical Planning
Authors: B. Corrêa Augusto , Seipp Jendrik
Published: September 2022

Lifted planners are useful to solve tasks that are too hard to ground. Still, computing informative lifted heuristics is difficult: directly adapting ground heuristics to the lifted setting is often too expensive, and extracting heuristics from the lifted representation can be uninformative. A natural alternative for lifted planners is to use width-based search. These algorithms are among the strongest for ground planning, even the variants that do not access the action model. In this work, we adapt best-first width search to the lifted setting and show that this yields state-of-the-art performance for hard-to-ground planning tasks.
Multi-Agent Path Finding with Temporal Jump Point Search
Authors: Hu Shuli , Harabor Daniel D. , Gange Graeme , Stuckey Peter J. , Sturtevant Nathan R.
Published: September 2022

Temporal Jump Point Search (JPST) is a recently introduced algorithm for grid-optimal pathfinding among dynamic temporal obstacles. In this work we consider JPST as a low-level planner in Multi-Agent Path Finding (MAPF). We investigate how the canonical ordering of JPST can negatively impact MAPF performance and we consider several strategies which allow us to overcome these limitations. Experiments show our new CBS/JPST approach can substantially improve on CBS/SIPP, a contemporary and leading method from the area.
A Compilation Based Approach to Finding Centroids and Minimum Covering States in Planning
Authors: Karpas Erez
Published: September 2022

In some scenarios, an agent may want to prepare for achieving one of several possible goals, by reaching some state which is close (according to some metric) to all possible goals. Recently, this task was formulated as finding centroids (which minimize the average distance to the goals) or minimum covering states (which minimize the maximum distance). In this paper, we present a compilation based approach for finding such states. Our compilation is very similar to the one used to find the worst case distinctiveness (wcd) in goal recognition design (GRD), and is orders of magnitude faster than the previous state-of-the-art, which was based on exhaustive search.
A Hybrid Genetic Algorithm for the Vehicle Routing Problem with Roaming Delivery Locations
Authors: Pham Quang Anh , Hà Minh Hoàng , Vu Duy Manh , Nguyen Huy Hoang
Published: September 2022

The Vehicle Routing Problem with Roaming Delivery Locations (VRPRDL) is a variant of the Vehicle Routing Problem (VRP) in which a customer can be present at many locations during a working day and a time window is associated with each location. The objective is to find a set of routes such that (i) the total traveling cost is minimized, (ii) only one location of each customer is visited within its time window, and (iii) all capacity constraints are satisfied. To solve the problem, we introduce a hybrid genetic algorithm which relies on problem-tailored solution representation, mutation, local search operators, as well as a set covering component exploring routes found during the search to find better solutions. We also propose a new split procedure which based on dynamic programming to evaluate the fitness of chromosomes. Experiments conducted on the benchmark instances clearly show that our proposed algorithm outperforms existing approaches in terms of stability and solution quality. We also improve 49 best known solutions of the literature.
Classical Planning as QBF without Grounding
Authors: Shaik Irfansha , Van de Pol Jaco
Published: September 2022

Most classical planners use grounding as a preprocessing step, essentially reducing planning to propositional logic. However, grounding involves instantiating all rules and actions with concrete object combinations, and results in large encodings for SAT/QBF-based planners.
This severe cost in memory becomes a main bottleneck when actions have many parameters, such as in the Organic Synthesis problems from the IPC 2018 competition.
We provide a compact QBF encoding that is logarithmic in the number of objects and avoids grounding completely by using universal quantification for object combinations.
We show that we can solve some of the Organic Synthesis problems, which could not be handled before by any SAT/QBF based planners due to grounding.
Planning Satellite Swarm Measurements for Earth Science Models: Comparing Constraint Processing and MILP Methods
Authors: Levinson Rich , Niemoeller Samantha , Nag Sreeja , Ravindra Vinay
Published: September 2022

We compare two planner solutions for a challenging Earth science application to plan coordinated measurements (observations) for a constellation of satellites. This problem is combinatorially explosive, involving many degrees of freedom for planner choices. Each satellite carries two different sensors and is maneuverable to 61 pointing angle options. The sensors collect data to update the predictions made by a high-fidelity global soil moisture prediction model. Soil moisture is an important geophysical variable whose knowledge is used in applications such as crop health monitoring and predictions of floods, droughts, and fires.
The global soil-moisture model produces soil-moisture predictions with associated prediction errors over the globe represented by a grid of 1.67 million Ground Positions (GPs). The prediction error varies over space and time and can change drastically with events like rain/fire. The planner's goal is to select measurements which reduce prediction errors to improve future predictions. This is done by targeting high-quality observations at locations of high prediction-error. Observations can be made in multiple ways, such as by using one or more instruments or different pointing angles; the planner seeks to select the way with the least measurement-error (higher observation quality).
In this paper we compare two planning approaches to this problem: Dynamic Constraint Processing (DCP) and Mixed Integer Linear Programming (MILP). We match inputs and metrics for both DCP and MILP algorithms to enable a direct apples-to-apples comparison. DCP uses domain heuristics to find solutions within a reasonable time for our application but cannot be proven optimal, while the MILP produces provably optimal solutions. We demonstrate and discuss the trades between DCP flexibility and performance vs. MILP's promise of provable optimality.
Learning General Optimal Policies with Graph Neural Networks: Expressive Power, Transparency, and Limits
Authors: Ståhlberg Simon , Bonet Blai , Geffner Hector
Published: September 2022

It has been recently shown that general policies for many classical planning domains can be expressed and learned in terms of a pool of features defined from the domain predicates using a description logic grammar. At the same time, most description logics correspond to a fragment of k-variable counting logic (C_k) for k=2, that has been shown to provide a tight characterization of the expressive power of graph neural networks. In this work, we make use of these results to understand the power and limits of using graph neural networks (GNNs) for learning optimal general policies over a number of tractable planning domains where such policies are known to exist. For this, we train a simple GNN in a supervised manner to approximate the optimal value function V*(s) of a number of sample states s. As predicted by the theory, it is observed that general optimal policies are obtained in domains where general optimal value functions can be defined with C_2 features but not in those requiring more expressive C_3 features. In addition, it is observed that the features learned are in close correspondence with the features needed to express V* in closed form. The theory and the analysis of the domains let us understand the features that are actually learned as well as those that cannot be learned in this way, and let us move in a principled manner from a combinatorial optimization approach to learning general policies to a potentially, more robust and scalable approach based on deep learning.
Multi-Agent Tree Search with Dynamic Reward Shaping
Authors: Velasquez Alvaro , Bissey Brett , Barak Lior , Melcer Daniel , Beckus Andre , Alkhouri Ismail , Atia George
Published: September 2022

Sparse rewards and their representation in multi-agent domains remains a challenge for the development of multi-agent planning systems. While techniques from formal methods can be adopted to represent the underlying planning objectives, their use in facilitating and accelerating learning has witnessed limited attention in multi-agent settings. Reward shaping methods that leverage such formal representations in single-agent settings are typically static in the sense that the artificial rewards remain the same throughout the entire learning process. In contrast, we investigate the use of such formal objective representations to define novel reward shaping functions that capture the learned experience of the agents. More specifically, we leverage the automaton representation of the underlying team objectives in mixed cooperative-competitive domains such that each automaton transition is assigned an expected value proportional to the frequency with which it was observed in successful trajectories of past behavior. This form of dynamic reward shaping is proposed within a multi-agent tree search architecture wherein agents can simultaneously reason about the future behavior of other agents as well as their own future behavior.
Evaluating Plan-Property Dependencies: A Web-Based Platform and User Study
Authors: Eifler Rebecca , Brandao Martim , Coles Amanda , Frank Jeremy , Hoffmann Jörg
Published: September 2022

The trade-offs between different desirable plan properties -- e.g.
PDDL temporal plan preferences -- are often difficult to
understand. Recent work addresses this by iterative planning with
explanations elucidating the dependencies between such plan
properties. Users can ask questions of the form ``Why does the plan
not satisfy property p?'', which are answered by ``Because then we
would have to forego q''. It has been shown that such dependencies
can be computed reasonably efficiently. But is this form of
explanation actually useful for users? We run a large crowd-worker
user study (N=100 in each of 3 domains) evaluating that question. To
enable such a study in the first place, we contribute a Web-based
platform for iterative planning with explanations, running in standard
browsers. Comparing users with vs. without access to the explanations,
we find that the explanations enable users to identify better
trade-offs between the plan properties, indicating an improved
understanding of the planning task.
Anxiety-Sensitive Planning: From Formal Foundations to Algorithms and Applications
Authors: Vanhée Loïs , Jeanpierre Laurent , Mouaddib Abdel-Illah
Published: September 2022

Anxiety is the most prominent source of stress, harmful behaviours, and psychological disorders. AI systems, usually built for maximizing performance, increase the worldwide exposition to anxiety. This foundational paper introduces Anxiety-Aware Markov Decision Processes (AA-MDPs), the first formalism rooted in fundamental psychology research for modelling the anxiety tied to policies. In addition, this paper formalizes models and practical polynomial algorithms for generating anxiety-sensitive policies. Empirical validation demonstrates that AA-MDPs policies replicate the influence of anxiety on human decision-making observed by fundamental psychology research. Last, this paper demonstrates that AA-MDPs are directly applicable for social good, through a real-world use case (Anxiety-Sensitive Itinerary Planning), the immediate applicability for augmenting any formerly-defined MDP model with anxiety-awareness, and direct tracks developing future high-impact models.
THE INFLUENCE OF PLASMA ASSISTANCE MODES ON CHARACTERISTICS AND COMPOSITION OF PVD ZIRCONIUM NITRIDE COATINGS
Authors: Krysina Olga V. , Ivanov Yurii F. , Koval Nikolay N. , Prokopenko Nikita A.
Published: September 2022

Zirconium nitride coatings are deposited by a vacuum-arc method at a low (0.01-0.04 Pa) nitrogen partial pressure in the modes without and with plasma assistance. The plasma assistance is provided by the operation of a gas plasma source based on a non-self-sustained arc discharge with thermionic and hollow cathodes. This new low-inertia method has not been practically studied in terms of formation of nitride coatings with different architecture (single-layer, multi-layer, gradient coatings). We note that the effect of plasma assistance (an increase of the nitrogen concentration in the nitride coating with the increasing nitrogen ion fraction in the gas-metal plasma) is practically unobservable in the ZrN coatings formed under the selected conditions. Furthermore, their phase compositions do not noticeably change and their physical, mechanical and tribological properties are not significantly improved.
A novel capillary gel electrophoresis based fragment analysis method for the rapid detection of important thrips species on alfalfa in Turkey
Authors: Morca Ali Ferhan , Yücel Cenk , Barış Aydemir , Atakan Ekrem , Çelik Ali
Published: September 2022

Thrips cause significant yield reduction in several industrial crops. Since these pests are also included in the quarantine organisms of Turkey, the rapid detection of agents is important to prevent their spread to new areas. Mitochondrial cytochrome oxidase I (COI) barcoding gene assay; one of the molecular methods is widely used in thrips identification. However, as the COI gene has a very short fragment length, it is very difficult to distinguish fragment sizes on agarose gel after PCR. In this study, a new identification method was developed by integrating the Capillary Gel Electrophoresis (CGE) system for Thrips tabaci Lideman, Frankliniella occidentalis (Pergande) and Frankliniella intonsa (Trybom) species, using primer pairs previously used by different researchers. The assay produces strong signals obtained by minimizing the margin of error in the separation of fragment lengths close to each other, especially in the short fragment length COI gene. Therefore, by eliminating the gel electrophoresis step, reliable detections could be obtained without exposure to hazardous chemicals. The novel method shortened the detection time and minimized the process mistakes on the detection of a single thrips with a low DNA concentration. Total 83 thrips individual (52 F. intonsa, 31 F. occidentalis) were able to be detected with this capillary gel electrophoresis based fragment analysis. The novel method is evaluated as unique, specific and quick for the detection of three different thrips species. It is also thought to be able to utilize for identification of different thrips species with short fragment sizes in the foreseeable future.
Contributions to the knowledge of the vernal butterflies of East Mediterranean region in Turkey
Authors: Seven Çalışkan Selma , Bozacı Vildan
Published: September 2022

The present paper is a continuation of the previously published spring butterflies of the Eastern Mediterranean Region. The information of collection station of the previously listed species of 68 stations was included in this study. The stations were divided into 8 groups according to their vertical distribution. Habitat types at various altitudes have been defined. The communities of Lepidoptera detected in these habitats are given. The status of the Pontia daplidice/edusa species group in the region is discussed.
La proyección de la marca a partir del diseño del logo: de la representación visual a la imagenconcepto corporativo
Authors: Llorente Barroso Carmen , Mañas Viniegra Luis , García García Francisco
Published: September 2022

La relación logo-marca se ha estudiado desde perspectivas parciales que no han profundizado en la capacidad asociativa del diseño logosimbólico. La marca se conforma como una realidad bidimensional en la que convergen aspectos sensibles (tangibles) y conceptuales (intangibles) que quedan depositados en el logo que la representa. El objetivo de esta investigación es analizar las posibilidades simbólico-asociativas del diseño de los logos de algunas de las grandes marcas españolas, con el propósito de explicar las relaciones más determinantes en la configuración de ese concepto corporativoestereotipado (marca). Se propone una triangulación metodológica apoyada en un focus group de ocho personas y una prueba de asociación realizada por 332 sujetos, a quienes se somete a una muestra de los logos de las 10 marcas españolas más valoradas según Interbrand (2019) que encabezan sectores competitivos diferentes. Los resultados indican que estos emblemas se conectan a imágenes sensibles (tangibles), vinculadas a los productos y/o servicios de las marcas estudiadas. Si bien, la asociación del diseño del logo a los elementos visuales que lo componen es muy inferior a la que, a priori, cabría esperar, lo que indica el alto grado de proyección simbólica de estos signos visuales. Además, los 10 logos de la muestra se asocian a imágenes conceptuales (intangibles), relacionadas con los valores que definen la personalidad de las marcas que refieren. Se concluye que los logos se constituyen como estandartes corporativos que hacen confluir, en la complejidad simbólica de su aparente simplicidad estética, múltiples asociaciones entre suexpresión visual y su proyección conceptual.