Efficient Real-Time Robot Navigation Using Incremental State Discovery Via Clustering

We consider the problem of robot path planning in an initially unknown environment where the robot does not have access to an a priori map of its environment but is aware of some common obstacle patterns along with the paths that enable it to circumnavigate around these obstacles. In order to autonomously improve its navigation performance, the robot should be able to identify significant obstacle patterns and learn corresponding obstacle avoidance maneuvers as it navigates through different environments in order to solve its tasks. To achieve this objective, we propose a novel online algorithm called Incremental State Discovery Via Clustering (ISDC) which enables a robot to dynamically determine important obstacle patterns in its environments and their best representations as combinations of initially available basic obstacle patterns. Our results show that ISDC, when combined with our previously proposed navigation technique, was able to identify significant obstacle patterns in different environments in a time effective manner which accelerated the overall path planning and navigation times for the robots.