Shortest Sightseeing Tour
Mobile obot platform Dingo-O
Initial situation
The Institute for Mobile and Distributed Systems is developing robots based on the Dingo‑O platform in a research project to support care staff in nursing homes. The robots are intended to detect, search for, and accompany people. Their software consists of intercommunicating nodes in the Robot Operating System (ROS). Since testing on real hardware and in the target environment is time-consuming, development and testing are mostly carried out in simulated environments.
Problem statement / Project goal
The aim of this work is to develop an efficient algorithm that enables a robot to find a specific person in a large and cluttered room. Multiple people may be present, and obstacles can limit visibility, so not all individuals can be seen or identified from a single position.
Research Questions
What alternatives to VisLib exist on the market, and how do they compare in performance to VisLib?
Three alternatives to VisLib were tested: TriVis, CGAL, and VisiLibity1. The libraries were evaluated using an extensive framework provided by TriVis to assess their performance. Computation time, runtime behavior, and results were measured and analyzed.
How can the correctness of VisLib be ensured?
Methods to make VisLib more robust were investigated, with a focus on numerical stability. Two approaches were explored: implementing new, more robust geometric predicates, and replacing the previously used real floating-point numbers with rational numbers to avoid rounding errors.
How can an algorithm be implemented to find the shortest tour through a room so that all points are visible?
A new algorithm was developed that generates a spiral-shaped tour, allowing a polygonal space to be completely surveyed.
Results
The performance comparison of the four libraries showed that VisLib outperformed all other libraries except TriVis in computation time. However, VisLib could not match the others in calculation accuracy. To improve accuracy and make VisLib numerically more robust, standard floating-point numbers were replaced with arbitrary-precision rational numbers using the Boost.Multiprecision library. A subsequent performance comparison showed that while accuracy improved significantly, VisLib's computation time increased substantially.
Compared to the already existing algorithm, the newly developed algorithm, which generates a spiral tour to fully survey a polygonal room, generally finds a shorter tour through a polygon. However, it takes longer to compute the tour, and in some cases, especially with increasing viewing distance, it may even find a longer tour than the existing algorithm.
Key terms
- keyword 3Visibility problems
- keyword 2Algorithms
- keyword 1Robotics
Student
Louis Devillers
Advisor
Christoph Stamm