FAST FEASIBLE MOTION PLANNING WITHOUT TWO-POINT BOUNDARY VALUE SOLUTION

Abstract

Autonomous robotic systems have seen extensive deployment across domains such as manufacturing, industrial inspection, transportation, and planetary surface exploration. A crucial requirement for these systems is navigating from an initial to a final position, while avoiding potential collisions with obstacles en route. This challenging task of devising collision-free trajectories, formally termed as motion planning, is of prime importance in robotics. Traditional motion planning approaches encounter scalability challenges when planning in higher-dimensional state-spaces. Moreover, they rarely consider robot dynamics during the planning process. To address these limitations, a class of probabilistic planning methods called Sampling-Based Motion Planning (SBMP) has gained prominence. SBMP strategies exploit probabilistic techniques to construct motion planning solutions.

In this dissertation, our focus turns towards feasible SBMP algorithms that prioritize rapidly discovering solutions while considering robot kinematics and dynamics. These algorithms find utility in quickly solving complex problems (e.g., Alpha puzzle) where obtaining any feasible solution is considered as an achievement. Furthermore, they find practical use in computationally constrained systems and in seeding time-consuming optimal solutions.

However, many existing feasible SBMP approaches assume the ability to find precise trajectories that exactly connect two states in a robot's state space. This challenge is framed as the Two-Point Boundary Value Problem (TPBVP). But finding closed-form solutions for the TPBVP is difficult, and numerical approaches are computationally expensive and prone to precision and stability issues. Given these complexities, this dissertation's primary focus resides in the development of SBMP algorithms for different scenarios where solving the TPBVP is challenging.

Our work addresses four distinct scenarios -- two for single-agent systems and two for multi-agent systems. The first single-agent scenario involves quickly finding a feasible path from the start to goal state, using bidirectional search strategies for fast solution discovery. The second scenario focuses on performing prompt motion replanning when a vehicle's dynamical constraints change mid-mission. We leverage the heuristic information from the original search tree constructed using the vehicle's nominal dynamics to speed up the replanning process. Both these two scenarios unfold in static environments with pre-known obstacles. Transitioning to multi-agent systems, we address the feasible multi-robot motion planning problem where a robot team is guided towards predefined targets in a partially-known environment. We employ a dynamic roadmap updated from the current known environment to accelerate agent planning. Lastly, we explore the problem of multi-robot exploration in a completely unknown environment applied to the CADRE mission. We demonstrate how our proposed bidirectional search strategies can facilitate efficient exploration for robots with significant dynamics. The effectiveness of our algorithms is validated through extensive simulation and real-world experiments.