Robert Fitch

ICRA Conference 2025 Conference Paper

Efficient Path Planning in Complex Environments with Trust Region Continuous Belief Tree Search

• Andre Nuñez
• Felix H. Kong
• Alberto González-Cantos
• Robert Fitch

Real-world applications of path planning must contend with complicated constraint and objective functions imposed by the surrounding operational and regulatory environment. Traditional methods such as PRM* and RRT* have asymptotic guarantees, but often struggle in practice with complex blackbox objective/constraint functions, especially in compute-limited situations. Continuous Belief Tree Search (CBTS) addresses these limitations by maintaining local estimates of the objective function in order to sample new nodes from continuous space, often giving high-quality solutions more quickly. However, CBTS requires careful tuning of a control duration parameter, which introduces a tradeoff between compute time and path cost/feasibility. In environments with complex costs and constraints, there may be no single control duration that gives good paths in short compute time. This paper proposes Trust Region CBTS (TR-CBTS), an extension of CBTS with an adaptive control duration parameter inspired by trust region methods. TR-CBTS adjusts control duration based on information from recently sampled candidate nodes, allowing longer control duration where possible to speed up compute time, and shortening control duration when precise navigation in environments with complex, unknown constraint and objective functions. We show TR-CBTS outperforms existing comparable planners for a realistic robotic path planning application in autonomous ship routing.

ICRA Conference 2024 Conference Paper

Communicating Intent as Behaviour Trees for Decentralised Multi-Robot Coordination

• Rhett Hull
• Diluka Moratuwage
• Emily Scheide
• Robert Fitch
• Graeme Best

We propose a decentralised multi-robot coordination algorithm that features a rich representation for encoding and communicating each robot’s intent. This representation for “intent messages” enables improved coordination behaviour and communication efficiency in difficult scenarios, such as those where there are unknown points of contention that require negotiation between robots. Each intent message is an adaptive policy that conditions on identified points of contention that conflict with the intentions of other robots. These policies are concisely expressed as behaviour trees via algebraic logic simplification, and are interpretable by robot teammates and human operators. We propose this intent representation in the context of the Dec-MCTS online planning algorithm for decentralised coordination. We present results for a generalised multi-robot orienteering domain that show improved plan convergence and coordination performance over standard Dec-MCTS enabled by the intent representation’s ability to encode and facilitate negotiation over points of contention.

ICRA Conference 2024 Conference Paper

Multi-query TDSP for Path Planning in Time-varying Flow Fields

• James Ju Heon Lee
• Chanyeol Yoo
• Stuart Anstee
• Robert Fitch

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.

ICRA Conference 2023 Conference Paper

Decentralised Active Perception in Continuous Action Spaces for the Coordinated Escort Problem

• Rhett Hull
• Ki Myung Brian Lee
• Jennifer Wakulicz
• Chanyeol Yoo
• James McMahon
• Bryan Clarke
• Stuart Anstee
• Jijoong Kim

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.

ICRA Conference 2023 Conference Paper

Efficient Optimal Planning in non-FIFO Time-Dependent Flow Fields

• James Ju Heon Lee
• Chanyeol Yoo
• Stuart Anstee
• Robert Fitch

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.

IROS Conference 2023 Conference Paper

Risk-Aware Stochastic Ship Routing Using Conditional Value-at-Risk

• Andre Nuñez
• Felix H. Kong
• Alberto González-Cantos
• Robert Fitch

Improving the safety and efficiency of maritime shipping has the potential to reduce carbon emissions and improve profitability. Stochastic ship routing, the problem of finding a safe, efficient, and timely route for a ship is difficult in large part because of uncertainty in weather forecasts, which come as an ensemble, a collection of many possible future weather conditions. Previous safety-aware ship routing methods have used either conservative interpretations of the ensemble by assuming the worst-case weather conditions, leading to excessive fuel consumption, or by using the average weather conditions, leading to potentially unsafe routes. In this paper, we investigate the use of the well-known Conditional Value-at-risk (CVaR) in the objective and constraint functions for ship routing problems, which allows a range of risk tolerances between the average and the worst case. We illustrate the advantages of using CVaR for the problem of ship routing in several simulation examples using real weather forecasts.

ICRA Conference 2023 Conference Paper

Topological Trajectory Prediction with Homotopy Classes

• Jennifer Wakulicz
• Ki Myung Brian Lee
• Teresa A. Vidal-Calleja
• Robert Fitch

Trajectory prediction in a cluttered environment is key to many important robotics tasks such as autonomous navigation. However, there are an infinite number of possible trajectories to consider. To simplify the space of trajectories under consideration, we utilise homotopy classes to partition the space into countably many mathematically equivalent classes. All members within a class demonstrate identical high-level motion with respect to the environment, i. e. , travelling above or below an obstacle. This allows high-level prediction of a trajectory in terms of a sparse label identifying its homotopy class. We therefore present a light-weight learning framework based on variable-order Markov processes to learn and predict homotopy classes and thus high-level agent motion. By informing a Gaussian mixture model (GMM) with our homotopy class predictions, we see great improvements in low-level trajectory prediction compared to a naive GMM on a real dataset.

IROS Conference 2022 Conference Paper

Bio-inspired 2D Vertical Climbing with a Novel Tripedal Robot

• Clyde Webster
• Felix H. Kong
• Robert Fitch

Climbing robots have the potential to revolutionize the maintenance and inspection operations of many types of vertical structures. In nature, parrots exhibit a remarkable capacity for manipulation during climbing behaviors, for which robotics can benefit from studying. In this paper we present a novel tripedal robot that is inspired by the morphology of these impressive birds, which use their legs and beak in a tripedal fashion when climbing. We propose several foot placement, trajectory generation, and control methods for this system along with performance evaluation in simulation. A video of select simulations and live bird data is included in the supplementary material, and can also be found at https://youtu.be/vRVGralyQgQ.

IROS Conference 2022 Conference Paper

Coordinated Toolpath Planning for Multi-Extruder Additive Manufacturing

• Jayant Khatkar
• Chanyeol Yoo
• Robert Fitch
• Lee M. Clemon
• Ramgopal Mettu

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.

ICRA Conference 2022 Conference Paper

Informative Planning for Worst-Case Error Minimisation in Sparse Gaussian Process Regression

• Jennifer Wakulicz
• Ki Myung Brian Lee
• Chanyeol Yoo
• Teresa A. Vidal-Calleja
• Robert Fitch

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.

IROS Conference 2021 Conference Paper

3D Ensemble-Based Online Oceanic Flow Field Estimation for Underwater Glider Path Planning

• Felix H. Kong
• Kwun Yiu Cadmus To
• Gary Brassington
• Stuart Anstee
• Robert Fitch

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 vertical velocity 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.

ICRA Conference 2021 Conference Paper

An Upper Confidence Bound for Simultaneous Exploration and Exploitation in Heterogeneous Multi-Robot Systems

• Ki Myung Brian Lee
• Felix H. Kong
• Ricardo Cannizzaro
• Jennifer L. Palmer
• David Johnson
• Chanyeol Yoo
• Robert Fitch

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.

ICRA Conference 2021 Conference Paper

Estimation of Spatially-Correlated Ocean Currents from Ensemble Forecasts and Online Measurements

• Kwun Yiu Cadmus To
• Felix H. Kong
• Ki Myung Brian Lee
• Chanyeol Yoo
• Stuart Anstee
• Robert Fitch

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.

ICRA Conference 2021 Conference Paper

Hierarchical MCTS for Scalable Multi-Vessel Multi-Float Systems

• Giovanni D'Urso
• James Ju Heon Lee
• Oscar Pizarro
• Chanyeol Yoo
• Robert Fitch

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.

ICRA Conference 2021 Conference Paper

Path Planning in Uncertain Ocean Currents using Ensemble Forecasts

• Chanyeol Yoo
• James Ju Heon Lee
• Stuart Anstee
• Robert Fitch

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.

ICRA Conference 2021 Conference Paper

Signal Temporal Logic Synthesis as Probabilistic Inference

• 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.

ICRA Conference 2020 Conference Paper

An Efficient Planning and Control Framework for Pruning Fruit Trees

• Alexander You
• Fouad Sukkar
• Robert Fitch
• Manoj Karkee
• Joseph R. Davidson

Dormant pruning is a major cost component of fresh market tree fruit production, nearly equal in scale to harvesting the fruit. However, relatively little focus has been given to the problem of pruning trees autonomously. In this paper, we introduce a robotic system consisting of an industrial manipulator, an eye-in-hand RGB-D camera configuration, and a custom pneumatic cutter. The system is capable of planning and executing a sequence of cuts while making minimal assumptions about the environment. We leverage a novel planning framework designed for high-throughput operation which builds upon previous work to reduce motion planning time and sequence cut points intelligently. In end-to-end experiments with a set of ten different branch configurations, the system achieved a high success rate in plan execution and a 1. 5x speedup in throughput versus a baseline planner, representing a significant step towards the goal of practical implementation of robotic pruning.

ICRA Conference 2020 Conference Paper

Distance and Steering Heuristics for Streamline-Based Flow Field Planning

• Kwun Yiu Cadmus To
• Chanyeol Yoo
• Stuart Anstee
• Robert Fitch

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.

ICRA Conference 2020 Conference Paper

Efficient Updates for Data Association with Mixtures of Gaussian Processes

• Ki Myung Brian Lee
• Wolfram Martens
• Jayant Khatkar
• Robert Fitch
• Ramgopal Mettu

Gaussian processes (GPs) enable a probabilistic approach to important estimation and classification tasks that arise in robotics applications. Meanwhile, most GP-based methods are often prohibitively slow, thereby posing a substantial barrier to practical applications. Existing "sparse" methods to speed up GPs seek to either make the model more sparse, or find ways to more efficiently manage a large covariance matrix. In this paper, we present an orthogonal approach that memoises (i. e. reuses) previous computations in GP inference. We demonstrate that a substantial speedup can be achieved by incorporating memoisation into applications in which GPs must be updated frequently. Moreover, we derive a novel online update scheme for sparse GPs that can be used in conjunction with our memoisation approach for a synergistic improvement in performance. Across three robotic vision applications, we demonstrate between 40-100% speed-up over the standard method for inference in GP mixtures.

ICRA Conference 2020 Conference Paper

Hierarchical Planning in Time-Dependent Flow Fields for Marine Robots

• James Ju Heon Lee
• Chanyeol Yoo
• Stuart Anstee
• Robert Fitch

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.

IROS Conference 2020 Conference Paper

Information Driven Self-Calibration for Lidar-Inertial Systems

• Mitchell Usayiwevu
• Cedric Le Gentil
• Jasprabhjit Mehami
• Chanyeol Yoo
• Robert Fitch
• Teresa A. Vidal-Calleja

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.

ICRA Conference 2020 Conference Paper

Toward Optimal FDM Toolpath Planning with Monte Carlo Tree Search

• Chanyeol Yoo
• Samuel Lensgraf
• Robert Fitch
• Lee M. Clemon
• Ramgopal Mettu

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.

ICRA Conference 2019 Conference Paper

Multi-Robot Region-of-Interest Reconstruction with Dec-MCTS

• Fouad Sukkar
• Graeme Best
• Chanyeol Yoo
• Robert Fitch

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.

ICRA Conference 2019 Conference Paper

On-line 3D active pose-graph SLAM based on key poses using graph topology and sub-maps

• Yongbo Chen 0001
• Shoudong Huang
• Robert Fitch
• Liang Zhao 0003
• Huan Yu
• Di Yang

In this paper, we present an on-line active pose-graph simultaneous localization and mapping (SLAM) frame-work for robots in three-dimensional (3D) environments using graph topology and sub-maps. This framework aims to find the best trajectory for loop-closure by re-visiting old poses based on the T-optimality and D-optimality metrics of the Fisher information matrix (FIM) in pose-graph SLAM. In order to reduce computational complexity, graph topologies are introduced, including weighted node degree (T-optimality metric) and weighted tree-connectivity (D-optimality metric), to choose a candidate trajectory and several key poses. With the help of the key poses, a sampling-based path planning method and a continuous-time trajectory optimization method are combined hierarchically and applied in the whole framework. So as to further improve the real-time capability of the method, the sub-map joining method is used in the estimation and planning process for large-scale active SLAM problems. In simulations and experiments, we validate our approach by comparing against existing methods, and we demonstrate the on-line planning part using a quad-rotor unmanned aerial vehicle (UAV).

ICRA Conference 2019 Conference Paper

Online Estimation of Ocean Current from Sparse GPS Data for Underwater Vehicles

• Ki Myung Brian Lee
• Chanyeol Yoo
• Ben Hollings
• Stuart Anstee
• Shoudong Huang
• Robert Fitch

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.

IROS Conference 2019 Conference Paper

Stochastic Path Planning for Autonomous Underwater Gliders with Safety Constraints

• Chanyeol Yoo
• Stuart Anstee
• Robert Fitch

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$^{\ast }$ 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.

ICRA Conference 2019 Conference Paper

Streamlines for Motion Planning in Underwater Currents

• Kwun Yiu Cadmus To
• Ki Myung Brian Lee
• Chanyeol Yoo
• Stuart Anstee
• Robert Fitch

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.

IROS Conference 2018 Conference Paper

Decentralised Mission Monitoring with Spatiotemporal Optimal Stopping

• Graeme Best
• Shoudong Huang
• Robert Fitch

We consider a multi-robot variant of the mission monitoring problem. This problem arises in tasks where a robot observes the progress of another robot that is stochastically following a known trajectory, among other applications. We formulate and solve a variant where multiple tracker robots must monitor a single target robot, which is important because it enables the use of multi-robot systems to improve task performance in practice, such as in marine robotics missions. Our algorithm coordinates the behaviour of the trackers by computing optimal single-robot paths given a probabilistic representation of the other robots' paths. We employ a decentralised scheme that optimises over probability distributions of plans and has useful analytical properties. The planned trajectories collectively maximise the probability of observing the target throughout the mission with respect to probabilistic motion and observation models. We report simulation results for up to 8 robots that support our analysis and indicate that our algorithm is a feasible solution for improving the performance of mission monitoring systems.

ICRA Conference 2018 Conference Paper

Efficient Active SLAM Based on Submap Joining, Graph Topology and Convex Optimization

• Yongbo Chen 0001
• Shoudong Huang
• Robert Fitch
• Jianqiao Yu

The active SLAM problem considered in this paper aims to plan a robot trajectory for simultaneous localization and mapping (SLAM) as well as for an area coverage task with robot pose uncertainty. Based on a model predictive control (MPC) framework, these two problems are solved respectively by different methods. For the uncertainty minimization MPC problem, based on the graphical structure of the 2D feature-based SLAM, a non-convex constrained least-squares problem is presented to approximate the original problem. Then, using variable substitutions, it is further transformed into a convex problem, and then solved by a convex optimization method. For the coverage task considering robot pose uncertainty, it is formulated and solved by the MPC framework and the sequential quadratic programming (SQP) method. In the whole process, considering the computation complexity, we use linear SLAM, which is a submap joining approach, to reduce the time for planning and estimation. Finally, various simulations are presented to validate the effectiveness of the proposed approach.

ICRA Conference 2018 Conference Paper

Planning-Aware Communication for Decentralised Multi-Robot Coordination

• Graeme Best
• Michael Forrai
• Ramgopal Mettu
• Robert Fitch

We present an algorithm for selecting when to communicate during online planning phases of coordinated multi-robot missions. The key idea is that a robot decides to request communication from another robot by reasoning over the predicted information value of communication messages over a sliding time-horizon, where communication messages are probability distributions over action sequences. We formulate this problem in the context of the recently proposed decentralised Monte Carlo tree search (Dec-MCTS) algorithm for online, decentralised multi-robot coordination. We propose a particle filter for predicting the information value, and a polynomial-time belief-space planning algorithm for finding the optimal communication schedules in an online and decentralised manner. We evaluate the benefit of informative communication planning for a multi-robot information gathering scenario with 8 simulated robots. Our results show reductions in channel utilisation of up to four-fifths with surprisingly little impact on coordination performance.

IROS Conference 2017 Conference Paper

An approach to autonomous science by modeling geological knowledge in a Bayesian framework

• 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.

IROS Conference 2016 Conference Paper

Communication-efficient motion coordination and data fusion in information gathering teams

• Abdallah Kassir
• Robert Fitch
• Salah Sukkarieh

Multi-robot information gathering teams typically require communication for data fusion and cooperative decision making. However, when communication takes place over wireless networks, stringent bandwidth limits apply. These limits raise the need for efficient utilisation of available communication resources in a manner that balances information gathering utility with communication costs or limits. In our previous work, we introduced the dynamic information flow (DIF) problem as a general formulation of this trade-off. We introduced two variants of the problem addressing the issue of communication efficiency for data fusion only. In this paper, we extend one of the variants to address communication efficiency for both data fusion and cooperative decision making in a synergistic manner. We present a solution to this new variant that integrates a multi-cast routing algorithm with information structure optimisation. This solution allows teams that involve high-data-rate sensors and tight coordination to respect bandwidth limits. Through several simulations we verify that our solution significantly reduces bandwidth usage of such teams while maintaining information gathering performance.

ICRA Conference 2016 Conference Paper

Informative soaring with drifting thermals

• Joseph L. Nguyen
• Nicholas R. J. Lawrance
• Robert Fitch
• Salah Sukkarieh

The informative soaring (IFS) problem involves a gliding unmanned aerial vehicle (UAV) exploiting energy from thermals to extend its information gathering capability. In this paper, we address the realistic situation of detecting new thermals drifting with the wind in the search environment. We consider complex target-search scenarios characterised by information clusters and propose a new set of algorithms designed to both explore for and exploit high-value thermals to maximise information gain. Our algorithms: 1) compute a thermal exploration map to detect useful thermals that eventually intercept clusters, 2) solve a boundary value problem for inter-thermal path segment (ITP) generation with moving thermals, 3) compute thermal time windows to gather information from clusters and form a cluster service schedule, and 4) use branch and bound (BnB) tree search for global planning, considering high-utility-rate ITPs to maximise information gain. Our solution is compared against a greedy method that neither considers the thermal exploration map nor cluster schedule and a full knowledge method that has access to all thermals. Numerical simulations show that on average, our solution outperforms the greedy method in one-third of 2400 Monte Carlo trials, and achieves similar performance to the full knowledge method when environmental conditions are favourable.

IROS Conference 2016 Conference Paper

Multi-robot path planning for budgeted active perception with self-organising maps

• Graeme Best
• Jan Faigl
• Robert Fitch

We propose a self-organising map (SOM) algorithm as a solution to a new multi-goal path planning problem for active perception and data collection tasks. We optimise paths for a multi-robot team that aims to maximally observe a set of nodes in the environment. The selected nodes are observed by visiting associated viewpoint regions defined by a sensor model. The key problem characteristics are that the viewpoint regions are overlapping polygonal continuous regions, each node has an observation reward, and the robots are constrained by travel budgets. The SOM algorithm jointly selects and allocates nodes to the robots and finds favourable sequences of sensing locations. The algorithm has polynomial-bounded runtime independent of the number of robots. We demonstrate feasibility for the active perception task of observing a set of 3D objects. The viewpoint regions consider sensing ranges and self-occlusions, and the rewards are measured as discriminability in the ensemble of shape functions feature space. Simulations were performed using a 3D point cloud dataset from a real robot in a large outdoor environment. Our results show the proposed methods enable multi-robot planning for budgeted active perception tasks with continuous sets of candidate viewpoints and long planning horizons.

IROS Conference 2015 Conference Paper

Bayesian intention inference for trajectory prediction with an unknown goal destination

• Graeme Best
• Robert Fitch

Contextual cues can provide a rich source of information for robots that operate in the presence of other agents such as people, animals, vehicles and fellow robots. We are interested in context, in the form of the behavioural intent of an agent, for enhanced trajectory prediction. We present a Bayesian framework that estimates both the intended goal destination and future trajectory of a mobile agent moving among multiple static obstacles. Our method is based on multi-modal hypotheses of the intended goal, and is focused primarily on the long-term trajectory of the agent. We propose a computationally efficient solution and demonstrate its behaviour in a pedestrian scenario with a real-world data set. Results show the benefits of our method in comparison to traditional trajectory prediction methods and illustrate the feasibility of integration with higher-level planning algorithms.

ICRA Conference 2013 Conference Paper

Bootstrapping navigation and path planning using human positional traces

• Alen Alempijevic
• Robert Fitch
• Nathan Kirchner

Navigating and path planning in environments with limited a priori knowledge is a fundamental challenge for mobile robots. Robots operating in human-occupied environments must also respect sociocontextual boundaries such as personal workspaces. There is a need for robots to be able to navigate in such environments without having to explore and build an intricate representation of the world. In this paper, a method for supplementing directly observed environmental information with indirect observations of occupied space is presented. The proposed approach enables the online inclusion of novel human positional traces and environment information into a probabilistic framework for path planning. Encapsulation of sociocontextual information, such as identifying areas that people tend to use to move through the environment, is inherently achieved without supervised learning or labelling. Our method bootstraps navigation with indirectly observed sensor data, and leverages the flexibility of the Gaussian process (GP) for producing a navigational map that sampling based path planers such as Probabilistic Roadmaps (PRM) can effectively utilise. Empirical results on a mobile platform demonstrate that a robot can efficiently and socially-appropriately reach a desired goal by exploiting the navigational map in our Bayesian statistical framework.

ICRA Conference 2013 Conference Paper

Decentralised coordination of mobile robots for target tracking with learnt utility models

• Zhe Xu
• Robert Fitch
• Salah Sukkarieh

This paper addresses the coordination of a decentralised robot team for target tracking. In many approaches to coordination, robots jointly plan their actions through negotiation, which incurs communication costs. Previous work examined the use of learning to reduce the need for negotiations in a network of static robots. Robots incrementally learn how each team member impacts the team utility and can thus make coordinated, team-wide decisions. In this paper, we extend the concept of learning utility models to a team of mobile robots. We also propose a mechanism by which robots switch between negotiating and using the learnt model. This mechanism reduces the communications required for coordination whilst maintaining the same level of tracking performance. Hardware experiments demonstrated that our approach resulted in coordinated behaviours while only negotiating intermittently. Simulation results show that our approach reduced the data communicated for negotiations by up to 70%, without making a statistically significant impact on the tracking performance.

ICRA Conference 2013 Conference Paper

Energy-constrained motion planning for information gathering with autonomous aerial soaring

• Joseph L. Nguyen
• Nicholas R. J. Lawrance
• Robert Fitch
• Salah Sukkarieh

Autonomous aerial soaring presents a unique opportunity to extend the flight duration of Unmanned Aerial Vehicles (UAVs). In this paper, we examine the problem of a gliding UAV searching for a ground target while simultaneously collecting energy from known thermal energy sources. The problem is posed as a tree search problem by noting that a long-duration mission can be divided into similar segments of flying between and climbing in thermals. The algorithm attempts to maximise the probability of detecting a target by exploring a tree of the possible thermal-to-thermal transitions to a fixed search depth and executing the highest utility plan. The sensitivity of the algorithm to different search depths is explored, and the method is compared against a locally-optimal myopic search algorithm. In larger, more complicated problems, the suggested method outperforms myopic search by sacrificing short-term utility to reach more valuable exploration areas later in the mission.

ICRA Conference 2013 Conference Paper

Provably-correct stochastic motion planning with safety constraints

• Chanyeol Yoo
• Robert Fitch
• Salah Sukkarieh

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.

ICRA Conference 2012 Conference Paper

Decentralised information gathering with communication costs

• Abdallah Kassir
• Robert Fitch
• Salah Sukkarieh

Advantages of decentralised decision making systems for multi-agent robotic tasks are limited by the heavy demand they impose on communication. This paper presents an approach to control communication for the LQ team problem, namely a team of agents with linear dynamics and quadratic team cost. Communication costs are added to the objective of the LQ optimal control linear matrix inequality formulation, allowing for a well-defined balancing of communication costs and team performance. Results show a reduction in communication consistent with the specified cost and in a manner that upholds team performance relative to the reduced communication footprint. The applicability of the approach has also been extended to information gathering tasks through local LQ approximations along the agents' paths. Simulation testing on a sample two-agent problem shows a 40% reduction in communication with negligible impact on performance.

ICRA Conference 2012 Conference Paper

Learning utility models for decentralised coordinated target tracking

• Zhe Xu
• Robert Fitch
• Salah Sukkarieh

In decentralised target tracking, a set of sensors observes moving targets. When the sensors are static but steerable, each sensor must dynamically choose which target to observe in a decentralised manner. We show that the information exchanged by the sensors to synchronise their beliefs can be exploited to learn a model of the utility function that drives each others' decisions. Instead of communicating utilities to enable negotiation, each sensor regresses on the learnt model to predict the utilities of other team members. This approach bridges the gap between coordinating implicitly, a locally-greedy solution, and negotiating explicitly. We validated our approach in both hardware and simulations, and found that it out-performed implicit coordination by a statistically significant margin with both ideal and limited communications.

IROS Conference 2012 Conference Paper

Motion planning and stochastic control with experimental validation on a planetary rover

• Rowan McAllister
• Thierry Peynot
• Robert Fitch
• Salah Sukkarieh

Motion planning for planetary rovers must consider control uncertainty in order to maintain the safety of the platform during navigation. Modelling such control uncertainty is difficult due to the complex interaction between the platform and its environment. In this paper, we propose a motion planning approach whereby the outcome of control actions is learned from experience and represented statistically using a Gaussian process regression model. This model is used to construct a control policy for navigation to a goal region in a terrain map built using an on-board RGB-D camera. The terrain includes flat ground, small rocks, and non-traversable rocks. We report the results of 200 simulated and 35 experimental trials that validate the approach and demonstrate the value of considering control uncertainty in maintaining platform safety.

ICRA Conference 2012 Conference Paper

Real-time decentralized search with inter-agent collision avoidance

• Seng Keat Gan
• Robert Fitch
• Salah Sukkarieh

This paper addresses the problem of coordinating a team of mobile autonomous sensor agents performing a cooperative mission while explicitly avoiding inter-agent collisions in a team negotiation process. Many multi-agent cooperative approaches disregard the potential hazards between agents, which are an important aspect to many systems and especially for airborne systems. In this work, team negotiation is performed using a decentralized gradient-based optimization approach whereas safety distance constraints are specifically designed and handled using Lagrangian multiplier methods. The novelty of our work is the demonstration of a decentralized form of inter-agent collision avoidance in the loop of the agents' real-time group mission optimization process, where the algorithm inherits the properties of performing its original mission while minimizing the probability of inter-agent collisions. Explicit constraint gradient formulation is derived and used to enhance computational advantage and solution accuracy. The effectiveness and robustness of our algorithm has been verified in a simulated environment by coordinating a team of UAVs searching for targets in a large-scale environment.

ICRA Conference 2011 Conference Paper

A multi-radio architecture for neighbor-to-neighbor communication in modular robots

• Victor Kuo
• Robert Fitch

Decentralized control of modular robots requires reliable inter-module communication. Communication links must tolerate module misalignment and implement the neighbor-to-neighbor communication model. We propose a wireless system based on multiple radios per module that addresses these challenges. Our system scales to large robots because available bandwidth is independent of the number of modules. In this paper, we present our multi-radio single-channel architecture and validate its performance through hardware experiments. Results show that radios can provide reliable neighbor-to-neighbor communication suitable for modular robots.

ICRA Conference 2009 Conference Paper

Experiments with a zigbee wireless communication system for self-reconfiguring modular robots

• Robert Fitch
• Ritesh Lal

The problem of designing reliable low-cost communications systems to support decentralized algorithms is a major research challenge in self-reconfiguring modular robotics. In this paper we evaluate a communication system based on ZigBee, a wireless ad-hoc mesh networking standard. We present a 15-node system prototype and results from an experiment of 300 trials that measures system performance on a benchmark task. The benchmark we chose is the connectivity problem - how to maintain connectivity in the module graph during the disconnections and reconnections that occur during reconfiguration. We also provide full implementation details in pseudocode for our connectivity algorithm. Our results show that, despite its inherent scalability limitations, a ZigBee wireless system is feasible as a simple, low-cost communication system for self-reconfiguring modular robots.

ICRA Conference 2007 Conference Paper

Scalable Locomotion for Large Self-Reconfiguring Robots

• Robert Fitch
• Zack J. Butler

For large self-reconfiguring robots, any algorithm that requires linear amounts of memory per module (with respect to the number of modules) or linear time for computation or communication per actuation is undesirable. While shape-forming may require linear amounts of memory, locomotion can be performed with simpler shape specifications, and therefore sublinear algorithms are possible. In this paper, we present a locomotion technique that performs both planning and actuation control in sublinear time and memory. The algorithm is inspired by reinforcement learning and uses dynamic programming to plan module paths in parallel. To ensure the physical integrity of the overall robot during motion, we have developed a novel localized cooperation scheme which may also be used with other self-reconfiguration algorithms. Our overall algorithm is able to direct locomotion over arbitrary obstacles, and the formulation of the goal used in the planning encourages dynamic stability

ICML Conference 2007 Conference Paper

Tracking value function dynamics to improve reinforcement learning with piecewise linear function approximation

• Chee Wee Phua
• Robert Fitch

ICRA Conference 2005 Conference Paper

Reconfiguration Planning Among Obstacles for Heterogeneous Self-Reconfiguring Robots

• Robert Fitch
• Zack J. Butler
• Daniela Rus

Most reconfiguration planners for self-reconfiguring robots do not consider the placement of specific modules within the configuration. Recently, we have begun to investigate heterogeneous reconfiguration planning in lattice-based systems, in which there are various classes of modules. The start and goal configurations specify the class of each module, in addition to placement. Our previous work presents solutions for this problem with unrestricted free space available to the robot during reconfiguration, and also free space limited to a thin connected region over the entire surface of the configuration. In this paper, we further this restriction and define free space by an arbitrarily-shaped bounding region. This addresses the important problem of reconfiguration among obstacles, and reconfiguration over a rigid surface. Our algorithm plans module trajectories through the volume of the structure, and is divided into two phases: shape-forming, and sorting the goal configuration to correctly position modules by class. The worst-case running time for the first phase is O(n 2 ) with O(n 2 ) moves for an n-module robot, and a loose upper bound for the second phase is O(n 4 ) time and moves. However, we show this bound to be Θ (n 2 )time and moves in common instances.

IROS Conference 2003 Conference Paper

Reconfiguration planning for heterogeneous self-reconfiguring robots

• Robert Fitch
• Zack J. Butler
• Daniela Rus

Current research in self-reconfiguring robots focuses predominantly on systems of identical modules. However, allowing modules of varying types, with different sensors, for example, is of practical interest. In this paper, we propose the development of an algorithmic basis for heterogeneous self-reconfiguring systems. We demonstrate algorithmic feasibility by presenting O(n/sup 2/) time centralized and O(n/sup 3/) time decentralized solutions to the reconfiguration problem for n non-identical modules. As our centralized time bound is equal to the best published homogeneous solution, we argue that space, as opposed to time, is the critical resource in the reconfiguration problem. Our results encourage the development both of applications that use heterogeneous self-reconfiguration, and also heterogeneous hardware systems.

ICRA Conference 2002 Conference Paper

Distributed Goal Recognition Algorithms for Modular Robots

• Zack J. Butler
• Robert Fitch
• Daniela Rus
• Yuhang Wang

Modular robots are systems composed of a number of independent units that can be reconfigured to fit the task at hand. When the modules are computationally independent, they form a large distributed system with no central controller. We are concerned with the ability of such modular robots to easily recognize the achievement (or lack thereof) of a given goal configuration. We present algorithms for a class of 2D and 3D modular robots, along with correctness and running time analysis. We have successfully implemented the 2D algorithm on the second-generation Crystalline Atomic robot, a self-reconfigurable modular robot under development in our laboratory and we present implementation details and experimental results.

IROS Conference 2002 Conference Paper

Experiments in distributed locomotion with a unit-compressible modular robot

• Zack J. Butler
• Robert Fitch
• Daniela Rus

Effective algorithms for modular self-reconfiguring robots should be distributed and parallel. In previous work, we explored general algorithms for locomotion and self-replication and their instantiations to systems in which modules move over the surface of the robot. In this work, we present several algorithms applied to the Crystal robot-two new distributed locomotion algorithms designed specifically for unit-compressible actuation, as well as the adaptation of a generic division algorithm to the Crystal. We also present the integration of a locomotion algorithm with a distributed goal recognition algorithm developed previously. This allows the robot to reconfigure and recognize the achievement of its goal, all without the use of a central controller. We have instantiated all of these algorithms on the Crystal hardware, and we present results of our experiments. These experiments empirically verify the utility of our distributed algorithms on a self-reconfiguring system.

IROS Conference 2001 Conference Paper

3D rectilinear motion planning with minimum bend paths

• Robert Fitch
• Zack J. Butler
• Daniela Rus

Computing rectilinear shortest paths in two dimensions has been solved optimally using a number of different techniques. A variety of related problems have been solved, including minimizing the number of bends in the path, the total rectilinear distance, or some combination of both. However, solutions to the 3D versions of these problems are less common. We propose a solution to the 3D minimum-bend path problem, which has theoretical as well as practical interest. Applications include motion planning problems where straight line motion is preferred over taking arbitrary turns. We employ our results in motion planning for self-repair in self-reconfigurable robots.