Many applications of path planning in time-varying flow fields, particularly in areas such as marine robotics and ship routing, can be modelled as instances of the time-varying shortest path (TDSP) problem. Although there are no known polynomial-time solutions to TDSP in general, our recent work has identified a tractable case where the flow is modelled as piecewise constant. Extending this method to allow for computational reuse in larger multi-query problems, however, requires additional thought. This paper shows that the piecewise-linear form of the cost function employed in previously work can be used to build an analogy of a shortest path tree, thereby enabling optimal concatenation of sub-problem solutions in the absence of an optimal substructure, and without uniform time discretisation. We present a framework for multi-query TDSP that finds an optimal path that passes through a defined sequence of waypoints and is computationally efficient. Performance comparison is provided in simulation that shows large (up to 100x) speedup compared to a naive approach. This result is significant for applications such as ship routing, where route evaluation is a desirable capability.

We consider the coordinated escort problem, where a decentralised team of supporting robots implicitly assist the mission of higher-value principal robots. The defining challenge is how to evaluate the effect of supporting robots' actions on the principal robots' mission. To capture this effect, we define two novel auxiliary reward functions for supporting robots called satisfaction improvement and satisfaction entropy, which computes the improvement in probability of mission success, or the uncertainty thereof. Given these reward functions, we coordinate the entire team of principal and supporting robots using decentralised cross entropy method (Dec-CEM), a new extension of CEM to multi-agent systems based on the product distribution approximation. In a simulated object avoidance scenario, our planning framework demonstrates up to two-fold improvement in task satisfaction against conventional decoupled information gathering. The significance of our results is to introduce a new family of algorithmic problems that will enable important new practical applications of heterogeneous multi-robot systems.

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.

We present a planning framework for min-imising the deterministic worst-case error in sparse Gaus-sian process (GP) regression. We first derive a univer-sal worst-case error bound for sparse GP regression with bounded noise using interpolation theory on reproducing kernel Hilbert spaces (RKHSs). By exploiting the conditional inde-pendence (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.

We present a new algorithm for coordinating the motion of multiple extruders to increase throughput in fused filament fabrication (FFF)/fused deposition modeling (FDM) additive manufacturing. Platforms based on FFF are commonly available and advantageous to several industries, but are limited by slow fabrication time and could be could be significantly improved through efficient use of multiple extruders. We propose the coordinated toolpath planning problem for systems of extruders mounted as end-effectors on robot arms with the objective of maximizing utilization and avoiding collisions. Building on the idea of dependency graphs introduced in our earlier work, we develop a planning and control framework that precomputes a set of multi-layer toolpath segments from the input model and efficiently assigns them to individual extruders such that executed toolpaths are collision-free. Our method overcomes key limitations of existing methods, including utilization loss from workspace partitioning, precomputed toolpaths subject to collisions with the partially fabricated object, and wasted motion resulting from strict layer-by-layer fabrication. We report simulation results that show a major increase in utilization compared to single and multi-extruder methods, and favorable fabrication results using commodity hardware that demonstrate the feasibility of our method in practice.

Systems of multiple low-cost, underactuated floats combined with fully actuated surface vessels can improve the scalability and cost-effectiveness of autonomous systems for marine science and environmental monitoring. Here, we consider a coordination problem where surface vessels must drop off floats at locations such that they are likely to drift to observe given points of interest, and later must pick up the floats for redeployment. We define the Multi-Vessel Multi-Float (MVMF) problem and present a hierarchical solution based on the Dec-MCTS algorithm. Our solution defines customised sampling, rollout, and action generation algorithms to accommodate the problem’s large search space and provide computational performance sufficient for practical application. We report analytical and simulation results that demonstrate the computational efficiency of our method and validate its behaviour in practical problems. These results immediately enable field experiments to progress the development of this exciting concept in multi-robot marine systems.

Heterogeneous multi-robot systems are advantageous for operations in unknown environments because functionally specialised robots can gather environmental information, while others perform tasks. We de ne 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.

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.

We present a path planning framework for marine robots subject to uncertain ocean currents that exploits data from ensemble forecasting, which is a technique for current prediction used in oceanography. Ensemble forecasts represent a distribution of predicted currents as a set of flow fields that are considered to be equally likely. We show that the typical approach of computing the vector-wise mean and variance over this set can yield meaningless results, and propose an alternative approach that considers each flow field in the ensemble simultaneously. Our framework finds a sequence of vehicle controls that minimises the root-mean-square error distance (RMSE) over the full set of ensemble-induced trajectories. The key to achieving computational efficiency in this approach is our use of Monte Carlo tree search (MCTS) with a specialised heuristic that improves convergence rate while preserving asymptotic optimality and the anytime property. We demonstrate our results using real ensemble forecasts provided by the Australian Bureau of Meteorology, and provide comparisons with the deterministic mean-based approach where we observe RMSE reductions of 92% and 43% in two example scenarios. Further, we argue that the framework can be used in a plan-as-you-go manner where ensemble forecasts change over time. These results help to introduce ensemble forecasts as a viable source of data to improve path planning in marine robotics.

We present an efficient approach for finding shortest paths in flow fields that vary as a sequence of flow predictions over time. This approach is applicable to motion planning for slow marine robots that are subject to dynamic ocean currents. Although the problem is NP-hard in general form, we incorporate recent results from the theory of finding shortest paths in time-dependent graphs to construct a polynomial-time algorithm that finds continuous trajectories in time-dependent flow fields. The algorithm has a hierarchical structure where a graph is constructed with time-varying edge costs that are derived from sets of continuous trajectories in the underlying flow field. We show that the continuous algorithm retains the time complexity and path quality properties of the discrete graph solution, and demonstrate its application to surface and underwater vehicles including a traversal along the East Australian Current with an autonomous marine vehicle. Results show that the algorithm performs efficiently in practice and can find paths that adapt to changing ocean currents. These results are significant to marine robotics because they allow for efficient use of time-varying ocean predictions for motion planning.

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.

The most widely used methods for toolpath planning in 3D printing slice the input model into successive 2D layers to construct the toolpath. Unfortunately the methods can incur a substantial amount of wasted motion (i.e., the extruder is moving while not printing). 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 that optimize objective functions (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 generalpurpose 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 examine the performance on MCTS against our previous best local search-based algorithm in terms of toolpath quality. We show that a relatively short time budget for MCTS yields results on par with local search, while a larger time budget yields a 15% improvement in quality over local search. Additionally, we examine the properties of the models and MCTS executions that lead to better or worse results.

Multi-modal estimation systems have the advantage of increased accuracy and robustness. To achieve accurate sensor fusion with these types of systems, a reliable extrinsic calibration between each sensor pair is critical. This paper presents a novel self-calibration framework for lidar-inertial systems. The key idea of this work is to use an informative path planner to find the admissible path that produces the most accurate calibration of such systems in an unknown environment within a given time budget. This is embedded into a simultaneous localization, mapping and calibration lidar-inertial system, which involves challenges in dealing with agile motions for excitation and large amount of data. Our approach has two stages: firstly, the environment is explored and mapped following a pre-defined path; secondly, the map is exploited to find a continuous and differentiable path that maximises the information gain within a sampling-based planner. We evaluate the proposed self-calibration method in a simulated environment and benchmark it with standard predefined paths to show its performance.

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.

We consider the problem of reconstructing regions of interest of a scene using multiple robot arms and RGB-D sensors. This problem is motivated by a variety of applications, such as precision agriculture and infrastructure inspection. A viewpoint evaluation function is presented that exploits predicted observations and the geometry of the scene. A recently proposed non-myopic planning algorithm, Decentralised Monte Carlo tree search, is used to coordinate the actions of the robot arms. Motion planning is performed over a navigation graph that considers the high-dimensional configuration space of the robot arms. Extensive simulated experiments are carried out using real sensor data and then validated on hardware with two robot arms. Our proposed targeted information gain planner is compared to state-of-the-art baselines and outperforms them in every measured metric. The robots quickly observe and accurately detect fruit in a trellis structure, demonstrating the viability of the approach for real-world applications.

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.

Autonomous underwater gliders frequently execute extensive missions with high levels of uncertainty due to limitations of sensing, control and oceanic forecasting. Glider path planning seeks an optimal path with respect to conflicting objectives, such as travel cost and safety, that must be explicitly balanced subject to these uncertainties. In this paper, we derive a set of recursive equations for state probability and expected travel cost conditional on safety, and use them to implement a new stochastic variant of FMT* in the context of two types of objective functions that allow a glider to reach a destination region with minimum cost or maximum probability of arrival given a safety threshold. We demonstrate the framework using three simulated examples that illustrate how user-prescribed safety constraints affect the results.

Formal methods based on the Markov decision process formalism, such as probabilistic computation tree logic (PCTL), can be used to analyse and synthesise control policies that maximise the probability of mission success. In this paper, we consider a different objective. We wish to minimise time-to-completion while satisfying a given probabilistic threshold of success. This important problem naturally arises in motion planning for outdoor robots, where high quality mobility prediction methods are available but stochastic path planning typically relies on an arbitrary weighted cost function that attempts to balance the opposing goals of finding safe paths (minimising risk) while making progress towards the goal (maximising reward). We propose novel algorithms for model checking and policy synthesis in PCTL that (1) provide a quantitative measure of safety and completion time for a given policy, and (2) synthesise policies that minimise completion time with respect to a given safety threshold. We provide simulation results in a stochastic outdoor navigation domain that illustrate policies with varying levels of risk.