Information Technology Reference
In-Depth Information
Ta b l e 1 .
EVG-THIN parameters [11]
Command
Description
min-unknown [N]
The minimum greyscale value (1-254) of unknown cells. Occu-
pied cells are 0-(N-1).
max-unknown [M]
The maximum greyscale value (1-254) of unknown cells. Free
cells are (M+1)-255.
pruning [
0
|
1
]
Turns pruning on or off. Pruning removes all “branches” of the
skeleton except those that meet one of these conditions: 1) The
branch touches the edge of the grid. 2) The branch touches un-
known cells.
min-distance [R]
Bleeds obstacles by R cells before calculating skeleton. This re-
moves branches that come too close to obstacles.
max-distance [S]
If the skeleton exceeds the S cells from the nearest occupied cells,
it switches to following the occupied cells S away.
robot loc [X Y]
This location is used to select which skeleton is valid, given
complex images with multiple, disjoint skeletons. By default, the
“robot” is located at the centre of the image.
robot-close [
0
|
1
]
The robot location (see above) is used to choose which skeleton
is valid (if multiple exist). This is done by Euclidean distance be-
tween the robot's location at the skeletal points. This option turns
off the checking mechanism except for points where the robot's
distance is within the distance of the skeletal point to its closest
obstacle.
4
The Algorithm
In a previous work [6] a patrolling simulator was used to validate a multi-robot pa-
trolling approach based on balanced graph partitioning. Here, we show how the pre-
assumed graph is provided to the patrolling simulator. The algorithm is comprised of 4
steps which are detailed below.
4.1
Acquiring the Skeleton
A tool named EVG-THIN developed by Patrick Beeson [11] was used to acquire skele-
tons from occupancy grids in this project. “EVG” stands for the Extended Voronoi
Graph, which although being called a graph, does not present output related to informa-
tion about vertices and edges on the graph, giving instead an enhanced skeleton on top of
a grid map, when compared to the GVD. “THIN” accounts for the pixel-based thinning
algorithm that finds skeletons of bitmaps, which is a fast approximation of the Voronoi
diagram. Its code was written to be applied in real-time to occupancy grids, where cells
are either occupied, free, or unknown, but it also works on any grayscale bitmap image
in other domains. This command-line application runs in any Linux console upon the
definition of some parameters, such as the pixels' threshold for considering them free,
unknown or occupied; or the robot's minimum distance to an obstacle to account for the
