|
Li - Iyengar New Region Guarding Algorithm and its Applicaitons on Autonomous Pipeline Inspection
|
|
Active Pipeline monitoring is an essential task to prevent large scale ecological disasters. However, many pipeline systems are deep underground or underwater making them increasingly difficult to monitor. Even above ground pipelines can be difficult to inspect because of their locations in buildings. Furthermore, pipelines systems are long and complex and may be carrying hazardous materials. For these reasons, autonomous robots are used to monitor pipelines. Although much safer, this method of inspection is costly and labor intensive. It is important to efficiently analyze pipeline networks in to make robotic inspection viable. The LSU Research Team is the first group to propose a new algorithm to design an autonomous robotic inspection routine. Region Guarding Xin Li and S Sitharama Iyengar from Louisiana State University have proposed a solution to this problem by assigning robots to monitor specific three dimensional regions similar to the Museum Guarding Problem applied in three dimensions. In its simplest form, the Museum guarding problem centers on the problem of trying to guard every room in a museum with the fewest number of guards/cameras. In 2D, the Gallery Guarding Problem has been shown to be NP-hard. However, little analysis has been done trying to solve the problem in three dimensions. The LSU research team has proposed a High Integral Linear Programming (HILP) to find the optimal solution to this problem. The Algorithm The algorithm centers around three principles: * First, the system must be the most efficient. The inspection must be the most thorough without using extra resources. * Second, the solution must be autonomous. Robots can inspect the system with the fewest number of guarding positions possible. * Third, the solution must be general and robust. As in, it can apply to all types of piping systems. At Left, Guarding Statues using HILP. Small nodes are the guards, where green nodes are the latest computed guards on the finest level. Applied to pipeline inspection, the algorithm selects guarding locations, or scanning points, where each autonomous robot will scan the pipeline. It then moves to the next guarding position and so on until its cycle of checking positions are complete. This approach solves the problem of autonomous robotic inspection because the robot can scan each guard point when the pipeline is intact. Once the visual inspection reading is complete, the ideal data must be compared to the data stored from the intact pipeline inspection. A greedy algorithm solution would choose the compare data first from the points that capture the most guard points. This could result in a less than optimal final solution as the greedy solution passes over guard points in hard to reach locations, leaving them unchecked. An optimal solution, however, must find the most efficient solution using an Integral Linear Programming, ILP, approach. This is the most efficient method to solving the three dimensional gallery guarding problem. However, computing the optimal guarding based on ILP is highly time-consuming and it limits the size of problems that can be handled. General 3D volumetric shapes can easily have a number of 20 to 200 thousand vertices on its boundary surface, which is too large for this optimization. The algorithm must also reduce the number of vertices that require checking. Hierarchical Optimization The algorithm reduces the total number of vertices to use in the ILP for a solution that is faster and more efficient than the greedy solution while remaining more stable and robust. This method of reducing necessary vertices is also far less susceptible to geometric noise associated with small deformations in the ideal pipeline structure. center 
|
| < Prev | Next > |
|---|
Main Menu
| Home |
| Articles |
| Search |
| Submit Article |
| Contact Us |
| Donate to Wikibin |
