Fast Exploration Using Multirotors: Analysis, Planning, and Experimentation

FSR · 2021

How to enable fast exploration of 3D spaces using a multirotor vehicle?

Kshitij Goel Micah Corah Curtis Boirum Nathan Michael

Figures

**Method Teaser** A multirotor explores a complex unstructured three-dimensional environment (occupied voxels in black) using the proposed planning approach.

**Ideal Exploration Scenario** An ideal multirotor exploration scenario with no obstacles in the environment. The objective is to design a planner that takes actions such that over time, all of the unknown space (black voxels) is explored (white voxels) using a time-of-flight sensor while ensuring that the robot motion and planned trajectories are always within the free space (white voxels).

**Scenarios for Analysis** Ideal exploration scenarios considered for exploration performance analysis. Upper bounds on rate of novel voxels explored are computed for a double integrator system moving towards the sensor scan and parallel to it while performing rapid yaw motion. Environment is assumed completely free while the sensor scan is delayed.

**Velocity Bounds Analysis** Maximum achievable velocity moving toward a frontier based on cited parameters and varying (a) sensor range and (b) total latency (which consists of latency for the mapping system and time for planning). The circle marks the maximum velocity at which the robot can move toward unknown space for the parameters used in this paper, which is less than half the overall velocity bound. Approaching this velocity limit requires either sensor range exceeding 10 m, both higher planning rates and low mapping latency, or some combination of the two.

**Action Space** Available actions at the multirotor state. A set of forward arc motion primitives (gray) are sampled using user-specified action design parameters and discretized velocity bounds. The set of such primitives at each state is termed a motion primitive library (MPL). Dynamically feasible stopping trajectories are also available for each primitive (green, dashed) for safety.

**MCTS Overview** Brief overview of the general Monte Carlo tree search (MCTS) algorithm. Planner selects the deepest node that has unexpanded children based on the selection policy, which is usually based on Upper Confidence Bounds (UCB). From this selected node, children are expanded according to a random rollout policy until a terminal state or condition is reached. The cumulative reward and node visit statistics during this rollout are stored and back-propagated along the path to the root state. This process is iterated until a user-specified computational budget is reached, and the sequence of actions with the best rewards to visits ratio is returned.

**Safe Node Expansion** Overview of safe node expansion in the proposed MCTS-planner and the scheduling of stopping trajectories. Safety checks ensure that all trajectory segments (a), (b), and (c) lie in free space. Segment (a) is scheduled at the root node, while segments (b) and (c) are scheduled at the end of the current planning round. One of the segments (b) or (c) is selected for tracking based on the output of the next planning round. This approach to scheduling and safety checking ensures that the vehicle is always able to stop within free space, even if there is a failure in finding a feasible action during one of the planning rounds.

**Exploration Progression** Different stages of exploration with respect to time for the three-dimensional unstructured environment considered for evaluation of the proposed motion planning framework. Black voxels denote space marked as occupied. We consider a large room in a 3D warehouse environment with dimensions 60 m x 30 m x 11 m.

**Effect of Action Design** Rate of exploration variations with time to investigate effects of changes in action design on exploration performance. We observe substantial improvement in performance due to availability of parallel motions (a, c), while performance increment due to high speed perpendicular actions is observed to be minimal (b, d).

**Effect of Planning Rate** Results for effects of planning rate on exploration performance in a three-dimensional scenario. Two metrics, entropy reduction rate (a) and entropy reduction (b), are shown with respect to time. We observe a peculiar behavior: entropy reduction rate maximizes for 1 Hz planning rate, performing better than 2 Hz and 5 Hz. Furthermore, a substantial part of the environment is left unexplored at 0.5 Hz (b).

**Effect of Horizon Length** Variation in length of the finite-horizon and its effects on exploration performance in a two-dimensional scenario. Two metrics, entropy reduction rate (a) and entropy reduction (b), are shown with respect to time. As expected, longer finite horizon results in significantly better exploration rate (here we compare a 2 second with a 4 second horizon).

BibTeX

@inproceedings{fast-exploration-multirotors-2021,
  title={Fast Exploration Using Multirotors: Analysis, Planning, and Experimentation},
  author={Kshitij Goel, Micah Corah, Curtis Boirum, and Nathan Michael},
  booktitle={Field and Service Robotics (FSR), 2021},
  year={2021}
}