Papers

@phdthesis{Littlefield:2020aa,
title = {Efficient and Asymptotically Optimal Kinodynamic Motion Planning},
author = {Z Littlefield},
url = {http://www.cs.rutgers.edu/~kb572/pubs/LittlefieldThesisMay2020.pdf},
year = {2020},
date = {2020-05-01},
volume = {PhD},
school = {Rutgers, the State University of New Jersey},
abstract = {This dissertation explores properties of motion planners that build tree data structures in a robottextquoterights state space. Sampling-based tree planners are especially useful for planning for systems with significant dynamics, due to the inherent forward search that is per- formed. This is in contrast to roadmap planners that require a steering local planner in order to make a graph containing multiple possible paths. This dissertation explores a family of motion planners for systems with significant dynamics, where a steering local planner may be computationally expensive or may not exist. These planners focus on providing practical path quality guarantees without prohibitive computational costs. These planners can be considered successors of each other, in that each sub- sequent algorithm addresses some drawback of its predecessor. The first algorithm, Sparse-RRT, addresses a drawback of the RRT method by considering path quality during the tree construction process. Sparse-RRT is proven to be probabilistically complete under mild conditions for the first time here, albeit with a poor convergence rate. The second algorithm presented, SST, provides probabilistic completeness and asymptotic near-optimality properties that are provable, but at the cost of additional algorithmic overhead. SST is shown to improve the convergence rate compared to Sparse-RRT. The third algorithm, DIRT, incorporates learned lessons from these two algorithms and their shortcomings, incorporates task space heuristics to further improve runtime performance, and simplifies the parameters to more user-friendly ones. DIRT is also shown to be probabilistically complete and asymptotically near-optimal. Application areas explored using this family of algorithms include evaluation of distance functions for planning in belief space, manipulation in cluttered environments, and locomotion planning for an icosahedral tensegrity-based rover prototype that requires a physics engine to simulate its motions.},
keywords = {Dynamics, Planning, Soft-Robots},
pubstate = {published},
tppubtype = {phdthesis}
}

@phdthesis{Bekris:2009aa,
title = {Informed Planning and Safe Distributed Replanning under Physical Constraints},
author = {K Bekris},
url = {http://www.cs.rutgers.edu/~kb572/pubs/bekris_thesis.pdf},
year = {2009},
date = {2009-01-01},
volume = {PhD Thesis.},
pages = {148},
address = {Houston, TX},
school = {Rice University (Ph.D Thesis)},
abstract = {Motion planning is a fundamental algorithmic problem that attracts attention because of its importance in many exciting applications, such as controlling robots or virtual agents in simulations and computer games. While there has been great progress over the last decades in solving high-dimensional geometric problems there are still many challenges that limit the capabilities of existing solutions. In particular, it is important to effectively model and plan for systems with complex dynamics and significant drift (kinodynamic planning). An additional requirement is that realistic systems and agents must safely operate in a real-time fashion (replanning), with partial knowledge of their surroundings (partial observability) and despite the presence or in collaboration with other moving agents (distributed planning). This thesis describes techniques that address challenges related to real-time motion planning while focusing on systems with non-trivial dynamics. The first contribution is a new kinodynamic planner, termed Informed Subdivision Tree (IST), that incorporates heuristics to solve motion planning queries more effectively while achieving the theoretical guarantee of probabilistic completeness. The thesis proposes also a general methodology to construct heuristics for kinodynamic planning based on configuration space knowledge through a roadmap-based approach. Then this thesis investigates replanning problems, where a planner is called periodically given a predefined amount of time. In this scenario, safety concerns arise by the presence of both dynamic motion constraints and time limitations. The thesis proposes the framework of Short-Term Safety Replanning (STSR), which achieves safety guarantees in this context while minimizing computational overhead. The final contribution corresponds to an extension of the STSR framework in distributed planning, where multiple agents communicate to safely avoid collisions despite their dynamic constraints. The proposed algorithms are tested on simulated systems with interesting dynamics, including physically simulated systems. Such experiments correspond to the state-of-the-art in terms of system modeling for motion planning. The experiments show that the proposed techniques outperform existing alternatives, where available, and emphasize their computational advantages.},
keywords = {Dynamics, Planning},
pubstate = {published},
tppubtype = {phdthesis}
}