Embedded Files
Objective: To find the Watchman Route, when the area of the map is given, by using the optimal positions of the scan locations.
Approach: For a given "realistic" polygon with or without holes, first find the ideal static scan locations by solving the Art Gallery Problem by using the geometry of the polygon. In this case, we check the visibility of the edges of the polygon for each vertex and choose the vertex which has the highest visibility, and keep on recursively repeating this process till all the edges of the polygon are scanned. Here our scanners are considered Omnipotent meaning they have 360 degree vision and no limit on how far they can look. There are also certain constraints where if the scanner can see < 10 degrees of the edge, then it is not considered to be scanned by that particular scanner. Given the positions of these scanners, if the watchman were to visit all these scan locations at least once, by solving travelling salesman problem, then it would mean that the watchman has scanned all the edges of the polygon and thus successfully completed a watchman route.
To summarize the approach: 1) Solve the Art Gallery Problem, 2) Get the Scan Locations, 3) Solve the Travelling Salesman Problem, 4) Get the Watchman Route.
Figure 1 - Conversion of indoor environment into a polygon, and scan locations
Art Gallery Problem - Scan Locations:
Art Gallery Problem is a problem to determine the minimum number of scan locations that are required or are sufficient to cover or see every point in the interior of an indoor environment. An indoor environment can be viewed as a polygon with or without holes with a total of n vertices; and scanners as points in the polygon, or on the vertex of the polygon. or on the edge of the polygon. Any point P in the polygon is said to be visible from a scanner G if the line segment joining P and G does not intersect the exterior of the polygon.
Proposed Algorithm to Solve the Art Gallery Problem:
Create a polygon
Find a vertex(Vi) in the polygon which scans maximum no. of edges of the polygon
Now search for edges that remain unscanned by the previous vertex (Vi)
Find another vertex (Vj) on the polygon which scans maximum of the remaining unscanned edges.
Continue step 3 and 4 until all the edges are scans
Figure 2 - Proposed Algorithm Implementation in Python (Matplotlib)
Art Gallery Problem for Polygons with Holes:
Figure 3 - Proposed Algorithm for Polygon with Holes
Now that we have got the scan locations, lets connect them by solving the travelling salesman problem to finally get the optimal watchman route
Travelling Salesman Problem - Watchman Route (Robot Route)
Watchman Route is considered a Travelling Salesman Problem, which is defined as Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city?". In our case the cities are replaced with scan locations. In normal TSP, you get the path distance between two cities directly by connecting them in a straight line. However, for our case, the points are constrained in the polygon and subsequently subjected to discretization. In order to connect the points, we used A* search algorithm by setting heuristic as eucledian distance between the points. Here we have to consider if a point is inside the polygon or not before exploring those points.
After we get the path lengths for each scanner, we use them as input for the two algorithms we have tried to implement:
Brute Force
Held-Karp Algorithm
Figure 4 - Implementation of Travelling Salesman Problem in Python (Matplotlib)
Figure 5 - Implementation of Travelling Salesman Problem on Polygon with Holes
Even though we say the route is "Optimal", it is optimal only in the constrained discretized grid. If we keep on discretizing the grid even finer, we will get a better result but we can never escape the curse of discretization. Perhaps, one better approach could be to try to directly connect the scan locations in a straight line and when we encounter an obstacle, in this case would be the polygon boundary or holes within the polygon, we can switch to A* or Dijkstra algorithm to find the path. Some mix of Global and Local planner perhaps.
Why to use A* algorithm over other discrete planning algorithms, to connect the scan locations?
The figure 6 below shows why we prefer A* over BFS, DFS, and Dijkstra.
Although for the given grid the path of BFS, Dijkstra, and A* is almost similar, but the number of steps required by A* to find the same path are less as compared to others.
Which sampling based algorithm to use to connect the scan locations?
The comparison between few sampling based algorithms is shown in the figures below, and by looking at the figure 7 it is clear that informed RRT* search performs better than RRT and RRT*.
If we have a look at the PRM methods with different sampling strategies, in the figure 8, then we can be sure that PRM method can not be applied to solve this problem, due to its non-deterministic and inefficient solutions.
Figure 7 - Implementation of RRT and its Variants for solving travelling salesman problem
Figure 8 - Implementation of PRM with three different sampling methods, for solving travelling salesman problem
Figure 9 - Implementation of Sampling Based Algorithms for solving travelling salesman problem for polygons with holes
Conclusions and Future Work:
We were able to make use of the output from one research area and connect it to another research area.
We successfully found the static scan locations and connected them.
Based on the experimentation, we can conclude that placing the scan locations on polygon vertices and Voronoi vertices (for better scan quality) gave the optimal solution for the Art Gallery Problem.
From experimentation, we found that as the number of scan locations increased, Held-Karp algorithm performed better relatively.
We could use the watchman route to divide the region by casting a coverage area for a dynamic guard and work with multi-robot agents.
Page updated
Report abuse