Information Technology Reference
In-Depth Information
The ID is obtained by relating the coordinates of the newly-detected vertex to the
ID list previously computed. The direction is defined in a similar way to the compass
rose designation, as show on the right side of Figure 3,
e.g.
, if the direction of the route
leading to the neighbor vertex starts in the pixel above the examined vertex, than the
direction is defined as North (N). Also, the edge weight between vertices is defined as
the cost of travelling from one vertex to another in pixel units, more specifically, the
number of red pixels in the edge between both vertices.
Every vertex is identified by a single blue pixel, as shown previously in Figure 2.
After obtaining all the data fields, each vertex will have a table of neighbors with the size
of its degree and all the edges and the connectivity between neighbor vertices will be
well characterized. This is clear in Figure 4. Having all this information, the framework
for agents' navigation in the Patrolling Simulator is finally created.
5
Results and Discussion
The algorithm presented in this article was tested using a large diversity of maps that
generated elegant and balanced representations that range from simple topologies to
complex ones. An important aspect is that the complexity of the topological maps ex-
tracted has no relation to the dimension of the environment (in terms of Cartesian dis-
tances). The algorithm attained clear and visually attractive graph representations from
metric maps of all sizes and shape, presenting no vertices with self-loops, staying away
from obstacles and considering the sensing range of the robots; showing that it scales
well in terms of environment, as shown in Figures 5-8. Beyond the accurate results ob-
tained, the algorithm has shown to be computationally efficient. The C++ programming
language was used and the Graphical User Interface (GUI) for the Patrolling Simulator
was implemented using QT Open Source Edition 4.4.3, which is also based on C++
Language
3
. The system ran on Ubuntu 8.10 Intrepid on an AMD Athlon 64 Processor
3500+, 2.21GHz, with 1GB RAM.
Table 2 illustrates the time taken by the algorithm to extract all information from
diverse metric maps, which is dependent not only on the amount of pixels in the free
area of each metric map, as well as the complexity of the generated graph. Around
95% of the time values shown is spent computing the skeleton of the environment (first
step of the Algorithm), which is the responsibility of EVG-THIN. The three other steps
of the approach are computed in a few hundredths of second, which is extremely fast
considering the application for which it was designed for.
The image pixels presented in the table do not relate in the same way, for every
case, to the free pixels detected in each image. It is also clear that the computation time
does not depend exclusively on this. It also depends on the graph's dimension as, for
example, the fourth and fifth line of the table highlights.
These results attest to the applicability of the method proposed herein. It is a valuable
method for obtaining a topological map of the environment from either an
apriori
known metric map or a metric map being built on the fly.
3
The Patrolling simulator code is available at:
