Chanyeol Yoo

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.

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.

Chanyeol Yoo, Calin Belta

Autonomous agents often operate in uncertain environments where their decisions are made based on beliefs over states of targets. We are interested in controller synthesis for complex tasks defined over belief spaces. Designing such controllers is challenging due to computational complexity and the lack of expressivity of existing specification languages. In this paper, we propose a probabilistic extension to signal temporal logic (STL) that expresses tasks over continuous belief spaces. We present an efficient synthesis algorithm to find a control input that maximises the probability of satisfying a given task. We validate our algorithm through simulations of an unmanned aerial vehicle deployed for surveillance and search missions.