bluuebunny/crossref_metadata_2025 huggingface dataset:
Iterative Resource Allocation for Memory Intensive Parallel Search Algorithms (Extended Abstract)
Authors: Fukunaga Alex , Kishimoto Akihiro , Botea Adi
Published: November 2022

The increasing availability of “utility computing” resources such as clouds, grids, and massively parallel shared clusters can provide practically unlimited processing and memory capacity on demand, at some cost per unit of resource usage. This requires a new perspective in the design and evaluation of parallel search algorithms. Previous work in parallel search implicitly assumed ownership of a cluster with a static amount of CPU cores and RAM, and emphasized wallclock runtime. With utility computing resources, trade-offs between performance and monetary costs must be considered. This paper considers dynamically increasing the usage of utility computing resources until a problem is solved. Efficient resource allocation policies are analyzed in comparison with an optimal allocation strategy. We evaluate our iterative allocation strategy by applying it to the HDA* parallel search algorithm. The experimental results validate our theoretical predictions. They show that, in practice, the costs incurred by iterative allocation are reasonably close to an optimal (but a priori unknown) policy, and are significantly better than the worst-case analytical bounds.
Automatic Move Pruning Revisited
Authors: Burch Neil , Holte Robert
Published: November 2022

In this paper we show that the move pruning method we presented at SoCS last year sometimes prunes all the least-cost paths from one state to another. We present two examples exhibiting this erroneous behaviour--a simple, artificial example and a slightly more complex example that arose in last year's experiments. We then formally prove that a simple modification to our move pruning method makes it "safe," i.e., it will never prune all the least-cost paths between a pair of states. Finally, we present the results of rerunning last year's experiments with this provably safe version of move pruning and show that last year's main conclusions still hold, namely: (1) in domains where there are short redundant sequences move pruning produces substantial speedups in depth-first search, and (2) in domains where the only short redundant sequences are 2-cycles, move pruning is faster than parent pruning by a factor of two or more.
Meta-Agent Conflict-Based Search For Optimal Multi-Agent Path Finding
Authors: Sharon Guni , Stern Roni , Felner Ariel , Sturtevant Nathan
Published: November 2022

The task in the multi-agent path finding problem (MAPF) isto find paths for multiple agents, each with a different startand goal position, such that agents do not collide. It is possibleto solve this problem optimally with algorithms that arebased on the A* algorithm. Recently, we proposed an alternativealgorithm called Conflict-Based Search (CBS) (Sharonet al. 2012), which was shown to outperform the A*-basedalgorithms in some cases. CBS is a two-level algorithm. Atthe high level, a search is performed on a tree based on conflictsbetween agents. At the low level, a search is performedonly for a single agent at a time. While in some cases CBSis very efficient, in other cases it is worse than A*-based algorithms.This paper focuses on the latter case by generalizingCBS to Meta-Agent CBS (MA-CBS). The main idea isto couple groups of agents into meta-agents if the number ofinternal conflicts between them exceeds a given bound. MACBSacts as a framework that can run on top of any completeMAPF solver. We analyze our new approach and provideexperimental results demonstrating that it outperforms basicCBS and other A*-based optimal solvers in many cases.
Learning Heuristic Functions Faster by Using Predicted Solution Costs
Authors: Lelis Levi , Jabbari Arfaee Shahab , Zilles Sandra , Holte Robert
Published: November 2022

Jabbari Arfaee, Zilles, and Holte presented the bootstrap learning system, a system that learns strong heuristic functions for state-space problems. They showed that IDA* with a bootstrap heuristic is able to quickly find near-optimal solutions in several problem domains. However, the process the bootstrap method uses to learn heuristic functions is time-consuming: it is on the order of days. In this paper we present a learning system that uses an approximation method instead of an exact one to generate the training set required to learn heuristics. We showed recently that solution costs can often be quickly and accurately predicted without having to actually find a solution. In this paper we apply this idea to speedup the process of learning heuristics. In contrast with other learning approaches that use search algorithms to solve problem instances to generate the training set, our system uses a solution cost predictor. We reduce the time required to learn strong heuristics from days to minutes on the domains tested.
Evolving Instance Specific Algorithm Configuration
Authors: Malitsky Yuri , Mehta Deepak , O'Sullivan Barry
Published: November 2022

Combinatorial problems are ubiquitous in artificial intelligence and related areas. While there has been a significant amount of research into the design and implementation of solvers for combinatorial problems, it is well-known that there is still no single solver that performs best across a broad set of problem types and domains.This has motivated the development of portfolios of solvers. A portfolio typically comprises either many different solvers, instances of the same solver tuned in different ways, or some combination of these. However, current approaches to portfolio design take a static view of the process.Specifically, the design of the portfolio is determined offline, and then deployed in some setting.In this paper we propose an approach to evolving the portfolio over time based on the problems instances that it encounters.We study several challenges raised by such a dynamic approach, such as how to re-tune the portfolio over time.Our empirical results demonstrate that our evolving portfolio approach significantly out-performed the standard static approach in the case when the type of instances observed change over time.
Reconnecting with the Ideal Tree: An Alternative to Heuristic Learning in Real-Time Search
Authors: Rivera Nicolas , Illanes Leon , Baier Jorge , Hernandez Carlos
Published: November 2022

In this paper, we present a conceptually simple, easy-to-implement real-time search algorithm suitable for a priori partially known environments. Instead of performing a series of searches towards the goal, like most Real-Time Heuristic Search Algorithms do, our algorithm follows the arcs of a tree T rooted in the goal state that is built initially using the heuristic h. When the agent observes that an arc in the tree cannot be traversed in the actual environment, it removes such an arc from T and our algorithm carries out a reconnection search whose objective is to find a path between the current state and any node in T. The reconnection search need not be guided by $h$, since the search objective is not to encounter the goal. Furthermore, h need not be updated. We implemented versions of our algorithm that utilize various blind search algorithms for reconnection. We show experimentally that these implementations significantly outperform state-of-the-art real-time heuristic search algorithms for the task of pathfinding in grids. In grids, our algorithms, which do not incorporate any geometrical knowledge, naturally behaves similarly to a bug algorithm, moving around obstacles, and never returning to areas that have been visited in the past. In addition, we prove theoretical properties of the algorithm.
The Hierarchy in Grid Graphs (Extended Abstract)
Authors: Storandt Sabine
Published: November 2022

Many speed-up techniques developed for accelerating the computation of shortest paths in road networks, like reach or contraction hierarchies, are based on the property that some streets are ’more important’ than others, e.g. on long routes the usage of an interstate is almost inevitable. In grids there is no obvious hierarchy among the edges, especially if the costs are uniform. Nevertheless we will show that contraction hierarchies can be applied to grid graphs as well. We will point out interesting connections to speed-up techniques shaped for routing on grids, like swamp hierarchies and jump points, and provide experimental results for game maps, mazes, random grids and rooms.
Finding Bounded Suboptimal Multi-Agent Path Planning Solutions Using Increasing Cost Tree Search (Extended Abstract)
Authors: Aljalaud Faten , Sturtevant Nathan
Published: November 2022

The Increasing Cost Tree Search (ICTS) algorithm is used to produce optimal solutions to the multi-agent path finding problem (MAPF). In this problem, multiple agents are trying to reach their goals without conflicting with each other, while minimizing the total cost of the paths. ICTS has been shown to be very effective in finding optimal solutions. In this paper we consider the problem of finding solutions with bounded suboptimality by changing the order in which ICTS searches its increasing cost tree. With a variety of strategies, we are unable to consistently and significantly reduce the cost of ICTS. Further experimentation suggests why significantly more work is needed to modify ICTS to find suboptimal solutions.
Anytime Tree-Restoring Weighted A* Graph Search
Authors: Gochev Kalin , Safonova Alla , Likhachev Maxim
Published: November 2022

Incremental graph search methods reuse information from previous searches in order to minimize redundant computation and to find solutions to series of similar search queries much faster than it is possible by solving each query from scratch. In this work, we present a simple, but very effective, technique for performing incremental weighted A* graph search in an anytime fashion. On the theoretical side, we show that our anytime incremental algorithm preserves the strong theoretical guarantees provided by the weighted A* algorithm, such as completeness and bounds on solution cost sub-optimality. We also show that our algorithm can handle a variety of changes to the underlying graph, such as both increasing and decreasing edge costs, and changes in the heuristic. On the experimental side, we demonstrate the effectiveness of our algorithm in the context of (x, y, z, yaw) navigation planning for an unmanned aerial vehicle and compare our algorithm to popular incremental and anytime graph search algorithms.
Estimating Search Tree Size with Duplicate Detection
Authors: Lelis Levi , Stern Roni , Sturtevant Nathan
Published: November 2022

In this paper we introduce Stratified Sampling with Duplicate Detection (SSDD), an algorithm for estimating the number of state expansions performed by heuristic search algorithms seeking solutions in state spaces represented by undirected graphs. SSDD is general and can be applied to estimate other state-space properties. We test SSDD on two tasks: (i) prediction of the number of A* expansions in a given f-layer when using a consistent heuristic function, and (ii) prediction of the state-space radius. SSDD has the asymptotic guarantee of producing perfect estimates in both tasks. Our empirical results show that in task (i) SSDD produces good estimates in all four domains tested, being in most cases orders of magnitude more accurate than a competing scheme, and in task (ii) SSDD quickly produces accurate estimates of the radii of the 4x4 Sliding-Tile Puzzle and the 3x3x3 Rubik's Cube.
Reaching the Goal in Real-Time Heuristic Search: Scrubbing Behavior is Unavoidable
Authors: Sturtevant Nathan , Bulitko Vadim
Published: November 2022

Real-time agent-centered heuristic search is a well-studied problem where an agent that can only reason locally about the world must travel to a goal location using bounded computation and memory at each step. Many algorithms have been proposed for this problem, and theoretical results have also been derived for the worst-case performance. Assuming sufficiently poor tie-breaking, among other conditions, we derive theoretical best-case bounds for reaching the goal using LRTA*, a canonical example of a real-time agent-centered heuristic search algorithm. We show that the number of steps required to reach the goal can grow asymptotically faster than the state space, resulting in a "scrubbing" when the agent repeatedly visits the same state. This theoretical result, supported by experimental data, encourages recent work in the field that uses novel tie-breaking schemas and/or perform different types of learning.
The Application of Pareto Local Search to the Single-Objective Quadratic Assignment Problem
Authors: Alsheddy Abdullah
Published: November 2022

This (short) paper presents the employment of Pareto optimality as a strategy to help (single-objective) local search escaping local optima. Instead of local search, Pareto local search is applied to solve the quadratic assignment problem which is multi-objectivized by adding a helper objective. The additional objective is defined as a function of the primary one with augmented penalties that are dynamically updated.
Dynamic Redeployment to Counter Congestion or Starvation in Vehicle Sharing Systems
Authors: Ghosh Supriyo , Varakantham Pradeep , Adulyasak Yossiri , Jaillet Patrick
Published: November 2022

Vehicle sharing (ex: bike sharing, car sharing) systems, an attractive alternative of private transportation, are widely adopted in major cities around the world. In vehicle-sharing systems, base stations (ex: docking stations for bikes) are strategically placed throughout a city and each of the base stations contain a pre-determined number of vehicles at the beginning of each day. Due to the stochastic and individualistic movement of customers, there is typically either congestion (more than required) or starvation (fewer than required) of vehicles at certain base stations, which causes a significant loss in demand. We propose to dynamically redeploy idle vehicles using carriers so as to minimize lost demand or alternatively maximize revenue for the vehicle sharing company. To that end, we contribute an optimization formulation to jointly address the redeployment (of vehicles) and routing (of carriers) problems and provide two approaches that rely on decomposability and abstraction of problem domains to reduce the computation time significantly.
Moving Target Search with Subgoal Graphs
Authors: Nussbaum Doron , Yörükçü Alper
Published: November 2022

Moving Target Search (MTS) is a dynamic path planning problem, where an agent is trying to reach a moving entity with a minimum path cost. Problems of this nature can be found in video games and dynamic robotics, which require fast processing time (real time). In this work, we introduce a new algorithm for this problem - the Moving Target Search with Subgoal Graphs (MTSub). MTSub is based on environment abstraction and uses Subgoal Graphs to speed up the searches for a minimal cost route to the target. The algorithm is optimal with respect to the knowledge that the agent has during the search. Experimental results show that MTSub can be used in real-time applications (e.g., applications requiring 5 microseconds response time per step). The experiments compared MTSub to G-FRA*, which is the best known dynamic algorithm so far, showing that MTSub is up to 29 times faster in average time per step, and up to 186 times faster in maximum time per step.
Tight Bounds for HTN Planning with Task Insertion (Extended Abstract)
Authors: Alford Ron , Bercher Pascal , Aha David
Published: November 2022

Hierarchical Task Network (HTN) planning with task insertion (TIHTN planning) is a variant of HTN planning. In HTN planning, the only means to alter task networks is to decompose compound tasks. In TIHTN planning, tasks may also be inserted directly. In this paper we provide tight complexity bounds for TIHTN planning along two axis: whether variables are allowed and whether methods must be totally ordered.
Exploring the Synergy between Two Modular Learning Techniques for Automated Planning
Authors: Fuentetaja Raquel , Chrpa Lukáŝ , McCluskey Thomas , Vallati Mauro
Published: November 2022

In the last decade the emphasis on improving the operational performance of domain independent automated planners has been in developing complex techniques which merge a range of different strategies. This quest for operational advantage, driven by the regular international planning competitions, has not made it easy to study, understand and predict what combinations of techniques will have what effect on a planner’s behaviour in a particular application domain. In this paper, we consider two machine learning techniques for planner performance improvement, and exploit a modular approach to their combination in order to facilitate the analysis of the impact of each individual component. We believe this can contribute to the development of more transparent planning engines, which are designed using modular, interchangeable, and well-founded components. Specifically, we combined two previously unrelated learning techniques, entanglements and relational decision trees, to guide a “vanilla” search algorithm. We report on a large experimental analysis which demonstrates the effectiveness of the approach in terms of performance improvements, resulting in a very competitive planning configuration despite the use of a more modular and transparent architecture. This gives insights on the strengths and weaknesses of the considered approaches, that will help their future exploitation.
Computing Plans with Control Flow and Procedures Using a Classical Planner
Authors: Jimenez Celorrio Sergio , Jonsson Anders
Published: November 2022

We propose a compilation that enhances a given classical planning task to compute plans that contain control flow and procedure calls. Control flow instructions and procedures allow us to generate compact and general solutions able to solve planning tasks for which multiple unit tests are defined. The paper analyzes the relation between classical planning and structured programming with unit tests and shows how to exploit this relation in a classical planning compilation. In experiments, we evaluate the empirical performance of the compilation using an off-the-shelf classical planner and show that we can compress classical planning solutions and that these compressed solutions can solve planning tasks with multiple tests.
Improved Pattern Selection for PDB Heuristics in Classical Planning (Extended Abstract)
Authors: Scherrer Sascha , Pommerening Florian , Wehrle Martin
Published: November 2022

The iPDB approach selects patterns by a local search in the space of pattern collections. This search often gets stuck in local optima, which limits the quality of the resulting heuristic. In this research abstract, we report on current progress to tackle this problem. We investigate variable neighborhood search with encouraging experimental results.
Empowering Mini-Bucket in Anytime Heuristic Search with Look-Ahead: Preliminary Evaluation
Authors: Lam William , Kask Kalev , Dechter Rina
Published: November 2022

The paper explores the potential of look-ahead methods within the context of AND/OR search in graphical models using the Mini-Bucket heuristic for combinatorial optimization tasks (e.g., weighted CSPS or MAP inference). We study how these methods can be used to compensate for the approximation error of the initially generated Mini-Bucket heuristics, within the context of anytime Branch-And-Bound search.
Type System Based Rational Lazy IDA*
Authors: Betzalel Oded , Felner Ariel , Shimony Solomon
Published: November 2022

Meta-reasoning can improve numerous search algorithms, but necessitates collection of statistics to be used as probability distributions, and involves restrictive meta-reasoning assumptions. The recently suggested scheme of type systems in search algorithms is used in this paper for collecting these statistics. The statistics are then used to better estimate the unknown quantity of expected regret of computing a heuristic in Rational Lazy IDA* (RLIDA*), and also facilitate a second improvement due to relaxing one of the unrealistic meta-reasoning assumptions in RLIDA*.
Abstracts of Papers Presented at SoCS 2016 in the Previously Published Paper Track
Authors: Baier Jorge , Botea Adi
Published: November 2022

This document gathers the abstracts for the papers that were presented as part of the Previously Published Paper Track.
Dynamic Potential Search — A New Bounded Suboptimal Search
Authors: Gilon Daniel , Felner Ariel , Stern Roni
Published: November 2022

Potential Search (PS) is an algorithm that is designed to solve bounded cost search problems. In this paper, we modify PS to work within the framework of bounded suboptimal search and introduce Dynamic Potential Search (DPS). DPS uses the idea of PS but modifies the bound to be the product of the minimal f-value in OPEN and the required suboptimal bound. We study DPS and its attributes. We then experimentally compare DPS to WA* and to EES on a variety of domains and study parameters that affect the behavior of these algorithms.In general we show that in domains with unit edge costs (e.g., many standard benchmarks) DPS significantly outperforms WA* and EES but there are exceptions.
Generalizing JPS Symmetry Detection: Canonical Orderings on Graphs
Authors: Sturtevant Nathan
Published: November 2022

The Jump Point Search (JPS) algorithm is designed explicitly for search on grids; it uses grid-specific properties to reduce symmetry and provide faster optimal search without pre-computation. Recent work has broken the algorithm down into three components: a best-first search, a canonical ordering of states, and a jumping policy. This paper shows how a canonical ordering can be built on general graphs and used in a similar manner to the canonical ordering of JPS. This approach is able to significantly reduce the number of states generated by an A* search, but more work is needed to optimize and fully characterize the correctness of the approach.
Compliant Conditions for Polynomial Time Approximation of Operator Counts
Authors: Chakraborti Tathagata , Sreedharan Sarath , Sengupta Sailik , Kumar T. K. Satish , Kambhampati Subbarao
Published: November 2022

In this brief abstract, we develop a computationally simpler version of the operator count heuristic for a particular class of domains. The contribution of this abstract is thus threefold, we (1) propose an efficient closed form approximation to the operator count heuristic; (2) leverage compressed sensing techniques to obtain an integer approximation in polynomial time; and (3) discuss the relationship of the proposed formulation to existing heuristics and investigate properties of domains where such approaches are useful.
Calculating the Number of Order-6 Magic Squares with Modular Lifting
Authors: Croy Skylar , Hansen Jeremy , McQuillan Daniel
Published: November 2022

There is no known general formula to calculate the total number of magic squares of a given order. However, using various methods, the number of magic squares has been calculated for orders smaller than 6. In this work we describe an approach to bounding the computational complexity of enumerating order-6 squares and provide a related method to approximate the number of such squares.
Modifying Optimal SAT-Based Approach to Multi-Agent Path-Finding Problem to Suboptimal Variants
Authors: Surynek Pavel , Felner Ariel , Stern Roni , Boyarski Eli
Published: November 2022

In multi-agent path finding (MAPF) the task is to find non-conflicting paths for multiple agents. Recently, a SAT-based approach was developed to solve this problem and proved beneficial in many cases when compared to other search-based solvers. In this paper, we introduce SAT-based unbounded- and bounded-suboptimal algorithms and compare them to relevant search-based algorithms.
Interval Based Relaxation Heuristics for Numeric Planning with Action Costs
Authors: Aldinger Johannes , Nebel Bernhard
Published: November 2022

We adapt the relaxation heuristics hmax, hadd and hFF to interval based numeric relaxation frameworks, combining them with two different relaxation techniques and with two different search techniques. In contrast to previous approaches, the heuristics presented here are not limited to a subset of numeric planning and support action costs.
Cost-Based Heuristics and Node Re-Expansions across the Phase Transition
Authors: Cohen Eldan , Beck J.
Published: November 2022

Recent work aimed at developing a deeper understanding of suboptimal heuristic search has demonstrated that the use of a cost-based heuristic function in the presence of large operator cost ratio and the decision to allow re-opening of visited nodes can have a significant effect on search effort. In parallel research, phase transitions in problem solubility have proved useful in the study of problem difficulty for many computational problems and have recently been shown to exist in heuristic search problems. In this paper, we show that the impact on search effort associated with a larger operator cost ratio and the number of node re-expansions is concentrated almost entirely in the phase transition region. Combined with previous work connecting local minima in the search space with such behavior, these observations lead us to hypothesize a relationship between the phase transition and the existence of local minima.
Better Orders for Saturated Cost Partitioning in Optimal Classical Planning
Authors: Seipp Jendrik
Published: November 2022

Cost partitioning is a general method for adding multiple heuristic values admissibly. In the setting of optimal classical planning, saturated cost partitioning has recently been shown to be the cost partitioning algorithm of choice for pattern database heuristics found by hill climbing, systematic pattern database heuristics and Cartesian abstraction heuristics. To evaluate the synergy of the three heuristic types, we compute the saturated cost partitioning over the combined sets of heuristics and observe that the resulting heuristic is outperformed by the heuristic that simply maximizes over the three saturated cost partitioning heuristics computed separately for each heuristic type. Our new algorithm for choosing the orders in which saturated cost partitioning considers the heuristics allows us to compute heuristics outperforming not only the maximizing heuristic but even state-of-the-art planners.
Symbolic Leaf Representation in Decoupled Search
Authors: Gnad Daniel , Torralba Álvaro , Hoffmann Jörg
Published: November 2022

Star-Topology Decoupled Search has recently been introduced in classical planning. It splits the planning task into a set of components whose dependencies take a star structure, where one center component interacts with possibly many leaf components. Here we address a weakness of decoupled search, namely large leaf components, whose state space is enumerated explicitly. We propose a symbolic representation of the leaf state spaces via decision diagrams, which can be dramatically smaller, and also more runtime efficient. We further introduce a symbolic version of the LM-cut heuristic, that nicely connects to our new leaf representation. We show empirically that the symbolic representation indeed pays off when the leaf components are large.
Block-Parallel IDA* for GPUs
Authors: Horie Satoru , Fukunaga Alex
Published: November 2022

We investigate GPU-based parallelization of Iterative-Deepening A* (IDA*). We show that straightforward thread-based parallelization techniques which were previously proposed for massively parallel SIMD processors perform poorly due to warp divergence and load imbalance. We propose Block-Parallel IDA* (BPIDA*), which assigns the search of a subtree to a block (a group of threads with access to fast shared memory) rather than a thread. On the 15-puzzle, BPIDA* on a NVIDIA GRID K520 with 1536 CUDA cores achieves a speedup of 4.98 compared to a highly optimized sequential IDA* implementation on a Xeon E5-2670 core.
k-Nearest Neighbors on Road Networks: Euclidean Heuristic Revisited
Authors: Abeywickrama Tenindra , Cheema Muhammad , Taniar David
Published: November 2022

In the age of smartphones, finding the nearest points of interest (POIs) is a highly relevant problem. A popular way to solve this is to use a k Nearest Neighbor (kNN) query to retrieve POIs by their road network distances from a query location. However, we find that existing kNN methods have not been carefully compared. We present a detailed and fair experimental study of the state-of-the-art, documenting the many insights gleaned along the way. Notably, a long overlooked Euclidean distance heuristic is often the best performing method by a wide margin. We have also released all code as open-source for readers to reproduce experiments and easily add methods or queries to the testbed for new studies.
Fast Near-Optimal Path Planning on State Lattices with Subgoal Graphs
Authors: Uras Tansel , Koenig Sven
Published: November 2022

Subgoal graphs can be constructed on top of graphs during a preprocessing phase to speed-up shortest path queries. They have an undominated query-time/memory trade-off in the Grid-Based Path Planning Competitions. While grids are useful for path planning, other kinds of graphs, such as state lattices, have to be used for motion planning. While state lattices are regular graphs like grids, subgoal graphs improve query times by a much smaller factor on state lattices than on grids. In this paper, we present a new version of subgoal graphs that forfeits its optimality guarantee for smaller query times. It guarantees completeness, and our experimental results on state lattices suggest that it can find paths that are close to optimal.
Bounded Suboptimal Game Tree Search
Authors: Atzmon Dor , Stern Roni , Saffidine Abdallah
Published: November 2022

Finding the minimax value of a game is an important problem in a variety of fields, including game theory, decision theory, statistics, philosophy, economics, robotics, and security. Classical algorithms such as the Minimax algorithm can be used to find the minimax value, but require iterating over the entire game tree, which is in many cases too large. Alpha-Beta pruning identifies portions of the game tree that are not necessary for finding the minimax value, but in many cases the remaining part of the game tree is still too large to search in reasonable time. For such cases, we propose a class of algorithms that accepts a parameter e and returns a value that is guaranteed to be at most e away from the true minimax value. We lay the theoretical foundation for building such algorithms and present one such algorithm based on Alpha-Beta. Experimentally, we show that our algorithm allows controlling this runtime/solution quality tradeoff effectively.
Forward Search in Contraction Hierarchies
Authors: Harabor Daniel , Stuckey Peter
Published: November 2022

Contraction hierarchies are graph-based data structure developed to speed up shortest path search in road networks. Built during an offline pre-processing step, contraction hierarchies are always paired with an online query algorithm which is a variation on bi-directional Dijkstra search. Though effective and highly popular this combination can sometimes be difficult to extend, for example in order to leverage goal-directed heuristics or other forward-driven pruning techniques. In this paper we deconstruct the bi-directional query algorithm of contraction hierarchies and derive a new algorithmic schema which is compatible with standard uni-directional or bi-directional search. We then develop a variety of new uni-directional query algorithms to find optimal paths in contraction hierarchies. These are based on the combination of A* search and Geometric Containers, a well known and successful edge-pruning technique. Empirical results show that our approach can improve search times by an order of magnitude vs bi-directional Dijkstra, albeit at the cost of additional memory and pre-processing time.
Stubborn Sets Pruning for Privacy Preserving Planning
Authors: Schulte Tim
Published: November 2022

We adapt a partial order reduction technique based on stubborn sets to the setting of privacy-preserving multi-agent planning. We prove that the presented approach preserves optimality and show experimentally that it can significantly improve search performance on some domains.
ASSESSMENT OF SUSTAINABLE GREEN CONCRETE PROPERTIES USING RECYCLED PLASTIC WASTE AS REPLACEMENT FOR FINE AGGREGATE USING MACHINE LEARNING TECHNIQUE
Authors: Sau Debasis , Hazra Tumpa , Shiuly Amit
Published: November 2022

The use of waste plastic as a replacement for natural aggregates in cement composites can solve the problem of the disposal of waste plastics sustainably. This study aims to investigate and compare the impact of replacing fine natural aggregate with recycled aggregates made up of polyethylene (PE) in M30 grade of concrete by analyzing the physical and mechanical properties of both fresh and hardened concrete in terms of workability, dry and fresh unit weight, 28-day compressive strength, flexural strength, split tensile strength, and ultrasonic pulse velocity. Nine concrete mixtures containing PE was prepared as a partial volumetric replacement for fine aggregate with substitution levels of 0%, 5%, 10%, 15%, 20%, 25%, 30%, 35% and 40%. Due to the application of superplasticizers, the workability of concrete containing recycled plastic has improved. The fresh and dry unit weight values of the PE-based concrete decreased by 8.16% and 8.6%, respectively, with the increase in PE aggregate and can therefore be considered lightweight concrete. The compressive strength of concrete at various ages is reduced as the quantity of plastic in concrete increases. As the PE replacement ratio in concrete increased, the flexural strength and split tensile strength also declined. Up to 10% replacement gives acceptable physical and mechanical properties of concrete for structural purposes. In this study, artificial neural network (ANN) was used to predict the fresh and hardened properties of waste plastic aggregate-based concrete, and it was discovered that it can predict concrete qualities with good accuracy (R2 = 0.99).
Hydration and mixture design of calcined clay blended cements: review by the RILEM TC 282-CCL
Authors: Zunino Franco , Dhandapani Yuvaraj , Ben Haha Mohsen , Skibsted Jørgen , Joseph Shiju , Krishnan Sreejith , Parashar Anuj , Juenger Maria C. G. , Hanein Theodore , Bernal Susan A. , Scrivener Karen L. , Avet François
Published: November 2022

The RILEM technical committee 282-CCL: Calcined Clays as Supplementary Cementitious Materials, investigates all the aspects related to calcined clays, from clay exploration and characterization to calcination process, hydration reactions and concrete properties. This white paper focuses on the hydration mechanisms of calcined clay-blended Portland cements, covering both 1:1 and 2:1 calcined clays. The pozzolanic reaction of calcined clay is detailed, and the main reaction products are described. The differences observed depending on the clay type are also discussed, as well as the potential influence of the secondary phases present in calcined clay. The factors controlling and limiting the reaction of calcined clay are investigated, evidencing the role of porosity saturation and refinement of the microstructure. The complete characterisation of the hydration of calcined clay cements is made possible by the determination of the reaction degree of calcined clay. Several methods are compared to estimate the extent of calcined clay reaction. The influence of clinker and limestone mineralogy are also discussed. Finally, guidelines for optimising the mixture design of calcined clay blended cements are provided, with special attention to sulphate adjustment and clinker factor.
SEVGİ EKSENLİ DİNDARLIĞIN İMKÂNI ÜZERİNE
Authors: KARACA Faruk , GÜZEL Fahri
Published: November 2022

İnsan-Allah ilişkisi, Din Psikolojisinin ele aldığı temel konulardan biri olarak karşımıza çıkmaktadır. İnanç, ibadet, dua şeklinde İnsandan Allah’a doğru arz edilen iletişim, Allah’tan vahiy, duanın kabulü şeklinde cevap bulmaktadır. Dinin Allah ile girilen ruhsal ilişki olarak tanımlanması, beraberinde bu özel ilişkinin “mahiyeti” ve dayandığı “psikolojik temellerin” neler olduğu sorusunu getirmektedir. Dini hayatı besleyici duygusal faktörler arasında daha fazla etkin olan sevgi duygusunun konumu ise dini psikolojik perspektiften incelemeye çalışan araştırmacıları meşgul eden sorulardan biri olmuştur. Ancak dini hayatı besleme konusunda büyük potansiyele sahip olsa da, sevgi kavramının oldukça geniş, karmaşık ve muğlak doğası, özellikle psikoloji kaynaklarında neredeyse hiç araştırmaya konu edilmemesine yol açmıştır. İnsan Allah ilişkisinin sevgi temelinde gerçekleşmesinin şartları ve sonuçlarının ele alındığı bu çalışmada öncelikle kavramsal çerçevede sevgi, sevgi objeleri ve Kur’an-ı Kerim’de sevgi kavramının ele alınış biçimi değerlendirilmiş daha sonra Allah sevgisi ve bu sevginin boyutları irdelenmeye çalışılmıştır.
The Need for Monitoring and Assessment of Legal Aid Quality in South Africa
Authors: Holness Dave
Published: November 2022

Legal aid is needed in South Africa as one mechanism for poor South Africans to realise their legal rights and to use the law as a vehicle for positive social change in a grossly unequal society in which deep poverty is rife. However, simply having a legal aid service provider is insufficient if the quality of such services is not satisfactory. But how can high quality legal services be ensured? This paper considers how different forms of legal aid service provision can be effectively monitored and assessed to ensure that satisfactory standards of legal aid work are delivered. Categories of "legal aid" (broadly construed) which are considered are legal NGOs, including university law clinics, the state's Legal Aid South Africa telephonic advice, and pro bono work by private lawyers. Separate research has focussed on the need for much improved coordination between legal service providers to promote co-operation among legal aid services. The next step is to ensure that such coordination leads to quality services and promoting quality control mechanisms which are appropriate and which can be considered best practice. This paper analyses and discusses this next step. If legal aid is not of an adequate standard or quality assurance is not in place, the legal aid is not serving a positive function. The paper considers viable means for vetting the quality of these free legal services in a South African context, including telephonic legal advice in the Covid era. It suggests mechanisms to promote high-level free legal service provision by assessing the quality of such services. Legal aid quality control methods abroad were analysed to serve as an indicator of the options used in this regard in those jurisdictions. The question to be answered is what quality control measures are most apposite in the South African legal aid arena.
Investigation of infraclavicular block success using the perfusion index: a randomized clinical trial
Authors: Şeyhanlı İbrahim , Duran Mehmet , Yılmaz Nezir , Nakır Hamza , Doğukan Mevlüt , Uludağ Öznur
Published: November 2022

The results of the pinprick and cold tests performed on the arm, forearm, and wrist-wrist areas of patients scheduled for upper extremity procedures are subjective and dependent on patient's compliance. The purpose of this study was to determine whether the perfusion index (PI) could be used as an objective indicator to demonstrate block efficacy. Fifty patients between the ages of 18 and 65 years who were scheduled for upper extremity procedures and had an American Society of Anesthesiologists risk assessment class of I-II were included in this study. Infraclavicular block was performed on the patients using the peripheral nerve stimulation and ultrasonography. Preoperative and postoperative PI values were measured and recorded. The pinprick test took an average of 7.98 ± 1.49 minutes to turn positive, whereas the grade 3 of Modified Bromage Scale took an average of 11.08 ± 1.71 minutes. Differences between baseline values and perioperative values were found to be significantly different in the paired comparisons of the PI values. With 80% sensitivity and 80% specificity, increases in the PI value at or above 3.8 units were indicative for sensory block. With 84% sensitivity and 84% specificity, increases in the PI value by or above 3.9 units were indicative for grade 3 of Modified Bromage Scale in patients. It was determined that the PI is a faster, more reliable, and simpler technique than conventional methods for determining the efficacy of a block because of the vasodilatation that occurs before sensory and motor block.
A multicenter interventional study aimed to assess the effectiveness of Lavanda aroma in reducing anxiety and pain in patients undergoing PROstatic BIOpsy (LA-BIOPRO): Study protocol
Authors: Tatiana Bolgeo , Roberta di Matteo , Denise Gatti , Salvatore Cotroneo , Pietro Ricci , Andrea Di Stasio , Armando Serao , Carmelo Boccafoschi , Antonio Maconi
Published: November 2022

Background: A prostatic biopsy is a diagnostic test used in cases of suspected prostate cancer. The patient expresses significant levels of anxiety from the very first outpatient visits; anxiety and pain management is essential for a successful outcome of the procedure. Lavender oil is one of the essential oils that is commonly used in aromatherapy to reduce anxiety and pain, its low toxicity and side effects have made it the preferred treatment in complementary medicine. Aim: To assess the 'effectiveness of lavender scent in decreasing the levels of anxiety and pain in patients undergoing a prostatic biopsy. Methods: An interventional non-pharmacological, randomized, two-arm, multi-center, nonprofit study. The SS Antonio e Biagio e Cesare Arrigo Hospital and the City of Alessandria Clinic, Monza Polyclinic of Alessandria, will enroll consecutively all adult patients undergoing outpatient prostatic biopsy from April 1, 2022, to October 1, 2022. The Numerical Rating Scale and Hamilton Anxiety Rating Scale will be used for assessments. Conclusion: Lavender oil aromatherapy could have a clinically significant effect on reducing pain and anxiety during prostatic biopsy procedures; its simple use, safety, and low cost provide a therapeutic option to be considered, complementary to other medical interventions in certain clinical settings.
Air pollution and possible risk of dementia in the Czech Republic
Authors: Topinka J , Rossner P , Rossnerova A , Sram RJ
Published: November 2022

A review of recent literature indicates a significant effect of air pollution on the increased incidence of dementia, particularly Alzheimer’s disease. A possible mechanism is related to oxidative damage and inflammation. In the Czech Republic in previous decades the mining districts of Northern Bohemia suffered from very high air pollution levels, while during the last period in Northern Moravia this problem was also noted. This specific situation could be used to study the impact of air pollution on dementia, using new methods of molecular epidemiology together with the complex analysis of the lifestyle of the population living in the polluted regions.
HPA-3 and C807T polymorphisms are associated with laboratory biomarkers of coronary artery disease in Brazilian women
Authors: Suellen Pinheiro Carvalho Valverde , Setondji Cocou Modeste Alexandre Yahouédéhou , Rodrigo Mota de Oliveira , Nathalie Souza Veloso , Cleverson Alves Fonseca , Karina Oliveira Mendes , Cynara Gomes Barbosa , Marilda de Souza Gonçalves , Elisângela Vitória Adôrno
Published: November 2022

Reports describe the association between platelet activation, adhesion, and aggregation, as well as polymorphisms in genes encoding platelet membrane glycoproteins with a predisposition to coronary artery disease (CAD). This study investigates associations between HPA-1, -3 and C807T polymorphisms and CAD. A cross-sectional study involving 114 women who underwent coronary angiography was performed. The CAD+ group consisted of 63 women while the CAD- group of 51 women. Hematological and biochemical parameters were evaluated by electronic methods. Polymorphisms were investigated by PCR-RFLP and PCR-SSP and participants answered an epidemiological questionnaire and provided anthropometric data. Blood pressure was also measured. Statistical analyses were performed using EpiInfo v. 7.0 software. Results showed that age, diabetes mellitus, hypertension, and hyperlipidemia were associated with CAD. In addition, CAD+ women showed elevated glucose, TG, and VLDL-c levels and reduced HDL-c levels. No significant difference was observed between the allelic and genotypic distributions of the polymorphisms HPA-1, -3, and C807T in CAD+ and CAD- groups. However, CAD+ women carriers of the variant 3b allele had elevated TG and sP-selectin levels while the carriers of the variant 807T allele had reduced CT and LDL-c levels. Hence, our data suggest that the polymorphism HPA-3 increases, indirectly, the risk of CAD development and occurrence while polymorphism C807T reduces this effec.
Foreskin Tissue DNA Extraction v1
Authors: Maust Brandon
Published: November 2022

Extracts total DNA from foreskin tissue, as used in Maust et al. 2022
Mouse Islet Perifusion (3-stimuli protocol) v1
Authors: and Pancreas Analysis Core Islet
Published: November 2022

Our perifusion setup consists of 4 independently-driven channels, which allows for up to 4 different groups of islets to be studied simultaneously. Each channel has an intake catheter, a peristaltic pump, a chamber to hold the islets, and a fraction collector. This protocol details stimulation of mouse islets with 3 secretagogues (high glucose, IBMX, and KCl). The flow rate for the perifusion is 1 mL/minute, and fractions are collected every 3 minutes. The animation below illustrates the protocol.
Lexical Borrowing of Covid-19 Terminologies in the Indonesian Language
Authors: Claria Dewa Ayu Kadek , Artawa Ketut , Satyawati Made Sri , Putra Anak Agung Putu
Published: November 2022

New terminologies of Covid-19 in the Indonesian language began to appear during the pandemic. Generally, English affects the articulation of many terms in Indonesian when no equivalent words exist, leading to the borrowing process. The spread of new terms is inseparable from the influence of technological advances. Hence, the data used were obtained from a trusted national online media site antvklik.com, and qualitative methods were used to examine Indonesian terms that existed during the Covid-19 pandemic. This research concluded that the borrowed term can be classified into five forms, namely words, phrases, synonyms, abbreviations, and acronyms. Some terminologies are adjusted to enhance acceptance in society, while others are used directly.
Gender Role of Characters in the Illustrations of Local and Introduced Edition Textbooks of College Portuguese Teaching in China
Authors: Sui Jiajia
Published: November 2022

As an important resource and tool for college Portuguese teaching and learning, textbooks contain rich cultural concepts to a certain extent, among which gender culture is also deeply embedded in the textbooks and influences Portuguese students' perceptions of gender roles. This paper presents an empirical study that is based on a comparative analysis using the illustrated characters of four current college Portuguese textbooks, both local and introduced edition as the object of analysis to investigate the gender roles in these textbooks. By building a research framework that covers six dimensions of analysis: a) the number of male illustrations, female illustrations, and male and female illustrations; b) the number of male and female characters in the illustrations; c) the emotions of the male and female characters in the illustrations; d) the occupations of the male and female characters in the illustrations; e) the activity scenes of the male and female characters in the illustrations; f) the specific activities of male and female characters in the illustrations, we found that there is an imbalance of gender roles in the four introduced edition and local Portuguese textbooks, the findings suggest that the construction of gender culture in future Portuguese textbooks should pay attention to give balanced treatment to male and female characters and break down the gender stereotypes not only in the linguistic term but also visual and pictorial.