  This paper deals with the problem of autonomous navigation of a mobile robot
in an unknown 2D environment to fully explore the environment as efficiently as
possible. We assume a terrestrial mobile robot equipped with a ranging sensor
with a limited range and 360 degrees field of view. The key part of the
exploration process is formulated as the d-Watchman Route Problem which
consists of two coupled tasks - candidate goals generation and finding an
optimal path through a subset of goals - which are solved in each exploration
step. The latter has been defined as a constrained variant of the Generalized
Traveling Salesman Problem and solved using an evolutionary algorithm. An
evolutionary algorithm that uses an indirect representation and the nearest
neighbor based constructive procedure was proposed to solve this problem.
Individuals evolved in this evolutionary algorithm do not directly code the
solutions to the problem. Instead, they represent sequences of instructions to
construct a feasible solution. The problems with efficiently generating
feasible solutions typically arising when applying traditional evolutionary
algorithms to constrained optimization problems are eliminated this way. The
proposed exploration framework was evaluated in a simulated environment on
three maps and the time needed to explore the whole environment was compared to
state-of-the-art exploration methods. Experimental results show that our method
outperforms the compared ones in environments with a low density of obstacles
by up to 12.5%, while it is slightly worse in office-like environments by 4.5%
at maximum. The framework has also been deployed on a real robot to demonstrate
the applicability of the proposed solution with real hardware.
