| Motion planning for systems with challenging constraints is receiving increasing interest in robotics over the last couple of decades. This work focuses on improving performance of sampling-based algorithms, a dominant family of algorithms proposed in late 1990's, which can deal with high-dimensional, highly-constrained problems. Sampling-based planners have been shown to be effective in quickly searching unexplored parts of a robot's state space. Such desirable properties, however, depend on the availability of an appropriate metric function, which is often difficult to be defined for important robotic systems, such as non-holonomic and underactuated ones.;This work investigates two algorithms addressing the challenges arising from complex systems. The first algorithm proposed is a linear approach. For systems which dynamics and underactuation, the state-space exploration of sampling-based tree planners can be inherently biased towards a specific direction, thus not allowing the efficient search of the state space. The premise of the first approach is that it is possible to use statistical tools to learn quickly the effects of the constraints in the state-space exploration process during a training session. Then during the online operation of the algorithm, this information can be utilized so as to counter the undesirable bias due to the dynamics by appropriately adapting the control propagation step. The resulting method achieves a more balanced exploration of the state-space, resulting in faster solutions to planning challenges. Experiments comparing against and improving upon standard solutions for dynamic systems are provided.;The second proposed method is a nonlinear algorithm, which tries to automatically learn the optimal cost-go-to metric during an offline learning phase. The proposed method utilizes sampling to construct a dense graph that approximates the connectivity properties of the state space. This graph can be employed online to compute approximate distances between states using the nearest neighbor queries and standard search algorithms, such as A*. Unfortunately, this process significantly increases the online cost of a sampling-based planner. The paper proceeds into investigating ways that allow the computationally efficient utilization of the learned metric during the planner's online operation. One idea considered is the mapping of the sampled states into a higher-dimensional Euclidean space through multi-dimensional scaling so as to retain the relative distances represented by the sampled graph. Proof of concept simulations on systems with complicated constraints indicates that the approach has merit and can lead into more effective sampling-based algorithms. |
