Philip Kilby

SoCS Conference 2022 Conference Paper

Weight Constrained Path Finding with Bidirectional A

• Saman Ahmadi
• Guido Tack
• Daniel Harabor
• Philip Kilby

Weight constrained path finding, known as a challenging variant of the classic shortest path problem, aims to plan cost optimum paths whose weight/resource usage is limited by a side constraint. Given the bi-criteria nature of the problem (i. e. , the presence of cost and weight), solutions to the Weight Constrained Shortest Path Problem (WCSPP) have some properties in common with bi-objective search. This paper leverages the state-of-the-art bi-objective search algorithm BOBA* and presents WC-BA*, an exact A*-based WCSPP method that explores the search space in different objective orderings bidirectionally. We also enrich WC-BA* with two novel heuristic tuning approaches that can significantly reduce the number of node expansions in the exhaustive search of A*. The results of our experiments on a large set of realistic problem instances show that our new algorithm solves all instances and outperforms the state-of-the-art WCSPP algorithms in various scenarios.

AAAI Conference 2021 Conference Paper

A Fast Exact Algorithm for the Resource Constrained Shortest Path Problem

• Saman Ahmadi
• Guido Tack
• Daniel D. Harabor
• Philip Kilby

Resource constrained path finding is a well studied topic in AI, with real-world applications in different areas such as transportation and robotics. This paper introduces several heuristics in the resource constrained path finding context that significantly improve the algorithmic performance of the initialisation phase and the core search. We implement our heuristics on top of a bidirectional A* algorithm and evaluate them on a set of large instances. The experimental results show that, for the first time in the context of constrained path finding, our fast and enhanced algorithm can solve all of the benchmark instances to optimality, and compared to the state of the art algorithms, it can improve existing runtimes by up to four orders of magnitude on large-size network graphs.

SoCS Conference 2021 Conference Paper

Bi-Objective Search with Bi-directional A* (Extended Abstract)

• Saman Ahmadi
• Guido Tack
• Daniel Harabor
• Philip Kilby

Bi-objective search is a problem of finding a set of optimal solutions in a two-dimensional domain. This study proposes several enhancements to the state-of-the-art bi-objective search with A* and develops its bi-directional variant. Our experimental results on benchmark instances show that our enhanced algorithm is on average five times faster than the state of the art bi-objective search algorithms.

JAIR Journal 2016 Journal Article

A Study of Proxies for Shapley Allocations of Transport Costs

• Haris Aziz
• Casey Cahan
• Charles Gretton
• Philip Kilby
• Nicholas Mattei
• Toby Walsh

We survey existing rules of thumb, propose novel methods, and comprehensively evaluate a number of solutions to the problem of calculating the cost to serve each location in a single-vehicle transport setting. Cost to serve analysis has applications both strategically and operationally in transportation settings. The problem is formally modeled as the traveling salesperson game (TSG), a cooperative transferable utility game in which agents correspond to locations in a traveling salesperson problem (TSP). The total cost to serve all locations in the TSP is the length of an optimal tour. An allocation divides the total cost among individual locations, thus providing the cost to serve each of them. As one of the most important normative division schemes in cooperative games, the Shapley value gives a principled and fair allocation for a broad variety of games including the TSG. We consider a number of direct and sampling-based procedures for calculating the Shapley value, and prove that approximating the Shapley value of the TSG within a constant factor is NP-hard. Treating the Shapley value as an ideal baseline allocation, we survey six proxies for it that are each relatively easy to compute. Some of these proxies are rules of thumb and some are procedures international delivery companies use(d) as cost allocation methods. We perform an experimental evaluation using synthetic Euclidean games as well as games derived from real-world tours calculated for scenarios involving fast-moving goods; where deliveries are made on a road network every day. We explore several computationally tractable allocation techniques that are good proxies for the Shapley value in problem instances of a size and complexity that is commercially relevant.

IJCAI Conference 2016 Conference Paper

Fleet Design Optimisation from Historical Data Using Constraint Programming and Large Neighbourhood Search

• Philip Kilby
• Tommaso Urli

We present an original approach to compute efficient mid-term fleet configurations at the request of a Queensland-based long-haul trucking carrier. Our approach considers one year's worth of demand data, and employs a constraint programming (CP) model and an adaptive large neighbourhood search (LNS) scheme to solve the underlying multi-day multi-commodity split delivery capacitated vehicle routing problem. This paper is an adaptation of the Best Application Paper at CP'15, published in the Constraints journal with the same title.

AAAI Conference 2016 Conference Paper

Intelligent Habitat Restoration Under Uncertainty

• Tommaso Urli
• Jana Brotánková
• Philip Kilby
• Pascal Van Hentenryck

Conservation is an ethic of sustainable use of natural resources which focuses on the preservation of biodiversity, i. e. , the degree of variation of life. Conservation planning seeks to reach this goal by means of deliberate actions, aimed at the protection (or restoration) of biodiversity features. In this paper we present an intelligent system to assist conservation managers in planning habitat restoration actions, with focus on the activities to be carried out in the islands of the Great Barrier Reef (QLD) and the Pilbara (WA) regions of Australia. In particular, we propose a constrained optimisation formulation of the habitat restoration planning (HRP) problem, capturing aspects such as population dynamics and uncertainty. We show that the HRP is NPhard, and develop a constraint programming (CP) model and a large neighbourhood search (LNS) procedure to generate activity plans under budgeting constraints in a reasonable amount of time.

ICAPS Conference 2012 Conference Paper

CP and MIP Methods for Ship Scheduling with Time-Varying Draft

• Elena Kelareva
• Sebastian Brand
• Philip Kilby
• Sylvie Thiébaux
• Mark Wallace 0001

Existing ship scheduling approaches either ignore constraints on ship draft (distance between the waterline and the keel), or model these in very simple ways, such as a constant draft limit that does not change with time. However, in most ports the draft restriction changes over time due to variation in environmental conditions. More accurate consideration of draft constraints would allow more cargo to be scheduled for transport on the same set of ships. We present constraint programming (CP) and mixed integer programming (MIP) models for the problem of scheduling ships at a port with time-varying draft constraints so as to optimise cargo throughput at the port. We also investigate the effect of several variations to the CP model, including a model containing sequence variables, and a model with ordered inputs. Our model allows us to solve realistic instances of the problem to optimality in a very short time, and produces better schedules than both scheduling with constant draft, and manual scheduling approaches used in practice at ports.

SoCS Conference 2011 Conference Paper

On Improving the Quality of Solutions in Large-Scale Cooperative Multi-Agent Pathfinding

• Ko-Hsin Cindy Wang
• Adi Botea
• Philip Kilby

Scaling up the number of simultaneously moving units in pathfinding problems to hundreds, or even thousands, is well beyond the capability of theoretically optimal algorithms in practice, which is consistent with existing intractability results. Significant scalability can be achieved by trading off solution optimality, which motivates evaluating the quality of suboptimal solutions, especially in instances much larger than can be handled by optimal algorithms. We consider pathfinding in uniform cost grid maps, and we study the solution quality using the three most common quality criteria, total travel distance, sum of actions, and makespan. We focus on MAPP, which has been shown as state-of-the-art in terms of scalability and success ratio (i. e. , percentage of solved units) on realistic game grid maps. Until now, the quality of MAPP

AAAI Conference 2011 Conference Paper

Solution Quality Improvements for Massively Multi-Agent Pathfinding

• Ko-Hsin Wang
• Adi Botea
• Philip Kilby

AAAI Conference 2006 Conference Paper

Estimating Search Tree Size

• Philip Kilby
• Sylvie Thiebaux

We propose two new online methods for estimating the size of a backtracking search tree. The first method is based on a weighted sample of the branches visited by chronological backtracking. The second is a recursive method based on assuming that the unexplored part of the search tree will be similar to the part we have so far explored. We compare these methods against an old method due to Knuth based on random probing. We show that these methods can reliably estimate the size of search trees explored by both optimization and decision procedures. We also demonstrate that these methods for estimating search tree size can be used to select the algorithm likely to perform best on a particular problem instance.

AAAI Conference 2005 Conference Paper

Backbones and Backdoors in Satisfiability

• Philip Kilby
• Sylvie Thiebaux

We study the backbone and the backdoors of propositional satisfiability problems. We make a number of theoretical, algorithmic and experimental contributions. From a theoretical perspective, we prove that backbones are hard even to approximate. From an algorithmic perspective, we present a number of different procedures for computing backdoors. From an empirical perspective, we study the correlation between being in the backbone and in a backdoor. Experiments show that there tends to be very little overlap between backbones and backdoors. We also study problem hardness for the Davis Putnam procedure. Problem hardness appears to be correlated with the size of strong backdoors, and weakly correlated with the size of the backbone, but does not appear to be correlated to the size of weak backdoors nor their number. Finally, to isolate the effect of backdoors, we look at problems with no backbone.

IJCAI Conference 2005 Conference Paper

The Backbone of the Travelling Salesperson

• Philip Kilby
• John Slaney
• Toby

We study the backbone of the travelling salesperson optimization problem. We prove that it is intractable to approximate the backbone with any performance guarantee, assuming that P6=NP and there is a limit on the number of edges falsely returned. Nevertheless, in practice, it appears that much of the backbone is present in close to optimal solutions. We can therefore often find much of the backbone using approximation methods based on good heuristics. We demonstrate that such backbone information can be used to guide the search for an optimal solution. However, the variance in runtimes when using a backbone guided heuristic is large. This suggests that we may need to combine such heuristics with randomization and restarts. In addition, though backbone guided heuristics are useful for finding optimal solutions, they are less help in proving optimality.

ECAI Conference 2000 Conference Paper

Estimating the Hardness of Optimisation

• John K. Slaney
• Sylvie Thiébaux
• Philip Kilby