Sample Based Motion Planning with TFC

The motion planning problem consists of finding a sequence of inputs for a system that drives it to a goal region from an initial state while avoiding collisions with obstacles. A popular class of motion planning algorithms are sample-based motion planners (SBMPs). SBMPs do not require an explicit construction of configuration space (C-space) and instead explore pathways with randomized sampling where safety is verified by a collision-detection routine. This randomized approach has its advantages in terms of providing fast solutions for difficult problems. The main drawback is that SBMPs ensure a weaker notion of completeness. SBMPs are instead probabilistically complete, which means that the probability of finding a feasible solution, if one exists, approaches one as the number of samples increases. Although SBMPs are merely probabilistically complete, they have been used to solve real-word motion planning problems in real-time, like self-driving cars.

One well known SBMP is the Rapidly-Exploring Random Tree (RRT) algorithm, along with its successor RRT*. The RRT and RRT* algorithm is a single-query planner where a tree is incrementally grown from the initial state to the goal region, or vice versa. The tree is grown by randomly selecting a state in the C-space. If it lies in the safe region, a connection is attempted to the nearest vertex in the tree. The critical distinction between RRT and RRT* is that the RRT* solution is asymptotically optimal while RRT's solution is not. RRT* operates analogously to RRT, except for its NearNeighbors and Rewire procedures. These two procedures working in tandem are what give RRT* its asymptotic optimality property. In each iteration of the RRT* algorithm, the connections between vertices "near" the sampled node are "rewired" towards the sampled node if some "cost" metric is reduced. Due to RRT*'s asymptotic optimality property stemming from its Rewire procedure it has seen extensive development and use in the optimal motion planning community.

One of the main drawbacks of the RRT* algorithm when used to solve an optimal kinodynamic motion planning problem, i.e., those with differential constraints, is the complexity of the optimal control problem that must be solved repeatedly to form connections in the tree. In our work we explore the advantages and drawbacks of using a physics informed neural network (PINN) framework based on the Theory of Functional Connections (TFC). Below are two videos that show the tree and solutions generated by two variants of the RRT* algorithm for solving a path-constrained energy-optimal rendezvous problem in relative motion. The two types of algorithms tested are essentially RRT* with PINN steering (PINN-RRT*) and linear quadratic regulator steering (LQR-RRT*). LQR-RRT* has been well studied by the robotics and aerospace community, and as such, provides a good comparison to PINN-RRT*. As the videos show PINN-RRT* is capable of providing a rendezvous solution and requires less path smoothing than the solution obtained by LQR-RRT*. Publication with more details and results coming soon.