bluuebunny/crossref_metadata_2025 huggingface dataset:
Heuristic Search for Generalized Stochastic Shortest Path MDPs
Authors: Kolobov Andrey , Mausam Mausam , Weld Daniel , Geffner Hector
Published: September 2022

Research in efficient methods for solving infinite-horizon MDPs has so far concentrated primarily on discounted MDPs and the more general stochastic shortest path problems (SSPs). These are MDPs with 1) an optimal value function V* that is the unique solution of Bellman equation and 2) optimal policies that are the greedy policies w.r.t. V*. This paper’s main contribution is the description of a new class of MDPs, that have well-defined optimal solutions that do not comply with either 1 or 2 above. We call our new class Generalized Stochastic Shortest Path (GSSP) problems. GSSP allows more general reward structure than SSP and subsumes several established MDP types including SSP, positive-bounded, negative, and discounted-reward models. While existing efficient heuristic search algorithms like LAO* and LRTDP are not guaranteed to converge to the optimal value function for GSSPs, we present a new heuristic-search-based family of algorithms, FRET (Find, Revise, Eliminate Traps). A preliminary empirical evaluation shows that FRET solves GSSPs much more efficiently than Value Iteration.
On Modeling the Tactical Planning of Oil Pipeline Networks
Authors: Ferber Daniel
Published: September 2022

This paper aims at incorporating tactical aspects of oil pipeline networks to the supply chain planning model. The strategic design of supply chains is covered in literature by well understood and recurring patterns such as multi-commodity networks, dynamic parameters over time, capacity on facilities, transportation capacity or facilities with demand, production and inventory. We consider the following characteristics: capacity for in-transit inventory, transit time and flow reversal. Our objective is a better estimate for resources required by the network and therewith allow a more precise optimization of their use. All aspects are modeled to be efficiently solved by linear programming algorithms.
When Acyclicity Is Not Enough: Limitations of the Causal Graph
Authors: Jonsson Anders , Jonsson Peter , Lööw Tomas
Published: September 2022

Causal graphs are widely used in planning to capture the internal structure of planning instances. In the past, causal graphs have been exploited to generate hierarchical plans, to compute heuristics, and to identify classes of planning instances that are easy to solve. It is generally believed that planning is easier when the causal graph is acyclic. In this paper we show that this is not true in the worst case, proving that the problem of plan existence is PSPACE-complete even when the causal graph is acyclic. Since the variables of the planning instances in our reduction are propositional, this result applies to STRIPS planning with negative pre-conditions. Having established that planning is hard for acyclic causal graphs, we study a subclass of planning instances with acyclic causal graphs whose variables have strongly connected domain transition graphs. For this class, we show that plan existence is easy, but that bounded plan existence is hard, implying that optimal planning is significantly harder than satisficing planning for this class.
Solving the Traveling Tournament Problem with Iterative-Deepening A*
Authors: Uthus David , Riddle Patricia , Guesgen Hans
Published: September 2022

We give an overview of our journal paper on applying iterative-deepening A* to the traveling tournament problem, a combinatorial optimization problem from the sports scheduling literature. This approach involved combining past ideas and creating new ideas to help reduce node expansion. This resulted in a state-of-the-art approach for optimally solving instances of the traveling tournament problem. It was the first approach to solve the classic NL10 and CIRC10 instances, which had not been solved since the problem’s introduction.
Temporal-Difference Search in Computer Go
Authors: Silver David , Sutton Richard , Mueller Martin
Published: September 2022

Temporal-difference (TD) learning is one of the most successful and broadly applied solutions to the reinforcement learning problem; it has been used to achieve master-level play in chess, checkers and backgammon. Monte-Carlo tree search is a recent algorithm for simulation-based search, which has been used to achieve master-level play in Go. We have introduced a new approach to high-performance planning. Our method, TD search, combines TD learning with simulation-based search. Like Monte-Carlo tree search, value estimates are updated by learning online from simulated experience. Like TD learning, it uses value function approximation and bootstrapping to efficiently generalise between related states. We applied TD search to the game of 9x9 Go, using a million binary features matching simple patterns of stones. Without any explicit search tree, our approach outperformed a vanilla Monte-Carlo tree search with the same number of simulations. When combined with a simple alpha-beta search, our program also outperformed all traditional (pre-Monte-Carlo) search and machine learning programs on the 9x9 Computer Go Server.
On Adversarial Policy Switching with Experiments in Real-Time Strategy Games
Authors: King Brian , Fern Alan , Hostetler Jesse
Published: September 2022

Given a Markov game, it is often possible to hand-code or learn a set of policies that capture a diversity of possible strategies. It is also often possible to hand-code or learn an abstract simulator of the game that can estimate the outcome of playing two strategies against one another from any state. We consider how to use such policy sets and simulators to make decisions in large Markov games such as real-time strategy (RTS) games. Prior work has considered the problem using an approach we call minimax policy switching. At each decision epoch, all policy pairs are simulated against each other from the current state, and the minimax policy is chosen and used to select actions until the next decision epoch. While intuitively appealing, our first contribution is to show that this switching policy can have arbitrarily poor worst case performance. Our second contribution is to describe a simple modification, whose worst case performance is provably no worse than the minimax fixed policy in the set. Our final contribution is to conduct experiments with these algorithms in the domain of RTS games using both an abstract game engine that we can exactly simulate and a real game engine that we can only approximately simulate. The results show the effectiveness of policy switching when the simulator is accurate, and highlight challenges in the face of inaccurate simulations.
Optimizing Planning Domains by Automatic Action Schema Splitting
Authors: Areces Carlos , Bustos Facundo , Dominguez Martín , Hoffmann Jörg
Published: September 2022

As modeling details can have a large impact on planner perormance, domain transformation has been a traditional subject of interest in the planning community not only betweenlanguages, but also within languages. Herein, we automatean intra-language transformation method that has as yet beenapplied only manually, and that has never been formally described: action schema splitting, which transforms an actionschema with a big interface (many parameters) into severalschemas with smaller interfaces, exponentially reducing thenumber of ground actions. We spell out this method, characterizing exactly the choice of splits preserving equivalence tothe original schema. Making that choice involves a trade-off between interface size and plan length, which we explore bydesigning automatic domain optimization methods. Our experiments show that these methods can substantially improveperformance on domains with large interfaces.
Directed Fixed-Point Regression-Based Planning for Non-Deterministic Domains
Authors: Ramírez Miquel , Sardina Sebastian
Published: September 2022

We present a novel approach to fully-observable nondeterministic planning (FOND) that attempts to bridge the gap between symbolic fix-point computation and recent approaches based on forward heuristic search. Concretely, we formalize the relationship between symbolic and dynamic programming nondeterministic planners, and then exploit such connection to propose a novel familyof planning algorithms that reasons over symbolic policies in a directed manner. By doing so, our proposal reasons over sets of states and executions in a succinct way (as done by symbolic planners) while biasing the reasoning with respect to the initial and goal states of the specific planning problem at hand (as done by heuristic planners). We show empirical results that prove this approach promising in settings where there is an intrinsic tension between plan efficiency and plan "robustness," a feature to be expected in nondeterministic domains.
Planning the Behaviour of Low-Cost Quadcopters for Surveillance Missions
Authors: Bernardini Sara , Fox Maria , Long Derek
Published: September 2022

Micro Aerial Vehicles (MAVs) are increasingly regarded as a valid low-cost alternative to UAVs and ground robots in surveillance missions and a number of other civil and military applications. Research on autonomous MAVs is still in its infancy and has focused almost exclusively on integrating control and computer vision techniques to achieve reliable autonomous flight. In this paper, we describe our approach to using automated planning in order to elicit high-level intelligent behaviour from autonomous MAVs engaged in surveillance applications. Planning offers effective tools to handle the unique challenges faced by MAVs that relate to their fast and unstable dynamics as well as their low endurance and small payload capabilities. We demonstrate our approach by focusing on the "Parrot AR.Drone2.0" quadcopter and Search-and-Tracking missions, which involve searching for a mobile target and tracking it after it is found.
Path Planning for Dexterous Mobility
Authors: Ruiken Dirk , Lanighan Michael , Grupen Roderic
Published: September 2022

In order to overcome a large variety of run-time constraints, robots are being designed to be more resourceful by incorporating more sensory and motor options for any given task. The added flexibility provides a basis for dexterous problem solving, but challenges planners by increasing the complexity of search. Moreover, the cost of functionally equivalent options can vary dramatically. In the worst case, naive approaches to planning avoid expensive actions until inexpensive options are explored exhaustively leading to poor overall search performance. We present a dexterous robot that introduces multiple types of locomotor actions with significant differences in cost and situational value and apply standard search techniques to demonstrate the additional challenges that arise in the context of dexterous mobility. Results highlight incentives, opportunities, and impact for overcoming these challenges. Additionally, we present a prototype for a path planner that uses environmental features to define an efficient set of subgoals for dexterous motion planning.
Improving the Design and Discovery of Dynamic Treatment Strategies Using Recent Results in Sequential Decision-Making
Authors: Pineau Joelle
Published: September 2022

In recent years, we have investigated algorithmic methods for automatically discovering and optimizing sequential treatments for chronic and life-threatening diseases. In this talk I will discuss two aspects of this work, first the problem of efficiently collecting data to learn good sequential treatment strategies, and second the problem of using data collected in multi-stage sequential trials to discover treatment strategies that are tailored to patient characteristics and timedependent outcomes. The methods will be illustrated using our recent work on learning adaptive neurostimulation policies for the treatment of epilepsy. Brief examples will be drawn from some of our other projects, including developing dynamic treatment regimes for mental illness, diabetes and cancer.
Interactive Relational Reinforcement Learning of Concept Semantics (Extended Abstract)
Authors: Nickles Matthias , Rettinger Achim
Published: September 2022

We propose a novel approach to the machine learning of formal word sense, learned in interaction with human users using a new form of Relational Reinforcement Learning. The envisaged main application area of our framework is humanmachine communication, where a software agent or robot needs to understand concepts used by human users (e.g., in Natural Language Processing, HCI or Information Retrieval). In contrast to traditional approaches to the machine learning and disambiguation of word meaning, our framework focuses on the interactive learning of concepts in a dialogue with the user and on the integration of rich formal background knowledge and dynamically adapted policy constraints in the learning process, which makes our approach suitable for dynamic interaction environments with varying word usage contexts.
Sequencing Operator Counts
Authors: Davies Toby , Pearce Adrian , Stuckey Peter , Lipovetzky Nir
Published: September 2022

Operator-counting is a recently developed framework for analysing and integrating many state-of-the-art heuristics for planning using Linear Programming. In cost-optimal planning only the objective value of these heuristics is traditionally used to guide the search. However the primal solution, i.e. the operator counts, contains useful information. We exploit this information using a SAT-based approach which given an operator-count, either finds a valid plan; or generates a generalized landmark constraint violated by that count. We show that these generalized landmarks can be used to encode the perfect heuristic, h*, as a Mixed Integer Program. Our most interesting experimental result is that finding or refuting a sequence for an operator-count is most often empirically efficient, enabling a novel and promising approach to planning based on Logic-Based Benders Decomposition (LBBD).
History-Based Controller Design and Optimization for Partially Observable MDPs
Authors: Kumar Akshat , Zilberstein Shlomo
Published: September 2022

Partially observable MDPs provide an elegant framework forsequential decision making. Finite-state controllers (FSCs) are often used to represent policies for infinite-horizon problems as they offer a compact representation, simple-to-execute plans, and adjustable tradeoff between computational complexityand policy size. We develop novel connections between optimizing FSCs for POMDPs and the dual linear programfor MDPs. Building on that, we present a dual mixed integer linear program (MIP) for optimizing FSCs. To assign well-defined meaning to FSC nodes as well as aid in policy search, we show how to associate history-based features with each FSC node. Using this representation, we address another challenging problem, that of iteratively deciding which nodes to add to FSC to get a better policy. Using an efficient off-the-shelf MIP solver, we show that this new approach can find compact near-optimal FSCs for severallarge benchmark domains, and is competitive with previous best approaches.
Indefinite-Horizon Reachability in Goal-DEC-POMDPs
Authors: Chatterjee Krishnendu , Chmelík Martin
Published: September 2022

DEC-POMDPs extend POMDPs to a multi-agent setting, where several agents operate in an uncertain environment independently to achieve a joint objective. DEC-POMDPs have been studied with finite-horizon and infinite-horizon discounted-sum objectives, and there exist solvers both for exact and approximate solutions. In this work we consider Goal-DEC-POMDPs, where given a set of target states, the objective is to ensure that the target set is reached with minimal cost.We consider the indefinite-horizon (infinite-horizon with either discounted-sum, or undiscounted-sum, where absorbing goal states have zero-cost) problem. We present a new and novel method to solve the problem that extends methods for finite-horizon DEC-POMDPs and the RTDP-Bel approach for POMDPs. We present experimental results on several examples, and show that our approach presents promising results.
More Shuttles, Less Cost: Energy Efficient Planning for Scalable High-Density Warehouse Environments
Authors: Hütter Christian
Published: September 2022

We propose planning strategies for a shuttle-based warehousing system. Within this system, goods are not only transported by, but also stored on shuttles. This allows the simultaneous motion of all goods without preparation time. We exploit these properties to improve both space- and energy efficiency compared to conventional storage systems while maintaining fast access to all goods. We present a framework to manage the shuttles in a very high density environment, allowing efficient in- and output, storage, and sequencing. The proposed framework is conflict-free, space- and energy efficient and its practical applicability is demonstrated in a simulative analysis based on a real-world problem. In our sample application holding 1950 shuttles we achieve storage densities of approximately 88% while maintaining efficient access to all goods.
Evaluation of Auction-Based Multi-Robot Routing by Parallel Simulation
Authors: Kishimoto Akihiro , Nagano Kiyohito
Published: September 2022

Auction methods are a promising approximation approach for distributed routing including multi-robot routing, where targets on a map need to be allocated to agents while a team objective is satisfied. While many algorithms based on sequential single-item (SSI) auctions have been presented, they are currently evaluated by serial simulation where agents serially calculate their bids on a single machine. We consider a scenario where a bidding algorithm incurs significant computational overhead due to on-demand calculations of the shortest distances on a road map. We evaluate the bidding algorithm under parallel simulations where agents perform bid calculations simultaneously on a parallel machine, and reveal that the algorithm suffers from severe synchronization overhead ignored by serial simulation. We also present the broadcasting and speculation techniques to alleviate such synchronization overhead. Our empirical results on multi-robot routing variants show that both techniques improve the efficiency of parallelization, and speculation achieves more significant improvement.
Submodular Function Maximization for Group Elevator Scheduling
Authors: Ramalingam Srikumar , Raghunathan Arvind , Nikovski Daniel
Published: September 2022

We propose a novel approach for group elevator scheduling by formulating it as the maximization of submodular function under a matroid constraint. In particular, we propose to model the total waiting time of passengers using a quadratic Boolean function. The unary and pairwise terms in the function denote the waiting time for single and pairwise allocation of passengers to elevators, respectively. We show that this objective function is submodular. The matroid constraints ensure that every passenger is allocated to exactly one elevator. We use a greedy algorithm to maximize the submodular objective function, and derive provable guarantees on the optimality of the solution. We tested our algorithm using Elevate 8, a commercial-grade elevator simulator that allows simulation with a wide range of elevator settings. We achieve significant improvement over the existing algorithms.
Tackling Large-Scale Home Health Care Delivery Problem with Uncertainty
Authors: Chen Cen , Rubinstein Zachary , Smith Stephen , Lau Hoong Chuin
Published: September 2022

In this work, we investigate a multi-period Home Health Care Scheduling Problem (HHCSP) under stochastic service and travel times. We first model the deterministic problem as an integer linear programming model that incorporates real-world requirements, such as time windows, continuity of care, workload fairness, inter-visit temporal dependencies. We then extend the model to cope with uncertainty in durations, by introducing chance constraints into the formulation. We propose efficient solution approaches, which provide quantifiable near-optimal solutions and further handle the uncertainties by employing a sampling-based strategy. We demonstrate the effectiveness of our proposed approaches on instances synthetically generated by real-world dataset for both deterministic and stochastic scenarios.
Performance Modelling of Planners from Homogeneous Problem Sets
Authors: De la Rosa Tomás , Cenamor Isabel , Fernández Fernando
Published: September 2022

Empirical performance models play an important role in the development of planning portfolios that make a per-domain or per-problem configuration of its search components. Even though such portfolios have shown their power when compared to other systems in current benchmarks, there is no clear evidence that they are capable to differentiate problems (instances) having similar input properties (in terms of objects, goals, etc.) but fairly different runtime for a given planner. In this paper we present a study of empirical performance models that are trained using problems having the same configuration, with the objective of guiding the models to recognize the underlying differences existing among homogeneous problems. In addition we propose a set of new features that boost the prediction capabilities under such scenarios. The results show that the learned models clearly performed over random classifiers, which reinforces the hypothesis that the selection of planners can be done on a per-instance basis when configuring a portfolio.
Hybrid Task Planning Grounded in Belief: Constructing Physical Copies of Simple Structures
Authors: Takahashi Takeshi , Lanighan Michael , Grupen Roderic
Published: September 2022

Symbolic planning methods have proved to be challenging in robotics due to partial observability and noise as well as unavoidable exceptions to rules that symbol semantics depend on. Often the symbols that a robot considers to support for planning are brittle, making them unsuited for even relatively short term use. Maturing probabilistic methods in robotics, however, are providing a sound basis for symbol grounding that supports using probabilistic distributions over symbolic entities as the basis for planning. In this paper, we describe a belief-space planner that stabilizes the semantics of feedback from the environment by actively interacting with a scene. When distributions over higher-level abstractions stabilize, powerful symbolic planning techniques can provide reliable guidance for problem solving. We present such an approach in a hybrid planning scheme that actively controls uncertainty and yields robust state estimation with bounds on uncertainty that can make effective use of powerful symbolic planning techniques. We illustrate the idea in a hybrid planner for autonomous construction tasks with a real robot system.
Embedding a Scheduler in Execution for a Planetary Rover
Authors: Chi Wayne , Chien Steve , Agrawal Jagriti , Rabideau Gregg , Benowitz Edward , Gaines Daniel , Fosse Elyse , Kuhn Stephen , Biehl James
Published: September 2022

Scheduling often takes place in the context of execution. This reality drives several key design decisions: (1) when to invoke (re) scheduling, (2) what to do when the scheduler is running, and (3) how to use the schedule to execute scheduled activities. We define these design decisions theoretically in the context of the embedded scheduler and practically in the context of the design of an embedded scheduler for a planetary rover. We use the concept of a commit window to enable execution to use the previously generated schedule while (re) scheduling. We define the concepts of fixed cadence, event driven, and hybrid scheduling to control invocation of (re) scheduling. We define the concept of flexible execution to enable execution of the generated schedule to be adaptive within the response cycle of the scheduler. We present empirical results from both synthetic and planetary rover scheduling and execution model data that documents the effectiveness of these techniques at enabling the scheduler to take advantage of execution opportunities to complete activities earlier.
The Factored Shortest Path Problem and Its Applications in Robotics
Authors: Wang Zhi , Cohen Liron , Koenig Sven , Kumar T. K. Satish
Published: September 2022

Many real-world combinatorial problems exhibit structure in the way in which their variables interact. Such structure can be exploited in the form of "factors" for representational as well as computational benefits. Factored representations are extensively used in probabilistic reasoning, constraint satisfaction, planning, and decision theory. In this paper, we formulate the factored shortest path problem (FSPP) on a collection of constraints interpreted as factors of a high-dimensional map. We show that the FSPP is not only a generalization of the regular shortest path problem but also particularly relevant to robotics. We develop factored-space heuristics for A* and prove that they are admissible and consistent. We provide experimental results on both random and handcrafted instances as well as on an example robotics domain to show that A* with factored-space heuristics outperforms A* with the Manhattan Distance heuristic in many cases.
On the Computational Complexity of Multi-Agent Pathfinding on Directed Graphs
Authors: Nebel Bernhard
Published: September 2022

The determination of the computational complexity of multi-agent pathfinding on directed graphs has been an open problem for many years. For undirected graphs, solvability can be decided in polynomial time, as has been shown already in the eighties. Further, recently it has been shown that a special case on directed graphs can be decided in polynomial time. In this paper, we show that the problem is NP-hard in the general case. In addition, some upper bounds are proven.
Integrating Acting, Planning, and Learning in Hierarchical Operational Models
Authors: Patra Sunandita , Mason James , Kumar Amit , Ghallab Malik , Traverso Paolo , Nau Dana
Published: September 2022

We present new planning and learning algorithms for RAE, the Refinement Acting Engine (Ghallab, Nau, and Traverso 2016). RAE uses hierarchical operational models to perform tasks in dynamically changing environments. Our planning procedure, UPOM, does a UCT-like search in the space of operational models in order to find a near optimal method to use for the task and context at hand. Our learning strategies acquire, from online acting experiences and/or simulated planning results, a mapping from decision contexts to method instances as well as a heuristic function to guide UPOM. Our experimental results show that UPOM and our learning strategies significantly improve RAE's performance in four test domains using two different metrics: efficiency and success ratio.
Guidelines for Action Space Definition in Reinforcement Learning-Based Traffic Signal Control Systems
Authors: Treca Maxime , Garbiso Julian , Barth Dominique
Published: September 2022

Previous works in the field of reinforcement learning applied to traffic signal control (RL-TSC) have focused on optimizing state and reward definitions, leaving the impact of the agent's action space definition largely unexplored. In this paper, we compare different types of TSC controllers – phase-based and step-based – in a simulated network featuring different traffic demand patterns in order to provide guidelines for optimally defining RL-TSC actions. Our results show that an agent's performance and convergence speed both increase with its interaction frequency with the environment. However, certain methods with lower observation frequencies – that can be achieved with realistic sensing technologies – have reasonably similar performance compared to higher frequency ones in all scenarios, and even outperform them under specific traffic conditions.
Admissible Heuristics for Multi-Objective Planning
Authors: Geißer Florian , Haslum Patrik , Thiébaux Sylvie , Trevizan Felipe
Published: September 2022

Planning problems of practical relevance commonly include multiple objectives that are difficult to weight a priori. Several heuristic search algorithms computing the Pareto front of non-dominated solutions have been proposed to handle these multi-objective (MO) planning problems. However, the design of informative admissible heuristics to guide these algorithms has not received the same level of attention. The standard practice is to use the so-called ideal point combination, which applies a single-objective heuristic to each objective independently, without capturing any of the trade-offs between them. This paper fills this gap: we extend several classes of classical planning heuristics to the multi-objective case, in such a way as to reflect the tradeoffs underlying the various objectives. We find that MO abstraction heuristics achieve overall the best performance, but that not every MO generalisation pays off.
Beyond Stars – Generalized Topologies for Decoupled Search
Authors: Gnad Daniel , Torralba Álvaro , Fišer Daniel
Published: September 2022

Decoupled search decomposes a classical planning task by partitioning its variables such that the dependencies between the resulting factors form a star topology. In this topology, a single center factor can interact arbitrarily with a set of leaf factors. The leaves, however, can interact with each other only indirectly via the center. In this work, we generalize this structural requirement and allow arbitrary topologies. The components must not overlap, i.e., each state variable is assigned to exactly one factor, but the interaction between factors is not restricted. We show how this generalization is connected to star topologies, which implies the correctness of decoupled search with this novel type of decomposition. We introduce factoring methods that automatically identify these topologies on a given planning task. Empirically, the generalized factorings lead to increased applicability of decoupled search on standard IPC benchmarks, as well as to superior performance compared to known factoring methods.
Compiling HTN Plan Verification Problems into HTN Planning Problems
Authors: Höller Daniel , Wichlacz Julia , Bercher Pascal , Behnke Gregor
Published: September 2022

Plan Verification is the task of deciding whether a sequence of actions is a solution for a given planning problem. In HTN planning, the task is computationally expensive and may be up to NP-hard. However, there are situations where it needs to be solved, e.g. when a solution is post-processed, in systems using approximation, or just to validate whether a planning system works correctly (e.g. for debugging or in a competition). There are verification systems based on translations to propositional logic and on techniques from parsing. Here we present a third approach and translate HTN plan verification problems into HTN planning problems. These can be solved using any HTN planning system. We collected a new benchmark set based on models and results of the 2020 International Planning Competition. Our evaluation shows that our compilation outperforms the approaches from the literature.
Simple Temporal Networks for Improvisational Teamwork
Authors: Morgan Malia , Schalkwyk Julianna , Wang Huaxiaoyue , Davalos Hannah , Martinez Ryan , Rohilla Vibha , Boerkoel James
Published: September 2022

When communication between teammates is limited to observations of each other's actions, agents may need to improvise to stay coordinated. Unfortunately, current methods inadequately capture the uncertainty introduced by a lack of direct communication. This paper augments existing frameworks to introduce Simple Temporal Networks for Improvisational Teamwork (STN-IT)—a formulation that captures both the temporal dependencies and uncertainties between agents who need to coordinate but lack reliable communication. We define the notion of strong controllability for STN-ITs, which establishes a static scheduling strategy for controllable agents that produces a consistent team schedule, as long as non-communicative teammates act within known problem constraints. We provide both an exact and approximate approach for finding strongly controllable schedules, empirically demonstrate the trade-offs between these approaches on benchmarks of STN-ITs, and show analytically that the exact method is correct.
Neural Network Action Policy Verification via Predicate Abstraction
Authors: Vinzent Marcel , Steinmetz Marcel , Hoffmann Jörg
Published: September 2022

Neural networks (NN) are an increasingly important representation of action policies. Verifying that such policies are safe is potentially very hard as it compounds the state space explosion with the difficulty of analyzing even single NN decision episodes. Here we address that challenge through abstract reachability analysis. We show how to compute predicate abstractions of the policy state space subgraph induced by fixing an NN action policy. A key sub-problem here is the computation of abstract state transitions that may be taken by the policy, which as we show can be tackled by connecting to off-the-shelf SMT solvers. We devise a range of algorithmic enhancements, leveraging relaxed tests to avoid costly calls to SMT. We empirically evaluate the resulting machinery on a collection of benchmarks. The results show that our enhancements are required for practicality, and that our approach can outperform two competing approaches based on explicit enumeration and bounded-length verification.
Conflict-Based Search for the Virtual Network Embedding Problem
Authors: Zheng Yi , Ravi Srivatsan , Kline Erik , Koenig Sven , Kumar T. K. Satish
Published: September 2022

In emerging network virtualization architectures, service providers will be able to create many heterogeneous virtual networks and offer customized end-to-end services by leasing shared resources from infrastructure providers. The Virtual Network Embedding (VNE) problem is central to such technology. It involves the proper allocation of CPU and bandwidth resources available in a physical substrate network to meet the demands of multiple virtual networks. Combinatorially, the VNE problem is a problem in resource management that is NP-hard to solve. In this paper, we present a novel version of the Conflict-Based Search (CBS) algorithm for solving the VNE problem. Our approach, called VNE-CBS, is inspired by the success of the CBS framework in the Multi-Agent Path Finding domain. We successfully address the unique challenges in applying the CBS framework to the VNE problem, and, in doing so, we pave the way for overcoming a crucial issue in Internet ossification via heuristic search methods. On the theoretical front, we show that, unlike many existing algorithms, our algorithm is complete and optimal. On the experimental front, we show that our algorithm significantly outperforms other state-of-the-art methods on various benchmark instances for both the offline and online versions of the VNE problem.
DOMA: Deep Smooth Trajectory Generation Learning for Real-Time UAV Motion Planning
Authors: Yu Jin , Piao Haiyin , Hou Yaqing , Mo Li , Yang Xin , Zhou Deyun
Published: September 2022

In this paper, we present a Deep Reinforcement Learning (DRL) based real-time smooth UAV motion planning method for solving catastrophic flight trajectory oscillation issues. By formalizing the original problem as a linear mixture of dual-objective optimization, a novel Deep smOoth Motion plAnning (DOMA) algorithm is proposed, which adopts an alternative layer-by-layer gradient descending optimization approach with the major gradient and the DOMA gradient applied separately. Afterward, the mix weight coefficient between the two objectives is also optimized adaptively. Experimental result reveals that the proposed DOMA algorithm outperforms baseline DRL-based UAV motion planning algorithms in terms of both learning efficiency and flight motion smoothness. Furthermore, the UAV safety issue induced by trajectory oscillation is also addressed.
Explaining Preference-Driven Schedules: The EXPRES Framework
Authors: Pozanco Alberto , Mosca Francesca , Zehtabi Parisa , Magazzeni Daniele , Kraus Sarit
Published: September 2022

Scheduling is the task of assigning a set of scarce resources distributed over time to a set of agents, who typically have preferences over the assignments they would like to get.
Due to the constrained nature of these problems, satisfying all agents' preferences often turns infeasible, which might lead to some agents not being happy with the resulting schedule.
Providing explanations has been shown to increase satisfaction and trust in solutions produced by AI tools.
However, explaining schedules poses some particular challenges such as problem interpretability (i.e., generating explanations from a huge and dense amount of information) and privacy preservation (i.e., generating explanations respecting the privacy of other agents involved).
In this paper we introduce the EXPRES framework, that can explain why a given preference was unsatisfied in a given optimal schedule. The EXPRES framework consists of (i) an explanation generator, that, based on a Mixed-Integer Linear Programming model, finds the best set of reasons that can explain an unsatisfied preference; and (ii) an explanation parser, which translates the generated explanations into human interpretable ones, while preserving agents' privacy.
Through simulations, we show that the explanation generator can efficiently scale to large instances.
Finally, through a set of user studies within J.P. Morgan, we show that employees preferred the explanations generated by EXPRES over human-generated ones when considering workforce scheduling scenarios.
Análisis de textiles arqueológicos desde la perspectiva del diseño. Caso de estudio: porta arpones
Authors: Bustamante Morales Marinella , Günther Buitano Patricia , Iglesias Daveggio Ana María
Published: September 2022

El artículo da cuenta de una investigación cuya finalidad fue visibilizar la Colección Chile Momia entre estudiosos e interesados en el área, y recoger aspectos a proyectar desde la perspectiva del Diseño. Se explora el modo de hacer, analizando la conformación textil de la pieza, estableciendo relaciones para reconocer su sentido e identidad, y así visibilizarla a través de la difusión de resultados. El proceso metodológico considera dos etapas: la primera orientada al análisis de los objetos que componen la colección, y la segunda establece relaciones para esbozar significados culturales en las piezas analizadas, con base en bibliografía especializada en textilería andina y entrevistas a expertos. Se presenta como caso de estudio un objeto textil funcional denominado porta arpones, cuya data corresponde aproximadamente a 1000-1470 d.C., durante el Periodo Intermedio Tardío. Su identificación cultural es prehispánica, específicamente la Cultura Arica. Desde una mirada analítica y con el fin de comprender su manufactura textil se procede al estudio y réplica de las técnicas de tejeduría que posee. En esa instancia, el objeto se transforma en evidencia de solución formal. El estudio permite concluir que en las manifestaciones de productos se reconocen tres hitos: existencia de una necesidad, proyectación para satisfacerla y elaboración, plasmando una respuesta; paralelo con el hacer del diseñador. A partir de la lectura realizada de las piezas arqueológicas, se concluye que su estudio aporta al diseño, sin embargo, debe excluir la apropiación, es decir, el traslado de un lenguaje iconográfico y/o morfológico. Ello es hacer caso omiso de su origen y significado, desconociendo su sentido semántico. Preservar y difundir tecnologías ancestrales aporta a nutrir al diseño, así como también a la artesanía aportando pertenencia, territorialidad y registro para las nuevas generaciones de profesionales que abordan el ámbito textil.
Fully automated coal quality control using digital twin material tracking and statistical model predictive control for yield optimization during production of semi soft coking- and power station coal
Authors: Coetzee B.J. , Sonnendecker PW.
Published: September 2022

The quality control of a two-stage coal washing process involves several complex components that need to be modelled accurately, to enable autonomous control of the process. The first objective is to develop a method to track the material through the washing process, while ensuring accurate washing prediction models are used. This was achieved through a digital twin model of the Grootegeluk 1 coal processing plant. The model is the amalgamation of manipulating and combining of data-sets from the plant historian, geological wash tables, and mining dispatch servers. This information is then used to control and set the processing medium densities of all 15 modules on the plant, 10 modules in the primary wash and 5 modules in the secondary wash. This controller has been successfully implemented and controlled the plant for 10 days.
Co-firing of high-ash discard coal and refuse-derived fuel - ash and gaseous emissions
Authors: Isaac K. , Bada S.O.
Published: September 2022

This research focuses on the co-firing of discard coal with refuse-derived fuel (RDF) to utilize this abundant resource in South Africa for energy generation and reduce the volume of waste disposed of at landfills. The potential of a coal with a high ash content (> 40%), which is a grade used in some power stations in South Africa, and its combustion compatibility with two different RDFs in terms of emission reductions has been established. Gaseous emissions and ash residues from the combustion and co-combustion of the coal, two different RDFs and coal/RDF blends of different proportion were analysed. One of the RDF samples contained mostly paper (PB) and the other mostly plastic (PL). Co-combustion ash from the discard coal and RDFs showed a decrease in chloride and alkali metal contents as the coal ratio in the blend increased. The slagging propensity of the co-fired blends was found to be very low, while the propensity for fouling decreased from high to medium for all the blends with < 75% RDF. Co-combustion of RDF with coal showed a decrease in SO2 emissions from 387 ppm (discard coal) to 50 ppm for the sample containing 25% coal discard plus 75% PL. A 15% PL to 85% coal blend also reduced NOx emissions from 145 ppm (100% PL) to 88 ppm. The lowest CO2 emission observed was 6000 ppm for the blend of 85% discard coal plus 15% PB. It was established that the most favourable fuel blend that can produce the lowest sulphur emissions if used for power generation is the 25% coal discard plus 75% PL sample.
Unusual neurological presentations resulting in diagnosis of lymphoma in three patients
Authors: Li Yuebing , McKee Zachary
Published: September 2022

Nervous system involvement affects up to one-third of patients with lymphoma, via a variety of mechanisms ranging from direct invasion, to demyelination, paraneoplastic processes, and treatment related complications. Nervous system involvement can manifest at any location and occur at any stage of lymphoma, often resulting in distinct and atypical patterns. Here we describe three patients, presenting each with motor predominant polyradiculoneuropathy and cranial neuropathy, transient encephalitis, and frontal gait dysfunction. Through further workup, all were diagnosed with lymphoma, with their neurological manifestations directly or indirectly related to the underlying lymphoma. Our study serves as an alert that in patients presenting with unusual neurological symptoms, lymphoma should be a consideration on the differential diagnosis.
FACS isolation of intestine-specific C. elegans cells v1
Authors: TP Williams Robert
Published: September 2022

This protocol describes the steps necessary for FACS isolation of C. elegans intestine cells. Section 1 contains general guidelines and considerations to be made before performing a FACS experiment. Sections 2-4 detail how to prepare cells for a specific developmental stage. Sections 5-7 detail how to prepare the FACS instrument for sorting and evaluating the purity of isolated cells. Section 8 describes how to handle cells once they have been isolated.
«Ed io che lasciai già l’ago e la gonna». Questioni di genere in Laura Battiferri
Authors: Cerrato Daniele
Published: September 2022

L’articolo studia Laura Battiferri e analizza alcuni aspetti del percorso vitale e letterario della poeta, come i suoi spostamenti da Urbino a Roma e poi a Firenze, la sua presenza nell’Accademia degli Intronati, il ruolo e l’influenza nell’opera del marito lo scultore Bartolomeo Ammannati, e lo scambio epistolare con Benedetto Varchi. Oltre alle sue capacità di inserirsi ed affermarsi nel contesto sociale e culturale del suo tempo, emergono chiaramente all’interno della sua produzione alcuni dei temi che caratterizzano il dibattito letterario-accademico della Querelle des Femmes.
Investigation of dimensional form errors of parts manufactured with an industrial 3-dimensional printer using ABS material
Authors: KIRAN Kadir , ŞEKERCİ Bahri , URGANCI Kemal Burak , DELİKANLI Yunus Emre , GEZGEN Baki
Published: September 2022

Eklemeli imalatta parça boyut hataları temel problemler arasında yerini almaktadır. Cihaz pozisyon hatalarına, parça çekmesine ya da büzülmesine ve STL dosya hatalarına bağlı olarak ortaya çıkan parça boyut hataları üretkenliği olumsuz etkilemektedir. Genel olarak, her bir cihaz-malzeme-imalat parametresi-geometri kombinasyonuna göre parçalarda farklı boyut hataları meydana gelebilmektedir. Dolayısıyla bu hataların hesaplanması ve analiz edilmesi son kullanıcılar ve cihaz imalatçıları açısından büyük önem taşımaktadır. Bu kapsamda adı geçen çalışmada endüstriyel bir üç boyutlu yazıcı olan Zaxe Z1 cihazı ile ABS malzemeli parça imalatında parça boyut hataları araştırılmıştır. İlk olarak, farklı boyutlarda daire, kare ve eşkenar üçgen geometrilerini üzerinde barındıran bir test parçası tasarlanmıştır. Ardından, test parçalarının imalat tablasındaki konumuna göre ortaya çıkan hataları incelemek amacıyla imalat tablasının farklı bölgelerine toplam 5 adet test parçası konumlandırılarak imalatı gerçekleştirilmiştir. Üçüncü adımda, bu test parçaları üzerinde yer alan tüm test geometrileri koordinat ölçme makinesi ile taranarak iki boyutlu profilleri elde edilmiştir. Dördüncü adımda ise, geliştirilen en küçük kareler tabanlı geometri uydurma algoritması ile taranan profillere geometri uydurma yapılmıştır. Son olarak da, uydurulan ve tasarlanan geometriler arasındaki profil toleransı değerleri hesaplanmıştır. Sonuçlar analiz edildiğinde, profil tolerans değerlerinin imalat tablasındaki konuma ve geometriye bağlı olarak değişkenlik sergilediği görülmüştür ve imal edilen tüm geometriler tasarlanan boyutlarından daha küçüktür. Başka bir ifadeyle tüm geometriler çekmeye maruz kalmıştır. Genel olarak bakıldığında, geometri boyutu arttıkça profil tolerans değerlerinde artış söz konusudur. Tüm geometriler için ortalama profil tolerans değeri 0.1987 mm olarak hesaplanmıştır. Bu değerin yarısı, yani ≈+0.1 mm, kadar tarama yollarının kaydırılması ile daha hassas geometriler elde edilebilir.
Effects of different salt concentrations on the germination in some turfgrass varieties used in landscape applications
Authors: YEŞİL Pervin , GÜZEL Mesut , ŞENGÜR Şeyma
Published: September 2022

This study was conducted in laboratory conditions to determine the response of some cool season turf grass species (Lolium perenne Caddieshack, Lolium multiflorum Jivet, Poa pratensis Evora, Festuca rubra Rassinante, Festuca arundinacea Starlet, Festuca ovina Ridu) to different salt doses during the germination period. In the study, 8 different NaCl doses, 0, 30, 60, 90, 120, 150, 180, 210 mM, were applied, germination rate (%), germination time (%), plumula length (cm), radicula length (cm) and vigor index values were examined. Because of the research, it was observed that the germination rate, plumula and radicula lengths increased at 30 mM concentrations and in general, significant damage occurred after the dose of 90 mM. Lolium perenne Caddieshack and Lolium multiflorum Jivet species showed the highest mean values and were less affected by increasing salt doses in all properties examined.