computational robotics

from tasks to motions

Inspection of 2D Environments

As defects to objects such as pipeline leakage can result in tremendous economical loss, the inspection problem is one of the most important problems in robotics. Given a set of objects located in an environment with obstacles, the task is to find a low-cost obstacle-avoiding path that inspects all objects. Inspection is often expressed in terms of visibility, which may be limited by the sensor range, e.g., laser, camera.

Inspection poses significant challenges since the robot needs to determine and reach a set of locations whose combined visibility covers the inspection area. To reach these locations, the robot often has to avoid numerous obstacles and pass through narrow passages. Planning such motions requires taking into account the robot geometry as well as differential constraints imposed by its dynamics on the velocity, turning radius, and acceleration. This is a challenging task as motion planning with dynamics is undecidable.

This paper develops an efficient approach to generate a collision-free and dynamically-feasible trajectory that enables a robotic vehicle to inspect the entire workspace or a subset consisting of one or several regions. The approach makes it possible to specify constraints on the order in which the regions should be inspected by using colors to ensure that regions with the same color are inspected as a group. A key aspect is the transformation of the multi-region inspection into a clustered traveling salesman problem (CTSP). This is achieved by generating several inspection points on the medial axis of each region to increase the visibility and by grouping the inspection points into clusters. We also develop a fast branch-and-bound CTSP solver to find low-cost clustered tours. These tours guide sampling-based motion planning as it expands a motion tree in search for a collision-free and dynamically-feasible trajectory to carry out the multi-region inspection. The approach is evaluated in simulation using a snake-like robot model to carry out inspection tasks in complex environments. Comparisons to related work show significant speedups.

Inspection of 3D Structures

Unmanned aerial vehicles (UAVs) provide a viable mechanism to automate the inspection of complex 3D environments and structures. This paper develops an approach that enables an aerial vehicle to carry out 3D surface inspections. Given a 3D environment with a set of objects that need to be inspected, and an inspection quality 0 < \alpha < 1, the objective is to compute a set of waypoints whose joint visibility ratio is at least $\alpha$ and a dynamically-feasible and collision-free trajectory that enables the aerial vehicle to reach all the waypoints. The approach seeks to minimize the number of the waypoints and the overall distance traveled by the aerial vehicle.

A superset of the waypoints is first generated by using random sampling or approximations of the medial axis via skeletonization algorithms. To reduce the number of the waypoints, the approach applies a visibility filtering mechanism based on a computation of a hitting set via Monte-Carlo search over an axis-aligned bounding box obstacle tree. After generating the waypoints, a multi-goal motion planning approach is applied to compute a collision-free and dynamically-feasible trajectory that visits all the waypoints while seeking to minimize the distance traveled. Experimental results in simulation with complex 3D models where the aerial vehicle carries out outside and inside inspection tasks demonstrate the effectiveness of the approach.

Related Publications

  • Edelkamp S, Can Secim, B and Plaku E (2017): "Surface Inspection via Hitting Sets and Multi-Goal Motion Planning." Springer LNCS Towards Autonomous Robotic Systems, vol. 10454, pp. 134--149  [publisher]  [preprint]
  • Edelkamp S, Pomarlan M, and Plaku E (2017): "Multi-Region Inspection by Combining Clustered Traveling Salesman Tours with Sampling-Based Motion Planning." IEEE Robotics and Automation Letters, vol. 2, pp. 428--435  [publisher]  [preprint]