Author name cluster

Charles Gretton

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

17 papers

2 author rows

ICAPS Conference 2024 Conference Paper

A Counter-Example Based Approach to Probabilistic Conformant Planning

Xiaodi Zhang 0002
Alban Grastien
Charles Gretton

This paper introduces a counter-example based approach for solving probabilistic conformant planning (PCP) problems. Our algorithm incrementally generates candidate plans and identifies counter-examples until it finds a plan for which the probability of success is above the specified threshold. We prove that the algorithm is sound and complete. We further propose a variation of our algorithm that uses hitting sets to accelerate the generation of candidate plans. Experimental results show that our planner is particularly suited for problems with a high probability threshold.

Details

AAAI Conference 2023 System Paper

Dagster: Parallel Structured Search

Mark Alexander Burgess
Charles Gretton
Josh Milthorpe
Luke Croak
Thomas Willingham
Alwen Tiu

We demonstrate Dagster, a system that implements a new approach to scheduling interdependent (Boolean) SAT search activities in high-performance computing (HPC) environments. Our system takes as input a set of disjunctive clauses (i.e., DIMACS CNF) and a labelled directed acyclic graph (DAG) structure describing how the clauses are decomposed into a set of interrelated problems. Component problems are solved using standard systematic backtracking search, which may optionally be coupled to (stochastic dynamic) local search and/or clause-strengthening processes. We demonstrate Dagster using a new Graph Maximal Determinant combinatorial case study. This demonstration paper presents a new case study, and is adjunct to the longer accepted manuscript at the Pacific Rim International Conference on Artificial Intelligence (2022).

PDF Details DOI

KR Conference 2023 Conference Paper

Property Directed Reachability for Planning Revisited

Ava Clifton
Charles Gretton

Property Directed Reachability (PDR) is a relatively new SAT-based search paradigm for classical AI planning. Compared to earlier SAT-based paradigms, PDR proceeds without unrolling the system transition function, and therefore without having the underlying procedure reason about potentially computationally expensive multi-step formulae. By maintaining a queue of obligations - i. e. , a state at a timestep - and knowledge about what is possible at each planning step, PDR iteratively evaluates whether an obligation can be progressed by one step towards the goal. We develop and evaluate two new distributed PDR algorithms for planning, and additionally implement serial and portfolio PDR algorithms for planning. We are the first to consider distributed PDR for planning and the first to consider PDR based on incremental SAT solving in that setting. Our first new algorithm, PS-PDR, evaluates many obligations independently in parallel using a pool of incremental SAT workers. PS-PDR is unique amongst distributed PDR algorithms in centrally maintaining a single queue of obligations, enabling an efficient focused search compared to a PDR portfolio. Our second new algorithm, PD-PDR, sequences subproblems according to the compositional structure of the concrete problem at hand. Subproblems are solved independently in parallel, with a concrete plan obtained by combining subproblem plans. Our experimental evaluation exhibits strong runtime gains for both new algorithms in both satisfiable and unsatisfiable planning benchmarks.

PDF Details DOI

UAI Conference 2022 Conference Paper

Enhanced adaptive optics control with image to image translation

Jeffrey Smith 0001
Jesse Cranney
Charles Gretton
Damien Gratadour

We aim to significantly enhance the science return of astronomical observatories, and in particular giant terrestrial optical telescopes. Observatories employ Adaptive Optics (AO) systems in order to acquire high sensitivity diffraction limited images of the sky. The incumbent “workhorse” for control of AO systems employs a linear real-time controller in a closed loop, with sensing of state performed via a (Shack-Hartmann) wavefront sensor (WFS). The actuators of a deformable mirror (DM) are driven, with the action performed in each iteration having a continuous representation as an array of DC voltages. The typical control regime is practical and scalable, nonetheless, there remains a residual uncompensated turbulence that leads to optical aberrations limiting the class of scientific assets that can be acquired. We have developed and trained a translational GAN model that accurately estimates residual perturbations from WFS images. Model inference occurs in 0. 34 milliseconds using off-the-shelf GPU hardware, and is applicable for use in AO control where the control loop might be running at 500Hz. We develop an AO control regime with a second controller stage actuating a second DM controlled in an open loop according to the estimated residual turbulence. Using the open-source COMPASS tool for simulation, we are able to significantly improve the performance using our new regime.

Details

ICAPS Conference 2018 Conference Paper

A TIL-Relaxed Heuristic for Planning with Time Windows

Tony Allard
Charles Gretton
Patrik Haslum

We consider planning problems with time windows, in which the availability of discrete resources is time constrained. We develop a novel heuristic that addresses specifically the difficulty of coordinating actions within time windows. The heuristic is based on solving a temporally relaxed problem and measuring the magnitude by which the relaxed solution violates the time window constraints. Applied in a state-space search planner, the heuristic reduces the number of dead-ends encountered during search, and improves planner coverage.

Details

ICAPS Conference 2017 Conference Paper

A State-Space Acyclicity Property for Exponentially Tighter Plan Length Bounds

Mohammad Abdulaziz
Charles Gretton
Michael Norrish

We investigate compositional bounding of transition system diameters, with application in bounding the lengths of plans. We establish usefully-tight bounds by exploiting acyclicity in state-spaces. We provide mechanised proofs in HOL4 of the validity of our approach. Evaluating our bounds in a range of benchmarks, we demonstrate exponentially tighter upper bounds compared to existing methods. Treating both solvable and unsolvable benchmark problems, we also demonstrate the utility of our bounds in boosting planner performance. We enhance an existing planning procedure to use our bounds, and demonstrate significant coverage improvements, both compared to the base planner, and also in comparisons with state-of-the-art systems.

Details

AIJ Journal 2017 Journal Article

Robot task planning and explanation in open and uncertain worlds

Marc Hanheide
Moritz Göbelbecker
Graham S. Horn
Andrzej Pronobis
Kristoffer Sjöö
Alper Aydemir
Patric Jensfelt
Charles Gretton

A long-standing goal of AI is to enable robots to plan in the face of uncertain and incomplete information, and to handle task failure intelligently. This paper shows how to achieve this. There are two central ideas. The first idea is to organize the robot's knowledge into three layers: instance knowledge at the bottom, commonsense knowledge above that, and diagnostic knowledge on top. Knowledge in a layer above can be used to modify knowledge in the layer(s) below. The second idea is that the robot should represent not just how its actions change the world, but also what it knows or believes. There are two types of knowledge effects the robot's actions can have: epistemic effects (I believe X because I saw it) and assumptions (I'll assume X to be true). By combining the knowledge layers with the models of knowledge effects, we can simultaneously solve several problems in robotics: (i) task planning and execution under uncertainty; (ii) task planning and execution in open worlds; (iii) explaining task failure; (iv) verifying those explanations. The paper describes how the ideas are implemented in a three-layer architecture on a mobile robot platform. The robot implementation was evaluated in five different experiments on object search, mapping, and room categorization.

Details DOI

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.

PDF Details DOI

IJCAI Conference 2015 Conference Paper

Exploiting Symmetries by Planning for a Descriptive Quotient

Mohammad Abdulaziz
Michael Norrish
Charles Gretton

We eliminate symmetry from a problem before searching for a plan. The planning problem with symmetries is decomposed into a set of isomorphic subproblems. One plan is computed for a small planning problem posed by a descriptive quotient, a description of any such subproblem. A concrete plan is synthesized by concatenating instantiations of that one plan for each subproblem. Our approach is sound.

PDF Details

AAAI Conference 2011 Conference Paper

A Switching Planner for Combined Task and Observation Planning

Moritz Göbelbecker
Charles Gretton
Richard Dearden

From an automated planning perspective the problem of practical mobile robot control in realistic environments poses many important and contrary challenges. On the one hand, the planning process must be lightweight, robust, and timely. Over the lifetime of the robot it must always respond quickly with new plans that accommodate exogenous events, changing objectives, and the underlying unpredictability of the environment. On the other hand, in order to promote efﬁcient behaviours the planning process must perform computationally expensive reasoning about contingencies and possible revisions of subjective beliefs according to quantitatively modelled uncertainty in acting and sensing. Towards addressing these challenges, we develop a continual planning approach that switches between using a fast satisﬁcing “classical” planner, to decide on the overall strategy, and decision-theoretic planning to solve small abstract subproblems where deeper consideration of the sensing model is both practical, and can signiﬁcantly impact overall performance. We evaluate our approach in large problems from a realistic robot exploration domain.

PDF Details

IJCAI Conference 2011 Conference Paper

Exploiting Probabilistic Knowledge under Uncertain Sensing for Efficient Robot Behaviour

Marc Hanheide
Charles Gretton
R. Dearden
Nick Hawes
Jeremy Wyatt
Andrzej Pronobis
Alper Aydemir
Moritz G

Robots must perform tasks efficiently and reliably while acting underuncertainty. One way to achieve efficiency is to give the robot common-sense knowledge about the structure of the world. Reliable robot behaviour can be achieved by modelling the uncertaintyin the world probabilistically. We present a robot system that combines these two approaches and demonstrate the improvements in efficiency and reliability that result. Our first contribution is a probabilistic relational model integrating common-sense knowledge about the world in general, with observations of a particular environment. Our second contribution is a continual planning system which is able to plan in the large problems posed by that model, by automatically switching between decision-theoretic and classical procedures. We evaluate our system on object search tasks in two different real-world indoor environments. By reasoning about the trade-offs between possible courses of action with different informational effects, and exploiting the cues and general structures of those environments, our robot is able to consistently demonstrate efficient and reliable goal-directed behaviour.

PDF Details DOI

ICAPS Conference 2009 Conference Paper

SAT-Based Parallel Planning Using a Split Representation of Actions

Nathan Robinson
Charles Gretton
Duc Nghia Pham
Abdul Sattar 0001

Planning based on propositional SAT(isfiability) is a powerful approach to computing step-optimal plans given a parallel execution semantics. In this setting: (i) a solution plan must be minimal in the number of plan steps required, and (ii) non-conflicting actions can be executed instantaneously in parallel at a plan step. Underlying SAT-based approaches is the invocation of a decision procedure on a SAT encoding of a bounded version of the problem. A fundamental limitation of existing approaches is the size of these encodings. This problem stems from the use of a direct representation of actions — i. e. each action has a corresponding variable in the encoding. A longtime goal in planning has been to mitigate this limitation by developing a more compact split — also termed lifted — representation of actions in SAT encodings of parallel step-optimal problems. This paper describes such a representation. In particular, each action and each parallel execution of actions is represented uniquely as a conjunct of variables. Here, each variable is derived from action pre and post-conditions. Because multiple actions share conditions, our encoding of the planning constraints is factored and relatively compact. We find experimentally that our encoding yields a much more efficient and scalable planning procedure over the state-of-the-art in a large set of planning benchmarks.

Details

ICAPS Conference 2008 Conference Paper

A Compact and Efficient SAT Encoding for Planning

Nathan Robinson
Charles Gretton
Duc Nghia Pham
Abdul Sattar 0001

In the planning-as-SAT paradigm there have been numerous recent developments towards improving the speed and scalability of planning at the cost of finding a step-optimal parallel plan. These developments have been towards: (1) Query strategies that efficiently yield approximately optimal plans, and (2) Having a SAT procedure compute plans from relaxed encodings of the corresponding decision problems in such a way that conflicts in a plan arising from the relaxation are resolved cheaply during a post-processing phase. In this paper we examine a third direction of tightening constraints in order to achieve a more compact, efficient, and scalable SAT-based encoding of the planning problem. For the first time, we use lifting (i. e., splitting) and factoring to encode the corresponding n-step decision problems with a parallel action semantics. To ensure compactness we exploit reachability and neededness analysis of the plangraph. Our encoding also captures state-dependent mutex constraints computed during that analysis. Because we adopt a lifted action representation, our encoding cannot generally support full action parallelism. Thus, our approach could be termed approximate, planning for a number of steps between that required in the optimal parallel case and the optimal linear case. We perform a detailed experimental analysis of our approach with 3 state-of-the-art SAT-based planners using benchmarks from recent international planning competitions. We find that our approach dominates optimal SAT-based planners, and is more efficient than the relaxed planners for domains where the plan existence problem is hard.

Details

IROS Conference 2008 Conference Paper

Induction of topological environment maps from sequences of visited places

Felix Werner
Charles Gretton
Frédéric Maire
Joaquin Sitte

In this paper we address the problem of topologically mapping environments which contain inherent perceptual aliasing caused by repeated environment structures. We propose an approach that does not use motion or odometric information but only a sequence of deterministic measurements observed by traversing an environment. Our algorithm implements a stochastic local search to build a small map which is consistent with local adjacency information extracted from a sequence of observations. Moreover, local adjacency information is incorporated to disambiguate places which are physically different but appear identical to the robots senses. Experiments show that the proposed method is capable of mapping environments with a high degree of perceptual aliasing, and that it infers a small map quickly.

Details

ICAPS Conference 2007 Conference Paper

Gradient-Based Relational Reinforcement Learning of Temporally Extended Policies

Charles Gretton

We consider the problem of computing general policies for decision-theoretic planning problems with temporally extended rewards. We describe a gradient-based approach to relational reinforcement learning (RRL) of policies for that setting. In particular, the learner optimises its behaviour by acting in a set of problems drawn from a target domain. Our approach is similar to inductive policy selection because the policies learnt are given in terms of relational control-rules. These rules are generated either (1) by reasoning from a first-order specification of the domain, or (2) more or less arbitrarily according to a taxonomic concept language. To this end the paper contributes a domain definition language for problems with temporally extended rewards, and a taxonomic concept language in which concepts and relations can be temporal. We evaluate our approach in versions of the miconic, logistics and blocks-world planning benchmarks and find that it is able to learn good policies. Our experiments show there is a significant advantage in making temporal concepts available in RRL for planning, whether rewards are temporally extended or not.

Details

UAI Conference 2004 Conference Paper

Exploiting First-Order Regression in Inductive Policy Selection

Charles Gretton
Sylvie Thiébaux

We consider the problem of computing optimal generalised policies for relational Markov decision processes. We describe an approach combining some of the benefits of purely inductive techniques with those of symbolic dynamic programming methods. The latter reason about the optimal value function using first-order decision theoretic regression and formula rewriting, while the former, when provided with a suitable hypotheses language, are capable of generalising value functions or policies for small instances. Our idea is to use reasoning and in particular classical first-order regression to automatically generate a hypotheses language dedicated to the domain at hand, which is then used as input by an inductive solver. This approach avoids the more complex reasoning of symbolic dynamic programming while focusing the inductive solver's attention on concepts that are specifically relevant to the optimal value function for the domain considered.

Details

UAI Conference 2003 Conference Paper

Implementation and Comparison of Solution Methods for Decision Processes with Non-Markovian Rewards

Charles Gretton
David Price
Sylvie Thiébaux

This paper examines a number of solution methods for decision processes with non-Markovian rewards (NMRDPs). They all exploit a temporal logic specification of the reward function to automatically translate the NMRDP into an equivalent Markov decision process (MDP) amenable to well-known MDP solution methods. They differ however in the representation of the target MDP and the class of MDP solution methods to which they are suited. As a result, they adopt different temporal logics and different translations. Unfortunately, no implementation of these methods nor experimental let alone comparative results have ever been reported. This paper is the first step towards filling this gap. We describe an integrated system for solving NMRDPs which implements these methods and several variants under a common interface; we use it to compare the various approaches and identify the problem features favoring one over the other

Details