{"id":{"repo_id":"rice","oai_identifier":"oai:repository.rice.edu:1911/76497"},"canonical_url":"https://search.dev.ndltd.org/etd/rice/oai:repository.rice.edu:1911/76497","repository":{"repo_id":"rice","name":"Rice University","base_url":"https://repository.rice.edu/server/oai/request"},"display":{"title":"Informed Planning and Safe Distributed Replanning under Physical Constraints","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.","abstract_html":"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.","abstract_has_math":false,"creators":["Bekris, Konstantinos E."],"institution":"Rice University","degree_name":"Doctor of Philosophy","degree_level":"Doctoral","degree_discipline":"Engineering","degree_department":null,"school":null,"contributors":[],"advisors":["Kavraki, Lydia E."],"committee_chairs":[],"committee_members":["Warren, Joe","Knightly, Edward W."],"year":2009,"date_issued":"2009","date_published":"2009","updated_at":"2026-07-24T04:10:32Z","subjects":["Computer science"],"languages":["eng"],"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."],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"https://hdl.handle.net/1911/76497","outbound_label":"Handle","outbound_source":"dc:identifier.uri"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.advisor","label":"Advisor","values":["Kavraki, Lydia E."]},{"key":"dc:contributor.committeemember","label":"Committee Member","values":["Warren, Joe","Knightly, Edward W."]},{"key":"dc:creator","label":"Author","values":["Bekris, Konstantinos E."]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2014-08-08T22:00:26Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2014-08-08T22:00:26Z"]},{"key":"dc:date.issued","label":"Date","values":["2009"]},{"key":"dc:type","label":"Dc Type","values":["Thesis"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Engineering"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Doctoral"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Doctor of Philosophy"]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["Rice University"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Computer science"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language.iso","label":"Language (ISO)","values":["eng"]},{"key":"dc:rights","label":"Dc Rights","values":["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."]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.uri","label":"Identifier URI","values":["https://hdl.handle.net/1911/76497"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["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."]},{"key":"dc:format.mimetype","label":"Dc Format Mimetype","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Informed Planning and Safe Distributed Replanning under Physical Constraints"]}]}],"canonical_facts":{"dc:contributor.advisor":["Kavraki, Lydia E."],"dc:contributor.committeemember":["Warren, Joe","Knightly, Edward W."],"dc:creator":["Bekris, Konstantinos E."],"dc:date.accessioned":["2014-08-08T22:00:26Z"],"dc:date.available":["2014-08-08T22:00:26Z"],"dc:date.issued":["2009"],"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.mimetype":["application/pdf"],"dc:identifier.uri":["https://hdl.handle.net/1911/76497"],"dc:language.iso":["eng"],"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."],"dc:subject":["Computer science"],"dc:title":["Informed Planning and Safe Distributed Replanning under Physical Constraints"],"dc:type":["Thesis"],"thesis:degree_discipline":["Engineering"],"thesis:degree_level":["Doctoral"],"thesis:degree_name":["Doctor of Philosophy"],"thesis:institution_name":["Rice University"]},"updated_at":"2026-07-24T04:10:32Z"}