  This paper presents a novel reactive motion planning framework for navigating
robots in unknown and cluttered 2D workspace. Typical existing methods are
developed by enforcing the robot staying in free regions represented by the
locally extracted ellipse or polygon. Instead, we navigate the robot in free
space with an alternate starshaped decomposition, which is calculated directly
from real-time sensor data. Additionally, a roadmap is constructed
incrementally to maintain the connectivity information of the starshaped
regions. Compared to the roadmap built upon connected polygons or ellipses in
the conventional approaches, the concave starshaped region is better suited to
capture the natural distribution of sensor data, so that the perception
information can be fully exploited for robot navigation. In this sense,
conservative and myopic behaviors are avoided with the proposed approach, and
intricate obstacle configurations can be suitably accommodated in unknown and
cluttered environments. Then, we design a heuristic exploration algorithm on
the roadmap to determine the frontier points of the starshaped regions, from
which short-term goals are selected to attract the robot towards the goal
configuration. It is noteworthy that, a recovery mechanism is developed on the
roadmap that is triggered once a non-extendable short-term goal is reached.
This mechanism renders it possible to deal with dead-end situations that can be
typically encountered in unknown and cluttered environments. Furthermore, safe
and smooth motion within the starshaped regions is generated by employing the
Dynamical System Modulation (DSM) approach on the constructed roadmap. Through
comprehensive evaluation in both simulations and real-world experiments, the
proposed method outperforms the benchmark methods in terms of success rate and
traveling time.
