NRR: a nonholonomic random replanner for navigation of car-like robots in unknown environments

• Published in: Robotica 2014-10, Vol.32 (7), p.1101-1123
• Main Authors: Masehian, Ellips, Kakahaji, Hossein
• Format: Article
• Language: English
• Subjects: Algorithms; Approximation; Motion planning; Navigation; Robots; Running; Sensors; Strategy
• ISSN: 0263-5747; 1469-8668
• DOI: 10.1017/S0263574713001276

In this paper, a new sensor-based approach called nonholonomic random replanner (NRR) is presented for motion planning of car-like mobile robots. The robot is incrementally directed toward its destination using a nonholonomic rapidly exploring random tree (RRT) algorithm. At each iteration, the robot's perceived map of the environment is updated using sensor readings and is used for local motion planning. If the goal was not visible to the robot, an approximate path toward the goal is calculated and the robot traces it to an extent within its sensor range. The robot updates its motion to goal through replanning. This procedure is repeated until the goal lies within the scope of the robot, after which it finds a more precise path by sampling in a tighter Goal Region for the nonholonomic RRT. Three main replanning strategies are proposed to decide when to perform a visibility scan and when to replan a new path. Those are named Basic, Deliberative and Greedy strategies, which yield different paths. The NRR was also modified for motion planning of Dubin's car-like robots. The proposed algorithm is probabilistically complete and its effectiveness and efficiency were tested by running several simulations and the resulting runtimes and path lengths were compared to the basic RRT method.