This paper proposes an improved solver for the maximal continuity graph painting problem. The problem is motivated by the real-world surface non-revisiting coverage path planning (NCPP) task carried out by manipulators, where the physical meaning of maximising the colouring continuity in the graph translates to minimising the number of undesirable transitions between end-effector force/torque control discontinuities. Early works have formulated the graph-based representation of the task and finitely solved the graph. However, the exponential growth of its algorithmic complexity makes the problem intractable for even relatively simple graphs. The improved solver proposed in this paper demonstrates exponential improvement compared to the state-of-the-art algorithm, setting guaranteed bounds on performance, whereby the algorithmic complexity is proven reduced by a factor of$2^N$,$N$being the number of internal edges in the graph. Challenging simulated experiments are presented to validate the computational advantage, and an open source implementation is also provided for the benefit of the community.Note to Practitioners—To solve a non-redundant manipulator NCPP task, the first step is collecting all valid inverse kinematics configurations that lead to coverage on the surface. Continuous configurations can then be grouped and assigned the same colour. This process creates a spatial distribution of colours on the target surface, forming a topological graph as detailed in this paper. Using the proposed algorithm, each coverable point on the surface is assigned a colour, which specifies the unique inverse kinematic configuration that the manipulator should adopt to cover such a point. A suitable geometric coverage planner can then be employed to generate the path that a manipulator end-effector must follow on the surface that is guaranteed to have the minimum number of end-effector discontinuities. In this paper, an (open-sourced) solver is proposed to solve the graph optimally from a computational point of view, most notably increasing productivity from a manufacturing/automated perspective.

This paper introduces an optimisation-based trajectory deformation and tracking algorithm for tethered differential-driven mobile robots. The motivation of this work is to generate self-entanglement-free (SEF) commands for a tethered differential-driven robot to track a path. Whilst existing path planners have been capable of generating SEF paths for tethered differential-driven robots lacking an omni-directional tether retracting mechanism, no trajectory planner can handle the unavoidable movement errors that cause robot pose deviate from the pre-defined path. The trajectory deformation and tracking is challenging because the admissible heading direction of the robot is highly constrained by the SEF constraint. As a result, even with an SEF path, the robot still encounters self-entanglement issues during execution.This paper fills this gap by formulating the trajectory deforming and tracking (TDT) problem of a tethered robot into a multi-objective optimisation framework. Explicit consideration of the constraint of the relative angle between the tether stretching direction and the robot’s heading direction to be admissible during its movement is provided in this framework. The proposed algorithm repeatedly deforms the pre-defined path for easier tracking, whilst generating a suitable velocity profile for robot execution. Compared to directly applying the commonly used untethered trajectory deformation and tracking algorithm into tethered cases, the proposed algorithm demonstrates improved performance in terms of minimising the risk of self-entanglement and maximising robot safety. These are validated in both simulated and real scenarios. An open-sourcesourcing implementation has also been provided for the benefit of the robotics community.

A novel algorithm to solve the 2D k-shortest non-homotopic path planning (k-SNPP) task is proposed in this paper. The task is of practical significance as a sub-module for higherlevel planning and scheduling tasks, and is gaining increasing attention and focus in recent years. There have existed algorithms that explicitly characterised non-homotopic paths using topological invariants such as ℎ-signature and winding number. However, these algorithms are inefficient due to their separate treatment of topology and geometry: Topological invariants are singularly utilised for distinguishing non-homotopic property among paths, which significantly increases the volume of the robot configuration space. Meanwhile, distance-optimal path planners search for locally shortest paths in the augmented space, which becomes extremely time-consuming. In this paper, a topological tree is proposed to simultaneously leverage topology and geometry. The tree grows from the starting location and explores all topological routes, until the best k of its leaves reach the goal. It is proven that different branches of the tree explore different homotopy classes of paths, and all the branches are locally shortest. Comparative experiments for k-SNPP are conducted in challenging grid-based simulated environments to validate the performance of the proposed algorithm. The C++ implementation of the proposed algorithm is released for the benefit of the robotics community.

A novel mechanism to derive self-entanglement-free path for tethered differential-driven robots is proposed in this work. The problem is tailored to the applications of tethered robots without an omni-directional tether re-tractor which is often encountered when an omni-directional tether retracting mechanism is incapable of being jointly equipped with other geometrically complex devices (e.g. a manipulator), for instance the disaster recovery, spatial exploration, etc. Without a special consideration on the spatial relation between the pose of the mobile base and the tether, self-entanglement appears when the robot moves, resulting in unsafe motion of the robot and potential damage to the tether. In this paper, the self-entanglement-free constraint is modelled as the admissible orientation of the tether anchoring on the robot with respect to the robot's heading orientation. A searching-based path planning algorithm is then proposed to generate a near optimal path solution with guaranteed null of tether self-entanglement. The effectiveness of the proposed algorithm is compared with the motions without considering self-entanglement-free constraint, illustrated in challenging planning cases, and validated in realworld scenes. An open-source implementation has also been provided for the benefit of the robotics community.

This work considers the optimal non-revisiting coverage tasks with a single non-redundant manipulator for the case when the object can be positioned at a predefined set of locations within the workcell. The scenario is often encountered in typical industrial settings, for instance when the object presents itself along a conveyor belt and its surface can not be serviced at a single location - the object being large or complex for that endeavour. Given the non-bijective nature of manipulator kinematics between task and joint space, without explicit consideration of joint-space continuity during its construction, a continuous coverage path designed in task-space may easily be truncated into intermittent segments where the manipulator needs to adopt a different configuration to continue the task, resulting in manipulator motions where the end-effector will need to lift off the surface, an altogether undesirable characteristic affecting the quality of the final product for smooth operations on objects such as polishing, painting or deburring. In this work, a novel algorithm to optimally partition the task-space whilst considering the various finite locations where the object may be stationed is proposed that ensures joint-space coverage continuity with minimal lift-offs. Results from the algorithm being challenged to achieve coverage of a number of objects, both in simulation and in real tests with an industrial manipulator, prove the effectiveness of the proposed planner when compared with classical coverage strategies faced with the same problem.