REPUBLIC OF SERBIA

MINISTRY OF DEFENCE

www.mod.gov.rs

MINISTRY OF DEFENCE

Material Resources Sector

Defensive Technologies Department

Military Technical Institute

www.vti.mod.gov.rs

AUTONOMOUS MOBILE ROBOT PATH PLANNING
IN complex and DYNAMIC ENVIRONMENTS

NOVAK ZAGRADJANIN

MoD RS, Department for Defence Technologies, Belgrade, e-mail: zagradjaninnovak@gmail.com

STEVICA GRAOVAC

University of Belgrade, School of Electrical Engineering, Belgrade, e-mail: graovac@etf.bg.ac.rs

Abstract: Robots operating in the real world often have limited time available for planning their next actions. Producing optimal plans is infeasible in these scenarios. Instead, robots must be satisfied with the best plans they can generate within the time available. A second challenge associated with planning in the real world is that models are usually imperfect and environments are often dynamic. Thus, robots need to update their models and consequently plans over time. In this paper, we present and compare three grid-based path planners. First we present Anytime Repairing A* (ARA*) algorithm that provides suboptimality bounds on the quality of the solution at any point in time. Than we present an incremental extension of A* algorithm called D* Lite that is used for robot navigation in unknown terrain, including goal-directed robot navigation and mapping of unknown terrain. At the end we present Anytime Dynamic A* (AD*) algorithm that is both anytime and incremental. This extension improves its current solution while deliberation time allows and is able to incrementally repair its solution when changes to the world model occur.

Keywords: path, planning, heuristic, anytime, incremental.