Show simple item record

dc.contributor.advisor Kavraki, Lydia E.
dc.creatorBekris, Konstantinos E.
dc.date.accessioned 2014-08-08T22:00:26Z
dc.date.available 2014-08-08T22:00:26Z
dc.date.issued 2009
dc.identifier.citation Bekris, Konstantinos E.. "Informed Planning and Safe Distributed Replanning under Physical Constraints." (2009) Diss., Rice University. https://hdl.handle.net/1911/76497.
dc.identifier.urihttps://hdl.handle.net/1911/76497
dc.description.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 ef­fectively while achieving the theoretical guarantee of probabilistic completeness. The thesis proposes also a general methodology to construct heuristics for kinody­namic 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 lim­itations. The thesis proposes the framework of Short-Term Safety Replanning (STSR), which achieves safety guarantees in this context while minimizing com­putational 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.
dc.format.extent 149 pp
dc.format.mimetype application/pdf
dc.language.iso eng
dc.subjectComputer science
dc.title Informed Planning and Safe Distributed Replanning under Physical Constraints
dc.identifier.digital BekrisK
dc.contributor.committeeMember Warren, Joe
dc.contributor.committeeMember Knightly, Edward W.
dc.type.genre Thesis
dc.type.material Text
thesis.degree.department Computer Science
thesis.degree.discipline Engineering
thesis.degree.grantor Rice University
thesis.degree.level Doctoral
thesis.degree.name Doctor of Philosophy


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record