Graeme Gange

AAAI Conference 2022 Conference Paper

Flex Distribution for Bounded-Suboptimal Multi-Agent Path Finding

• Shao-Hung Chan
• Jiaoyang Li
• Graeme Gange
• Daniel Harabor
• Peter J. Stuckey
• Sven Koenig

Multi-Agent Path Finding (MAPF) is the problem of finding collision-free paths for multiple agents that minimize the sum of path costs. EECBS is a leading two-level algorithm that solves MAPF bounded-suboptimally, that is, within some factor w of the minimum sum of path costs C∗. It uses focal search to find bounded-suboptimal paths on the low level and Explicit Estimation Search (EES) to resolve collisions on the high level. EES keeps track of a lower bound LB on C∗ to find paths whose sum of path costs is at most w · LB in order to solve MAPF bounded-suboptimally. However, the costs of many paths are often much smaller than w times their minimum path costs, meaning that the sum of path costs is much smaller than w ·C∗. In this paper, we therefore propose Flexible EECBS (FEECBS), which uses a flex(ible) distribution of the path costs (that relaxes the requirement to find bounded-suboptimal paths on the low level) in order to reduce the number of collisions that need to be resolved on the high level while still guaranteeing to solve MAPF bounded suboptimally. We address the drawbacks of flex distribution via techniques such as restrictions on the flex distribution, restarts of the high-level search with EECBS, and low-level focal-A* search. Our empirical evaluation shows that FEECBS substantially improves the efficiency of EECBS on MAPF instances with large maps and large numbers of agents.

ICAPS Conference 2022 Conference Paper

Multi-Agent Path Finding with Temporal Jump Point Search

• Shuli Hu
• Daniel Harabor
• Graeme Gange
• Peter J. Stuckey
• Nathan R. Sturtevant

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

SoCS Conference 2021 Conference Paper

ECBS with Flex Distribution for Bounded-Suboptimal Multi-Agent Path Finding

• Shao-Hung Chan
• Jiaoyang Li 0001
• Graeme Gange
• Daniel Harabor
• Peter J. Stuckey
• Sven Koenig

Multi-Agent Path Finding (MAPF) is the problem of finding collision-free paths for multiple agents. CBS is a leading optimal two-level MAPF solver whose low level plans optimal paths for single agents and whose high level runs a best-first search on a Constraint Tree (CT) to resolve the collisions between the paths. ECBS, a bounded-suboptimal variant of CBS, speeds up CBS by reducing the number of collisions that need to be resolved on the high level. It achieves this by generating bounded-suboptimal paths with fewer collisions with the paths of the other agents on the low level and expanding bounded-suboptimal CT nodes that contain fewer collisions on the high level. In this paper, we propose Flexible ECBS (FECBS) that further reduces the number of collisions that need to be resolved on the high level by using looser suboptimal bounds on the low level while still providing bounded-suboptimal solutions. Instead of requiring the cost of each path to be bounded-suboptimal, FECBS requires only the overall cost of the paths to be bounded-suboptimal, which gives us the freedom to distribute the cost leeway among different agents according to their needs. Our empirical results show that FECBS can solve more MAPF instances than state-of-the-art ECBS variants within 5 minutes.

ICAPS Conference 2021 Conference Paper

Jump Point Search with Temporal Obstacles

• Shuli Hu
• Daniel Harabor
• Graeme Gange
• Peter J. Stuckey
• Nathan R. Sturtevant

In 4-connected grid-based path planning one often needs to account for temporal and moving obstacles: ones that appear, disappear and which can prevent the agent from reaching its target. Such problems are common in a variety of settings (games, robotics etc.) and they can be surprisingly challenging to solve. First, because the temporal aspect increases the size of the search space; second because the search space contains many symmetric paths, indistinguishable from one another except by the order in which grid moves appear. To tackle such problems we consider a new optimal algorithm – in the style of Jump Point Search – which can identify and break these symmetries and thus improves performance; from several factor to more than one order of magnitude vs. SIPP, arguably the gold standard baseline in the area.

AAAI Conference 2021 Conference Paper

Optimising Automatic Calibration of Electric Muscle Stimulation

• Graeme Gange
• Jarrod Knibbe

Electrical Muscle Stimulation (EMS) has become a popular interaction technology in Human-Computer Interaction; allowing the computer to take direct control of the user’s body. To date, however, the explorations have been limited to coarse, generalised examples, due to the low resolution of achievable control. To increase this resolution, the EMS needs to increase significantly in complexity - using large numbers of electrodes in complex patterns. The calibration of such a system remains an unsolved challenge. We present a new SAT-based black-box calibration method, which requires no spatial information about muscular or electrode positioning. The method encodes domain knowledge and observations in a constraint model, and uses these to prune the space of feasible control signals. In a simulated environment we find this method can scale reliably to large arrays while requiring only a modest number of trials, and preliminary tests on real hardware show we can effectively calibrate an electrode array in a few minutes.

AIJ Journal 2021 Journal Article

Pairwise symmetry reasoning for multi-agent path finding search

• Jiaoyang Li
• Daniel Harabor
• Peter J. Stuckey
• Hang Ma
• Graeme Gange
• Sven Koenig

LOPSTR Conference 2020 Conference Paper

Algorithm Selection for Dynamic Symbolic Execution: A Preliminary Study

• Roberto Amadini
• Graeme Gange
• Peter Schachte
• Harald Søndergaard
• Peter J. Stuckey

Abstract Given a portfolio of algorithms, the goal of Algorithm Selection ( AS ) is to select the best algorithm(s) for a new, unseen problem instance. Dynamic Symbolic Execution ( DSE ) brings together concrete and symbolic execution to maximise the program coverage. DSE uses a constraint solver to solve the path conditions and generate new inputs to explore. In this paper we join these lines of research by introducing a model that combines DSE and AS approaches. The proposed AS/DSE model is a generic and flexible framework enabling the DSE engine to solve the path conditions it collects with a portfolio of different solvers, by exploiting and extending the well-known AS techniques that have been developed over the last decade. In this way, one can increase the coverage and sometimes even outperform the aggregate coverage achievable by running simultaneously all the solvers of the portfolio.

AIJ Journal 2020 Journal Article

Dashed strings for string constraint solving

• Roberto Amadini
• Graeme Gange
• Peter J. Stuckey

ICAPS Conference 2020 Conference Paper

New Techniques for Pairwise Symmetry Breaking in Multi-Agent Path Finding

• Jiaoyang Li 0001
• Graeme Gange
• Daniel Harabor
• Peter J. Stuckey
• Hang Ma 0001
• Sven Koenig

We consider two new classes of pairwise path symmetries which appear in the context of Multi-Agent Path Finding (MAPF). The first of them, corridor symmetry, arises when two agents attempt to pass through the same narrow passage in opposite directions. The second, target symmetry, arises when the shortest path of one agent passes through the target location of a second agent after the second agent has already arrived at it. These symmetries can produce an exponential explosion in the space of possible collision resolutions, leading to unacceptable runtimes even for state-of-the-art MAPF algorithms such as Conflict-Based Search (CBS). We propose to break these symmetries using new reasoning techniques that: (1) detect each class of symmetry and (2) resolve them by introducing specialized constraints. We experimentally show that our techniques can, in some cases, more than double the success rate of CBS and improve its runtime by one order of magnitude.

SoCS Conference 2020 Conference Paper

New Techniques for Pairwise Symmetry Breaking in Multi-Agent Path Finding

• Jiaoyang Li 0001
• Graeme Gange
• Daniel Harabor
• Peter J. Stuckey
• Hang Ma 0001
• Sven Koenig

We consider two new types of pairwise path symmetries which appear in the context of Multi-Agent Path Finding (MAPF). The first of them, corridor symmetry, arises when two agents attempt to pass through the same narrow passage but in opposite directions. The second, target symmetry, arises when the shortest path of one agent requires the target location of a second agent after the second agent has already arrived. These symmetries can produce an exponential blowup in the space of possible collision resolutions, leading to timeout failure even for state-of-the-art algorithms such as Conflict-Based Search. We propose to break symmetries using new reasoning techniques that: (1) detect each type of situation and, (2) resolve them by introducing specialized constraints. We implement our ideas in the context of Conflict-Based Search where, in a range of experiments, we report up to an order-of-magnitude improvement in runtime performance and, in some cases, more than a doubling in success rate.

ECAI Conference 2020 Conference Paper

String Constraint Solving: Past, Present and Future

• Roberto Amadini
• Graeme Gange
• Peter Schachte
• Harald Søndergaard
• Peter J. Stuckey

String constraint solving is an important emerging field, given the ubiquity of strings over different fields such as formal analysis, automated testing, database query processing, and cybersecurity. This paper highlights the current state-of-the-art for string constraint solving, and identifies future challenges in this field.

ICAPS Conference 2019 Conference Paper

Lazy CBS: Implicit Conflict-Based Search Using Lazy Clause Generation

• Graeme Gange
• Daniel Harabor
• Peter J. Stuckey

Conflict-based Search (CBS) is a effective approach to optimal multi-agent path finding. However, performance of CBS approaches degrade rapidly in highly-contended graphs with many agents. One of the reasons this occurs is that CBS does not detect independent subproblems; i. e. it can re-solve the same conflicts between the same pairs of agents up to exponentially many times, each time along a different branch. Constraint programming approaches with nogood learning avoid this kind of duplication of effort by storing nogoods that record the reasons for conflicts. This can exponentially reduce search in constraint programming. In this work, we present Lazy CBS, a new approach to multi-agent pathfinding which replaces the high-level solver of CBS with a lazily constructed constraint programming model with nogoods. We use core-guided depth-first search to explore the space of conflicts and we detect along each branch reusable nogoods which help to quickly identify feasible solutions. Our experiments show that Lazy CBS can significantly improve on the state-of-the-art for optimal MAPF problems under the sumof-costs metric, especially in cases where there exists significant contention.

IJCAI Conference 2018 Conference Paper

Machine Learning and Constraint Programming for Relational-To-Ontology Schema Mapping

• Diego de Uña
• Nataliia Rümmele
• Graeme Gange
• Peter Schachte
• Peter J. Stuckey

The problem of integrating heterogeneous data sources into an ontology is highly relevant in the database field. Several techniques exist to approach the problem, but side constraints on the data cannot be easily implemented and thus the results may be inconsistent. In this paper we improve previous work by Taheriyan et al. [2016a] using Machine Learning (ML) to take into account inconsistencies in the data (unmatchable attributes) and encode the problem as a variation of the Steiner Tree, for which we use work by De Uña et al. [2016] in Constraint Programming (CP). Combining ML and CP achieves state-of-the-art precision, recall and speed, and provides a more flexible framework for variations of the problem.

AAAI Conference 2018 Conference Paper

Sweep-Based Propagation for String Constraint Solving

• Roberto Amadini
• Graeme Gange
• Peter Stuckey

Solving constraints over strings is an emerging important field. Recently, a Constraint Programming approach based on dashed strings has been proposed to enable a compact domain representation for potentially large bounded-length string variables. In this paper, we present a more efficient algorithm for propagating equality (and related constraints) over dashed strings. We call this propagation sweep-based. Experimental evidences show that sweep-based propagation is able to significantly outperform state-of-the-art approaches for string constraint solving.

SAT Conference 2017 Conference Paper

A Benders Decomposition Approach to Deciding Modular Linear Integer Arithmetic

• Bishoksan Kafle
• Graeme Gange
• Peter Schachte
• Harald Søndergaard
• Peter J. Stuckey

Abstract Verification tasks frequently require deciding systems of linear constraints over modular (machine) arithmetic. Existing approaches for reasoning over modular arithmetic use bit-vector solvers, or else approximate machine integers with mathematical integers and use arithmetic solvers. Neither is ideal; the first is sound but inefficient, and the second is efficient but unsound. We describe a linear encoding which correctly describes modular arithmetic semantics, yielding an optimistic but sound approach. Our method abstracts the problem with linear arithmetic, but progressively refines the abstraction when modular semantics is violated. This preserves soundness while exploiting the mostly integer nature of the constraint problem. We present a prototype implementation, which gives encouraging experimental results.

AAAI Conference 2017 Conference Paper

Automatic Logic-Based Benders Decomposition with MiniZinc

• Toby Davies
• Graeme Gange
• Peter Stuckey

Logic-based Benders decomposition (LBBD) is a powerful hybrid optimisation technique that can combine the strong dual bounds of mixed integer programming (MIP) with the combinatorial search strengths of constraint programming (CP). A major drawback of LBBD is that it is a far more involved process to implement an LBBD solution to a problem than the ”model-and-run” approach provided by both CP and MIP. We propose an automated approach that accepts an arbitrary MiniZinc model and solves it using LBBD with no additional intervention on the part of the modeller. The design of this approach also reveals an interesting duality between LBBD and large neighborhood search (LNS). We compare our implementation of this approach to CP and MIP solvers on 4 different problem classes where LBBD has been applied before.

TCS Journal 2016 Journal Article

A complete refinement procedure for regular separability of context-free languages

• Graeme Gange
• Jorge A. Navas
• Peter Schachte
• Harald Søndergaard
• Peter J. Stuckey

AAAI Conference 2016 Conference Paper

Steiner Tree Problems with Side Constraints Using Constraint Programming

• Diego de Uña
• Graeme Gange
• Peter Schachte
• Peter Stuckey

The Steiner Tree Problem is a well know NP-complete problem that is well studied and for which fast algorithms are already available. Nonetheless, in the real world the Steiner Tree Problem is almost always accompanied by side constraints which means these approaches cannot be applied. For many problems with side constraints, only approximation algorithms are known. We introduce here a propagator for the tree constraint with explanations, as well as lower bounding techniques and a novel constraint programming approach for the Steiner Tree Problem and two of its variants. We find our propagators with explanations are highly advantageous when it comes to solving variants of this problem.

LOPSTR Conference 2014 Conference Paper

Analyzing Array Manipulating Programs by Program Transformation

• J. Robert M. Cornish
• Graeme Gange
• Jorge A. Navas
• Peter Schachte
• Harald Søndergaard
• Peter J. Stuckey

Abstract We explore a transformational approach to the problem of verifying simple array-manipulating programs. Traditionally, verification of such programs requires intricate analysis machinery to reason with universally quantified statements about symbolic array segments, such as “every data item stored in the segment A[i] to A[j] is equal to the corresponding item stored in the segment B[i] to B[j]. ” We define a simple abstract machine which allows for set-valued variables and we show how to translate programs with array operations to array-free code for this machine. For the purpose of program analysis, the translated program remains faithful to the semantics of array manipulation. Based on our implementation in LLVM, we evaluate the approach with respect to its ability to extract useful invariants and the cost in terms of code size.

ECAI Conference 2008 Conference Paper

Fast Set Bounds Propagation using BDDs

• Graeme Gange
• Vitaly Lagoon
• Peter J. Stuckey

Set bounds propagation is the most popular approach to solving constraint satisfaction problems (CSPs) involving set variables. The use of reduced ordered Binary Decision Diagrams (BDDs) to represent and solve set CSPs is well understood and brings the advantage that propagators for arbitrary set constraints can be built. This can substantially improve solving. The disadvantages of BDDs is that creating and manipulating BDDs can be expensive. In this paper we show how we can perform set bounds propagation using BDDs in a much more efficient manner by generically creating set constraint predicates, and using a marking approach to propagation. The resulting system can be significantly faster than competing approaches to set bounds propagation.