Robert Fitch

Jennifer Wakulicz, Ki Myung Brian Lee, Chanyeol Yoo et al.

We present a planning framework for minimising the deterministic worst-case error in sparse Gaussian process (GP) regression. We first derive a universal worst-case error bound for sparse GP regression with bounded noise using interpolation theory on reproducing kernel Hilbert spaces (RKHSs). By exploiting the conditional independence (CI) assumption central to sparse GP regression, we show that the worst-case error minimisation can be achieved by solving a posterior entropy minimisation problem. In turn, the posterior entropy minimisation problem is solved using a Gaussian belief space planning algorithm. We corroborate the proposed worst-case error bound in a simple 1D example, and test the planning framework in simulation for a 2D vehicle in a complex flow field. Our results demonstrate that the proposed posterior entropy minimisation approach is effective in minimising deterministic error, and outperforms the conventional measurement entropy maximisation formulation when the inducing points are fixed.

Giovanni D'urso, James Ju Heon Lee, Ki Myung Brian Lee et al.

Marine vehicles have been used for various scientific missions where information over features of interest is collected. In order to maximise efficiency in collecting information over a large search space, we should be able to deploy a large number of autonomous vehicles that make a decision based on the latest understanding of the target feature in the environment. In our previous work, we have presented a hierarchical framework for the multi-vessel multi-float (MVMF) problem where surface vessels drop and pick up underactuated floats in a time-minimal way. In this paper, we present the field trial results using the framework with a number of drifters and floats. We discovered a number of important aspects that need to be considered in the proposed framework, and present the potential approaches to address the challenges.

Ki Myung Brian Lee, Felix H. Kong, Ricardo Cannizzaro et al.

We present the design and implementation of a decentralised, heterogeneous multi-robot system for performing intelligence, surveillance and reconnaissance (ISR) in an unknown environment. The team consists of functionally specialised robots that gather information and others that perform a mission-specific task, and is coordinated to achieve simultaneous exploration and exploitation in the unknown environment. We present a practical implementation of such a system, including decentralised inter-robot localisation, mapping, data fusion and coordination. The system is demonstrated in an efficient distributed simulation. We also describe an UAS platform for hardware experiments, and the ongoing progress.

Ki Myung Brian Lee, Chanyeol Yoo, Robert Fitch

We reformulate the signal temporal logic (STL) synthesis problem as a maximum a-posteriori (MAP) inference problem. To this end, we introduce the notion of random STL~(RSTL), which extends deterministic STL with random predicates. This new probabilistic extension naturally leads to a synthesis-as-inference approach. The proposed method allows for differentiable, gradient-based synthesis while extending the class of possible uncertain semantics. We demonstrate that the proposed framework scales well with GPU-acceleration, and present realistic applications of uncertain semantics in robotics that involve target tracking and the use of occupancy grids.

Ki Myung Brian Lee, Felix H. Kong, Ricardo Cannizzaro et al.

Heterogeneous multi-robot systems are advantageous for operations in unknown environments because functionally specialised robots can gather environmental information, while others perform tasks. We define this decomposition as the scout-task robot architecture and show how it avoids the need to explicitly balance exploration and exploitation~by permitting the system to do both simultaneously. The challenge is to guide exploration in a way that improves overall performance for time-limited tasks. We derive a novel upper confidence bound for simultaneous exploration and exploitation based on mutual information and present a general solution for scout-task coordination using decentralised Monte Carlo tree search. We evaluate the performance of our algorithms in a multi-drone surveillance scenario in which scout robots are equipped with low-resolution, long-range sensors and task robots capture detailed information using short-range sensors. The results address a new class of coordination problem for heterogeneous teams that has many practical applications.

Felix H. Kong, K. Y. Cadmus To, Gary Brassington et al.

Estimating ocean flow fields in 3D is a critical step in enabling the reliable operation of underwater gliders and other small, low-powered autonomous marine vehicles. Existing methods produce depth-averaged 2D layers arranged at discrete vertical intervals, but this type of estimation can lead to severe navigation errors. Based on the observation that real-world ocean currents exhibit relatively low velocity vertical components, we propose an accurate 3D estimator that extends our previous work in estimating 2D flow fields as a linear combination of basis flows. The proposed algorithm uses data from ensemble forecasting to build a set of 3D basis flows, and then iteratively updates basis coefficients using point measurements of underwater currents. We report results from experiments using actual ensemble forecasts and synthetic measurements to compare the performance of our method to the direct 3D extension of the previous work. These results show that our method produces estimates with dramatically lower error metrics, with and without measurement noise.

K. Y. Cadmus To, Felix H. Kong, Ki Myung Brian Lee et al.

We present a method to estimate two-dimensional, time-invariant oceanic flow fields based on data from both ensemble forecasts and online measurements. Our method produces a realistic estimate in a computationally efficient manner suitable for use in marine robotics for path planning and related applications. We use kernel methods and singular value decomposition to find a compact model of the ensemble data that is represented as a linear combination of basis flow fields and that preserves the spatial correlations present in the data. Online measurements of ocean current, taken for example by marine robots, can then be incorporated using recursive Bayesian estimation. We provide computational analysis, performance comparisons with related methods, and demonstration with real-world ensemble data to show the computational efficiency and validity of our method. Possible applications in addition to path planning include active perception for model improvement through deliberate choice of measurement locations.

K. Y. Cadmus To, Chanyeol Yoo, Stuart Anstee et al.

Motion planning for vehicles under the influence of flow fields can benefit from the idea of streamline-based planning, which exploits ideas from fluid dynamics to achieve computational efficiency. Important to such planners is an efficient means of computing the travel distance and direction between two points in free space, but this is difficult to achieve in strong incompressible flows such as ocean currents. We propose two useful distance functions in analytical form that combine Euclidean distance with values of the stream function associated with a flow field, and with an estimation of the strength of the opposing flow between two points. Further, we propose steering heuristics that are useful for steering towards a sampled point. We evaluate these ideas by integrating them with RRT* and comparing the algorithm's performance with state-of-the-art methods in an artificial flow field and in actual ocean prediction data in the region of the dominant East Australian Current between Sydney and Brisbane. Results demonstrate the method's computational efficiency and ability to find high-quality paths outperforming state-of-the-art methods, and show promise for practical use with autonomous marine robots.

Stefan H. Kiss, K. Y. Cadmus To, Chanyeol Yoo et al.

Integrating mobile robots into human society involves the fundamental problem of navigation in crowds. This problem has been studied by considering the behaviour of humans at the level of individuals, but this representation limits the computational efficiency of motion planning algorithms. We explore the idea of representing a crowd as a flow field, and propose a formal definition of path quality based on the concept of invasiveness; a robot should attempt to navigate in a way that is minimally invasive to humans in its environment. We develop an algorithmic framework for path planning based on this definition and present experimental results that indicate its effectiveness. These results open new algorithmic questions motivated by the flow field representation of crowds and are a necessary step on the path to end-to-end implementations.

K. Y. Cadmus To, James Ju Heon Lee, Chanyeol Yoo et al.

Autonomous underwater gliders use buoyancy control to achieve forward propulsion via a sawtooth-like, rise-and-fall trajectory. Because gliders are slow-moving relative to ocean currents, glider control must consider the effect of oceanic flows. In previous work, we proposed a method to control underwater vehicles in the (horizontal) plane by describing such oceanic flows in terms of streamlines, which are the level sets of stream functions. However, the general analytical form of streamlines in 3D is unknown. In this paper, we show how streamline control can be used in 3D environments by assuming a 2.5D model of ocean currents. We provide an efficient algorithm that acts as a steering function for a single rise or dive component of the glider's sawtooth trajectory, integrate this algorithm within a sampling-based motion planning framework to support long-distance path planning, and provide several examples in simulation in comparison with a baseline method. The key to our method's computational efficiency is an elegant dimensionality reduction to a 1D control region. Streamline-based control can be integrated within various sampling-based frameworks and allows for online planning for gliders in complicated oceanic flows.

Chanyeol Yoo, Samuel Lensgraf, Robert Fitch et al.

The most widely used methods for toolpath planning in fused deposition 3D printing slice the input model into successive 2D layers in order to construct the toolpath. Unfortunately slicing-based methods can incur a substantial amount of wasted motion (i.e., the extruder is moving while not printing), particularly when features of the model are spatially separated. In recent years we have introduced a new paradigm that characterizes the space of feasible toolpaths using a dependency graph on the input model, along with several algorithms to search this space for toolpaths that optimize objective functions such as wasted motion or print time. A natural question that arises is, under what circumstances can we efficiently compute an optimal toolpath? In this paper, we give an algorithm for computing fused deposition modeling (FDM) toolpaths that utilizes Monte Carlo Tree Search (MCTS), a powerful general-purpose method for navigating large search spaces that is guaranteed to converge to the optimal solution. Under reasonable assumptions on printer geometry that allow us to compress the dependency graph, our MCTS-based algorithm converges to find the optimal toolpath. We validate our algorithm on a dataset of 75 models and show it performs on par with our previous best local search-based algorithm in terms of toolpath quality. In prior work we speculated that the performance of local search was near optimal, and we examine in detail the properties of the models and MCTS executions that lead to better or worse results than local search.

James Ju Heon Lee, Chanyeol Yoo, Stuart Anstee et al.

We propose an algorithm for solving the time-dependent shortest path problem in flow fields where the FIFO (first-in-first-out) assumption is violated. This problem variant is important for autonomous vehicles in the ocean, for example, that cannot arbitrarily hover in a fixed position and that are strongly influenced by time-varying ocean currents. Although polynomial-time solutions are available for discrete-time problems, the continuous-time non-FIFO case is NP-hard with no known relevant special cases. Our main result is to show that this problem can be solved in polynomial time if the edge travel time functions are piecewise-constant, agreeing with existing worst-case bounds for FIFO problems with restricted slopes. We present a minimum-time algorithm for graphs that allows for paths with finite-length cycles, and then embed this algorithm within an asymptotically optimal sampling-based framework to find time-optimal paths in flows. The algorithm relies on an efficient data structure to represent and manipulate piecewise-constant functions and is straightforward to implement. We illustrate the behaviour of the algorithm in an example based on a common ocean vortex model in addition to simpler graph-based examples.

Ki Myung Brian Lee, Chanyeol Yoo, Ben Hollings et al.

Underwater robots are subject to position drift due to the effect of ocean currents and the lack of accurate localisation while submerged. We are interested in exploiting such position drift to estimate the ocean current in the surrounding area, thereby assisting navigation and planning. We present a Gaussian process~(GP)-based expectation-maximisation~(EM) algorithm that estimates the underlying ocean current using sparse GPS data obtained on the surface and dead-reckoned position estimates. We first develop a specialised GP regression scheme that exploits the incompressibility of ocean currents to counteract the underdetermined nature of the problem. We then use the proposed regression scheme in an EM algorithm that estimates the best-fitting ocean current in between each GPS fix. The proposed algorithm is validated in simulation and on a real dataset, and is shown to be capable of reconstructing the underlying ocean current field. We expect to use this algorithm to close the loop between planning and estimation for underwater navigation in unknown ocean currents.

Kwun Yiu Cadmus To, Ki Myung Brian Lee, Chanyeol Yoo et al.

Motion planning for underwater vehicles must consider the effect of ocean currents. We present an efficient method to compute reachability and cost between sample points in sampling-based motion planning that supports long-range planning over hundreds of kilometres in complicated flows. The idea is to search a reduced space of control inputs that consists of stream functions whose level sets, or streamlines, optimally connect two given points. Such stream functions are generated by superimposing a control input onto the underlying current flow. A streamline represents the resulting path that a vehicle would follow as it is carried along by the current given that control input. We provide rigorous analysis that shows how our method avoids exhaustive search of the control space, and demonstrate simulated examples in complicated flows including a traversal along the east coast of Australia, using actual current predictions, between Sydney and Brisbane.

Akash Arora, P. Michael Furlong, Robert Fitch et al.

Robotic science missions in remote environments, such as deep ocean and outer space, can involve studying phenomena that cannot directly be observed using on-board sensors but must be deduced by combining measurements of correlated variables with domain knowledge. Traditionally, in such missions, robots passively gather data along prescribed paths, while inference, path planning, and other high level decision making is largely performed by a supervisory science team. However, communication constraints hinder these processes, and hence the rate of scientific progress. This paper presents an active perception approach that aims to reduce robots' reliance on human supervision and improve science productivity by encoding scientists' domain knowledge and decision making process on-board. We use Bayesian networks to compactly model critical aspects of scientific knowledge while remaining robust to observation and modeling uncertainty. We then formulate path planning and sensor scheduling as an information gain maximization problem, and propose a sampling-based solution based on Monte Carlo tree search to plan informative sensing actions which exploit the knowledge encoded in the network. The computational complexity of our framework does not grow with the number of observations taken and allows long horizon planning in an anytime manner, making it highly applicable to field robotics. Simulation results show statistically significant performance improvements over baseline methods, and we validate the practicality of our approach through both hardware experiments and simulated experiments with field data gathered during the NASA Mojave Volatiles Prospector science expedition.

Akash Arora, Robert Fitch, Salah Sukkarieh

Autonomous Science is a field of study which aims to extend the autonomy of exploration robots from low level functionality, such as on-board perception and obstacle avoidance, to science autonomy, which allows scientists to specify missions at task level. This will enable more remote and extreme environments such as deep ocean and other planets to be studied, leading to significant science discoveries. This paper presents an approach to extend the high level autonomy of robots by enabling them to model and reason about scientific knowledge on-board. We achieve this by using Bayesian networks to encode scientific knowledge and adapting Monte Carlo Tree Search techniques to reason about the network and plan informative sensing actions. The resulting knowledge representation and reasoning framework is anytime, handles large state spaces and robust to uncertainty making it highly applicable to field robotics. We apply the approach to a Mars exploration mission in which the robot is required to plan paths and decide when to use its sensing modalities to study a scientific latent variable of interest. Extensive simulation results show that our approach has significant performance benefits over alternative methods. We also demonstrate the practicality of our approach in an analog Martian environment where our experimental rover, Continuum, plans and executes a science mission autonomously.

Oliver M. Cliff, Mikhail Prokopenko, Robert Fitch

In this work, we are interested in structure learning for a set of spatially distributed dynamical systems, where individual subsystems are coupled via latent variables and observed through a filter. We represent this model as a directed acyclic graph (DAG) that characterises the unidirectional coupling between subsystems. Standard approaches to structure learning are not applicable in this framework due to the hidden variables, however we can exploit the properties of certain dynamical systems to formulate exact methods based on state space reconstruction. We approach the problem by using reconstruction theorems to analytically derive a tractable expression for the KL-divergence of a candidate DAG from the observed dataset. We show this measure can be decomposed as a function of two information-theoretic measures, transfer entropy and stochastic interaction. We then present two mathematically robust scoring functions based on transfer entropy and statistical independence tests. These results support the previously held conjecture that transfer entropy can be used to infer effective connectivity in complex networks.

Oliver M. Cliff, Mikhail Prokopenko, Robert Fitch

The behaviour of many real-world phenomena can be modelled by nonlinear dynamical systems whereby a latent system state is observed through a filter. We are interested in interacting subsystems of this form, which we model by a set of coupled maps as a synchronous update graph dynamical systems. Specifically, we study the structure learning problem for spatially distributed dynamical systems coupled via a directed acyclic graph. Unlike established structure learning procedures that find locally maximum posterior probabilities of a network structure containing latent variables, our work exploits the properties of dynamical systems to compute globally optimal approximations of these distributions. We arrive at this result by the use of time delay embedding theorems. Taking an information-theoretic perspective, we show that the log-likelihood has an intuitive interpretation in terms of information transfer.