Structural Inspection Path Planning
 A. Bircher, K. Alexis, M. Burri, P. Oettershagen, S. Omari, T. Mantel, R. Siegwart, "Structural Inspection Path Planning via Iterative Viewpoint Resampling with Application to Aerial Robotics", IEEE International Conference on Robotics & Automation, May 2630, 2015 (ICRA 2015), Seattle, Washington, USA .
 A. Bircher, M. Kamel, K. Alexis, M. Burri, P. Oettershagen, S. Omari, T. Mantel, R. Siegwart, "Threedimensional Coverage Path Planning via Viewpoint Resampling and Tour Optimization for Aerial Robots", Autonomous Robots, Springer US, DOI: 10.1007/s1051401595171, ISSN: 15737527
 OpenSource Git Repo: https://github.com/ethzasl/StructuralInspectionPlanner
 Experimental Datasets: https://github.com/ethzasl/StructuralInspectionPlanner/wiki/ExampleResults
Among the most wellestablished approaches in the field, those that separate the overall problem into that of finding a minimal set of fullcoverage viewpoints (Art Gallery Problem  AGP) and subsequently compute the optimal route among them (Traveling Salesman Problem  TSP) have been particularly successful. These methods often manage to produce good solutions in short time. However, they have two main limitations and problems, namely:
 They are prone to be suboptimal due to the twostep separation of the problem.
 In specific cases they can lead to unfeasible solutions/paths (e.g. in the case of nonholonomic vehicles)
As a response to the abovementioned limitations, the problem Structural Inspection Planner (SIP), revisits the concept of 2step optimization based inspection path planning. Essentially, SIP is driven by the idea that with a continuously (or very fast) sampling sensor, the number of viewpoints is not necessarily important but mostly their configuration in space. SIP does not search for a minimal set of viewpoints but rather for a set of full coverage viewpoints positioned such that the overall path gets minimized. SIP employs an iterative, viewpoint alternation and route recomputation 2step optimization paradigm. Therefore, it guarantees to find feasible path solutions for both holonomic and nonholonomic vehicles and typically arrives at fullcoverage solutions that are of lowcost.

Figure 1: Indicative SIP solution

Viewpoint Optimization Process
To perform the viewpoint optimization process, SIP relies on a mechanism based on a convex optimization methods. More specifically, admissible viewpoints are optimized for distance to the neighboring viewpoints. To guarantee that all viewpoints are admissible, the position solution g = [x,y,z] is constrained to allow finding an orientation for which the triangular face is visible: To account for the limited camera Field of View (FoV), it imposes a revoluted 2Dcone constraint. This is a nonconvex problem which is then convexified by dividing the problem into Nc equal convex pieces.
The concept is visualized in Figure 2.

Figure 2: Viewpoint optimization process for finding admissible viewpoints that satisfy the sensing limitations of the robot. On the left the incidence angle constraints on a triangular surface are shown. On the right the camera constraints and the revoluted 2Dcone convexification is shown.

Minimize the sum of squared distances to the preceding viewpoint gp^{k1}, the subsequent viewpoint gs^{k1} and the current viewpoint in the old tour g^{k1}. More formally:
In its current implementation, SIP relies on Statespace sampling methods, while an extension to controlspace sampling methods is possible. To find path solutions from one viewpoint to the other, it employs a Boundary Value Solver (BVS) for holonomic or nonholonomic vehicle configurations and relies on the optimal Rapidlyexploring Random Tree (RRT*) algorithm to derive collisionfree paths.
SIP Tour Optimization
To solve for the periteration SIP tour optimization and derive the corresponding TSP solution, the method relies on the LKH solver. LKH is an effective implementation of the LinKernighan heuristic for solving the Traveling Salesman Problem. The LinKernighan solver (also called the LinKernighanHelsgaun solver) is among the most efficient solvers of the TSP and it is employing the concept of kopt moves. The concept of kmoves is visualized in Figure 3. 
Figure 3: Visualization of the kmoves process.

The following video presents an execution of the SIP algorithm and enables intuitive understanding of its operation. The first part of the video simply presents the mesh visualization process.
Experimental Studies
The algorithm is actively used within the framework of inspection operations using both rotorcrafttype as well as fixedwing aerial robots. More specifically, the Firefly MAV platform and the AtlantikSolar UAV were used  both equipped with the VISensor. The platforms are shown in Figure 4. The following experimental datasets are available: Using FixedWing UAV:

Figure 4: Robot platforms used for the SIP experimental studies. Both fixedwing and rotorcraft unmanned aerial vehicles were employed for evaluation purposes.



To learn more about the SIP algorithm essentials, you may go through the papers and study the code at our opensource repository: https://github.com/ethzasl/StructuralInspectionPlanner/
As this corresponds to an open research topic, interested students may contact Dr. Kostas Alexis to discuss potential projects.
Installation Instructions
StructuralInspectionPlanner
Beta version
The structural inspection path planning algorithm presented in our paper contribution [1] is released as an opensource toolbox. The algorithm assumes a triangular mesh representation of the structure and employs an alternating twostep optimization paradigm to find good viewpoints that together provide full coverage and a connecting path that has low cost. In every iteration, the viewpoints are chosen such that the connection cost is reduced and, subsequently, the tour is optimized. Vehicle and sensor limitations are respected within both steps. Sample implementations are provided for rotorcraft and fixedwing unmanned aerial robots.
Additional functionality allows exportation of the computed paths to drone mission files. Supported systems are PX4/Pixhawk and DJI drones, as well as the RotorS simulator and will be extended in the future. (Refer to the utils section)
Installing the toolbox
To use the toolbox a ROS indigo installation with catkin setup and the following extra packages are required:
libeigen3dev
rosindigotf
rosindigorviz
rosindigooctomap
rosindigooctomapmsgs
Once these are there, a baseline example on how to get and install the tool is the following:
$ mkdir catkin_ws_repos # assuming you want to enter a new catkin directory
$ cd catkin_ws_repos # alternatively just cd your normal catkin workspace
$ mkdir src # assuming this folder does not exist
$ cd src/
$ catkin_init_workspace
$ git clone git@github.com:ethzasl/StructuralInspectionPlanner.git
$ cd ..
$ catkin_make
$ source devel/setup.bash
The build process should then be executed and successfully complete. Subsequently open two separate shells and run the following two commands to execute the baseline demo of the algorithm:
Shell #1
roslaunch koptplanner kopt.launch
Shell #2
rosrun request request
For visualization puprposes, a 3rd terminal has to be launched:
Shell #3
rosrun rviz rviz
Add the necessary displays:
‘Path’ on topic ‘visualization_marker’
‘Marker’ on topic ‘viewpoint_marker’
‘Path’ on topic ‘stl_mesh’
‘Marker’ on topic ‘scenario’
To display the progress, chose ‘/kopt_frame’ as fixed frame or publish a suitable transform.
Detailed Documentation
Detailed documentation may be found at the Wiki!
References:
 A. Bircher, K. Alexis, M. Burri, P. Oettershagen, S. Omari, T. Mantel and R. Siegwart, “Structural inspection path planning via iterative viewpoint resampling with application to aerial robotics,” in Robotics and Automation (ICRA), 2015 IEEE International Conference on, May 2015, pp. 6423–6430.
 K. Helsguan, “An effective implementation of the linkernighan traveling salesman heuristic”, European Journal of Operational Research, vol. 126, no. 1, pp. 106130, 2000.
 H.J. Ferreau and A. Potschka and C. Kirches, “qpOASES”
 S. Karaman and E. Frazzoli, “Samplingbased algorithms for optimal motion planning”, International Journal of Robotics Research”, vol. 30, no. 7, pp. 846894, 2011
If you use this software in a scientific publication, please cite the following paper:
@INPROCEEDINGS{BABOOMS_ICRA_15,
author = "{A. Bircher, K. Alexis, M. Burri, P. Oettershagen, S. Omari, T. Mantel and R. Siegwart}",
booktitle = {Robotics and Automation (ICRA), 2015 IEEE International Conference on},
title={Structural Inspection Path Planning via Iterative Viewpoint Resampling with Application to Aerial Robotics},
year={2015},
month={May},
pages={64236430},
}
Credits:
This algorithm was developed by Andreas Bircher with the help and support of the members of the Autonomous Systems Lab. The work was supported by the European Commissionfunded projects AEROWORKS and ICARUS.
Contact:
You can contact us for any question or remark:
* Andreas Bircher
* Kostas Alexis