Keywords
cycle detection
frontier exploration
RRT*
D* Lite
reinforcement learning
dynamic obstacles
urban navigation
How to Cite
Abstract
In a modern topology many robots already use the existed map structures, but developing an autonomous system in a previously unknown environment with minimal data and a limited field of view has not yet been definitively explored. Many features of the cities or some area create a closed route, which robots may not leave without human intervention. This paper compares the proposed hybrid graph-construction system with existing algorithms, RRT* and D*Lite, for navigation in an unknown environment; deterministic paths are used in open terrain for obstacle avoidance.
The developed algorithm will create a topographic graph that creates nodes for the future graph, which will then create loops. Once the loop detected the algorithm will use these nodes to exit the loop for further exploration of the terrain.
The goal of this paper is to analyze how the graph construction algorithm performs in a dynamic environment, compared to RRT* and D*Lite, where objects are static and dynamic. To achieve the goal, the following objectives will be performed: constructing a 2D map with random objects and destinations, training neural agents to detect possible nodes and exit them, and constructing an optimal path from point to point using minimal computation in a sufficiently open area.
The three methods were simultaneously simulated in 40 different situations with different initial parameters. The hybrid path construction method achieved the goal in half of all tests, where on average they approached the goal by 27.7%. The highest result was shown by RRT* at 37.3%, only it took an average of 1409 nodes to achieve the goal, which is twice as much as the proposed method in the work. D*Lite completed the training with a score of 3% of the distance traveled, as closed loops were created with complex calculations and heavy traffic.