Informed Planning and Safe Distributed Replanning under Physical Constraints

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.

Name thesis:degree_name

Doctor of Philosophy

Level thesis:degree_level

Doctoral

Discipline thesis:degree_discipline

Engineering

Grantor

Rice University

Year dc:date.issued

2009

Author dc:creator

• Bekris, Konstantinos E.

Advisor dc:contributor.advisor

• Kavraki, Lydia E.

Committee members dc:contributor.committeemember

• Warren, Joe
• Knightly, Edward W.

• Computer science

Statement dc:rights

• Copyright is held by the author, unless otherwise indicated. Permission to reuse, publish, or reproduce the work beyond the bounds of fair use or other exemptions to copyright law must be obtained from the copyright holder.

Language dc:language.iso

eng

Handle dc:identifier.uri

https://hdl.handle.net/1911/76497

OAI identifier oai:identifier

oai:repository.rice.edu:1911/76497