{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/81808"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/81808","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Geodesic Problems for Mobile Robots","abstract":"We consider the differential drive because it is ubiquitous in mobile robotics. To obtain a well-defined notion of shortest, the total amount of wheel rotation is optimized. We analytically characterize minimum wheel-rotation trajectories in the absence of obstacles, and identify 52 different minimum wheel-rotation trajectories. In the presence of obstacles, every minimum wheel-rotation trajectory is composed of two kinds of subtrajectories: on the boundary of obstacles and in the interior of collision-free space. We prove those subtrajectories that lie in the interior of collision-free space are tangent to the obstacles at both ends. The bitangency condition yields a nonholonomic bitangency graph which is a network of collision-free trajectories in which the solution is sought. In general, our nonholonomic bitangency graph is a 2-dimensional subset of the 3-dimensional configuration space of the robot. Therefore, further optimization or a continuous search may be required to answer queries. However if obstacles are circular and far enough from one another, the graph is a 1-dimensional subset of the configuration space and any graph search algorithm, such as Dijkstra's algorithm, extracts the solution. In the second problem, we introduce a new kinematic airplane model. Our airplane is a natural extention of the Dubins car, and extends it with an additional configuration variable for the altitude. We use the Pontryagin Maximum Principle to analytically characterize geodesics for it. To obtain a notion of shortest, time is optimized. Finally, we present an algorithm for computing optimal coordination of two polygonal robots without differential constraints. Each robot has a reference point that must lie on a network of paths called a roadmap. Each robot wants to move from its given initial location to its goal location without colliding with the other one. Rather than impose an a priori cost scalarization for choosing the best combined motion, we consider finding motions whose cost vectors are Pareto-optimal. Pareto-optimal coordination strategies are the ones for which there exists no strategy that would be better for both robots. The problem is equivalent to computing geodesics in the coordination space which is the Cartesian product of the roadmap with itself. We extend visibility graphs to solve the problem. If the roadmap is acyclic, then our algorithm has O(mn2 log n) time complexity, in which m is the number of paths in the roadmap, and n is the number of coordination space vertices. For cyclic roadmaps, our algorithm computes solutions in time O(25alpham1+5alpha n2 log(m2alpha n)), in which alpha = 1 + [(5ℓ + r)/ b] where ℓ is total length of the roadmap, r is total length of coordination space obstacle boundary, and b is the length of the shortest edge in the roadmap.","abstract_html":"We consider the differential drive because it is ubiquitous in mobile robotics. To obtain a well-defined notion of shortest, the total amount of wheel rotation is optimized. We analytically characterize minimum wheel-rotation trajectories in the absence of obstacles, and identify 52 different minimum wheel-rotation trajectories. In the presence of obstacles, every minimum wheel-rotation trajectory is composed of two kinds of subtrajectories: on the boundary of obstacles and in the interior of collision-free space. We prove those subtrajectories that lie in the interior of collision-free space are tangent to the obstacles at both ends. The bitangency condition yields a nonholonomic bitangency graph which is a network of collision-free trajectories in which the solution is sought. In general, our nonholonomic bitangency graph is a 2-dimensional subset of the 3-dimensional configuration space of the robot. Therefore, further optimization or a continuous search may be required to answer queries. However if obstacles are circular and far enough from one another, the graph is a 1-dimensional subset of the configuration space and any graph search algorithm, such as Dijkstra's algorithm, extracts the solution. In the second problem, we introduce a new kinematic airplane model. Our airplane is a natural extention of the Dubins car, and extends it with an additional configuration variable for the altitude. We use the Pontryagin Maximum Principle to analytically characterize geodesics for it. To obtain a notion of shortest, time is optimized. Finally, we present an algorithm for computing optimal coordination of two polygonal robots without differential constraints. Each robot has a reference point that must lie on a network of paths called a roadmap. Each robot wants to move from its given initial location to its goal location without colliding with the other one. Rather than impose an a priori cost scalarization for choosing the best combined motion, we consider finding motions whose cost vectors are Pareto-optimal. Pareto-optimal coordination strategies are the ones for which there exists no strategy that would be better for both robots. The problem is equivalent to computing geodesics in the coordination space which is the Cartesian product of the roadmap with itself. We extend visibility graphs to solve the problem. If the roadmap is acyclic, then our algorithm has O(mn2 log n) time complexity, in which m is the number of paths in the roadmap, and n is the number of coordination space vertices. For cyclic roadmaps, our algorithm computes solutions in time O(25alpham1+5alpha n2 log(m2alpha n)), in which alpha = 1 + [(5ℓ + r)/ b] where ℓ is total length of the roadmap, r is total length of coordination space obstacle boundary, and b is the length of the shortest edge in the roadmap.","abstract_has_math":false,"creators":["Chitsaz, Hamid Reza"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":["LaValle, Steven M."],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2015,"date_issued":"2015-09-25T20:20:32Z","date_published":"2015-09-25T20:20:32Z","updated_at":"2026-07-22T22:26:17Z","subjects":["Engineering, Robotics"],"languages":["eng"],"rights":[],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["(MiAaPQ)AAI3314745"],"render_values":[{"text":"(MiAaPQ)AAI3314745","href":null,"code":true}]}]},"links":{"outbound_url":"http://hdl.handle.net/2142/81808","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["LaValle, Steven M."]},{"key":"dc:creator","label":"Author","values":["Chitsaz, Hamid Reza"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2015-09-25T20:20:32Z","10000-01-01","2008"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph.D."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Engineering, Robotics"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["eng"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/81808","(MiAaPQ)AAI3314745"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["We consider the differential drive because it is ubiquitous in mobile robotics. To obtain a well-defined notion of shortest, the total amount of wheel rotation is optimized. We analytically characterize minimum wheel-rotation trajectories in the absence of obstacles, and identify 52 different minimum wheel-rotation trajectories. In the presence of obstacles, every minimum wheel-rotation trajectory is composed of two kinds of subtrajectories: on the boundary of obstacles and in the interior of collision-free space. We prove those subtrajectories that lie in the interior of collision-free space are tangent to the obstacles at both ends. The bitangency condition yields a nonholonomic bitangency graph which is a network of collision-free trajectories in which the solution is sought. In general, our nonholonomic bitangency graph is a 2-dimensional subset of the 3-dimensional configuration space of the robot. Therefore, further optimization or a continuous search may be required to answer queries. However if obstacles are circular and far enough from one another, the graph is a 1-dimensional subset of the configuration space and any graph search algorithm, such as Dijkstra's algorithm, extracts the solution. In the second problem, we introduce a new kinematic airplane model. Our airplane is a natural extention of the Dubins car, and extends it with an additional configuration variable for the altitude. We use the Pontryagin Maximum Principle to analytically characterize geodesics for it. To obtain a notion of shortest, time is optimized. Finally, we present an algorithm for computing optimal coordination of two polygonal robots without differential constraints. Each robot has a reference point that must lie on a network of paths called a roadmap. Each robot wants to move from its given initial location to its goal location without colliding with the other one. Rather than impose an a priori cost scalarization for choosing the best combined motion, we consider finding motions whose cost vectors are Pareto-optimal. Pareto-optimal coordination strategies are the ones for which there exists no strategy that would be better for both robots. The problem is equivalent to computing geodesics in the coordination space which is the Cartesian product of the roadmap with itself. We extend visibility graphs to solve the problem. If the roadmap is acyclic, then our algorithm has O(mn2 log n) time complexity, in which m is the number of paths in the roadmap, and n is the number of coordination space vertices. For cyclic roadmaps, our algorithm computes solutions in time O(25alpham1+5alpha n2 log(m2alpha n)), in which alpha = 1 + [(5ℓ + r)/ b] where ℓ is total length of the roadmap, r is total length of coordination space obstacle boundary, and b is the length of the shortest edge in the roadmap.","Made available in DSpace on 2015-09-25T20:20:32Z (GMT). No. of bitstreams: 2 license.txt: 4848 bytes, checksum: 96035ab3f5e1c23cc7138a224ce498bd (MD5) 3314745.pdf: 2341010 bytes, checksum: 599acc1c893f932331404a89bb317b72 (MD5) Previous issue date: 2008","Embargo set by: Seth Robbins for item 83089 Lift date: Forever Reason: Restricted to the U of I community idenfinitely during batch ingest of legacy ETDs","Restricted to the U of I community idenfinitely during batch ingest of legacy ETDs","U of I Only","137 p.","Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 2008."]},{"key":"dc:title","label":"Title","values":["Geodesic Problems for Mobile Robots"]}]}],"canonical_facts":{"dc:contributor":["LaValle, Steven M."],"dc:creator":["Chitsaz, Hamid Reza"],"dc:date":["2015-09-25T20:20:32Z","10000-01-01","2008"],"dc:description":["We consider the differential drive because it is ubiquitous in mobile robotics. To obtain a well-defined notion of shortest, the total amount of wheel rotation is optimized. We analytically characterize minimum wheel-rotation trajectories in the absence of obstacles, and identify 52 different minimum wheel-rotation trajectories. In the presence of obstacles, every minimum wheel-rotation trajectory is composed of two kinds of subtrajectories: on the boundary of obstacles and in the interior of collision-free space. We prove those subtrajectories that lie in the interior of collision-free space are tangent to the obstacles at both ends. The bitangency condition yields a nonholonomic bitangency graph which is a network of collision-free trajectories in which the solution is sought. In general, our nonholonomic bitangency graph is a 2-dimensional subset of the 3-dimensional configuration space of the robot. Therefore, further optimization or a continuous search may be required to answer queries. However if obstacles are circular and far enough from one another, the graph is a 1-dimensional subset of the configuration space and any graph search algorithm, such as Dijkstra's algorithm, extracts the solution. In the second problem, we introduce a new kinematic airplane model. Our airplane is a natural extention of the Dubins car, and extends it with an additional configuration variable for the altitude. We use the Pontryagin Maximum Principle to analytically characterize geodesics for it. To obtain a notion of shortest, time is optimized. Finally, we present an algorithm for computing optimal coordination of two polygonal robots without differential constraints. Each robot has a reference point that must lie on a network of paths called a roadmap. Each robot wants to move from its given initial location to its goal location without colliding with the other one. Rather than impose an a priori cost scalarization for choosing the best combined motion, we consider finding motions whose cost vectors are Pareto-optimal. Pareto-optimal coordination strategies are the ones for which there exists no strategy that would be better for both robots. The problem is equivalent to computing geodesics in the coordination space which is the Cartesian product of the roadmap with itself. We extend visibility graphs to solve the problem. If the roadmap is acyclic, then our algorithm has O(mn2 log n) time complexity, in which m is the number of paths in the roadmap, and n is the number of coordination space vertices. For cyclic roadmaps, our algorithm computes solutions in time O(25alpham1+5alpha n2 log(m2alpha n)), in which alpha = 1 + [(5ℓ + r)/ b] where ℓ is total length of the roadmap, r is total length of coordination space obstacle boundary, and b is the length of the shortest edge in the roadmap.","Made available in DSpace on 2015-09-25T20:20:32Z (GMT). No. of bitstreams: 2 license.txt: 4848 bytes, checksum: 96035ab3f5e1c23cc7138a224ce498bd (MD5) 3314745.pdf: 2341010 bytes, checksum: 599acc1c893f932331404a89bb317b72 (MD5) Previous issue date: 2008","Embargo set by: Seth Robbins for item 83089 Lift date: Forever Reason: Restricted to the U of I community idenfinitely during batch ingest of legacy ETDs","Restricted to the U of I community idenfinitely during batch ingest of legacy ETDs","U of I Only","137 p.","Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 2008."],"dc:identifier":["http://hdl.handle.net/2142/81808","(MiAaPQ)AAI3314745"],"dc:language":["eng"],"dc:subject":["Engineering, Robotics"],"dc:title":["Geodesic Problems for Mobile Robots"],"dc:type":["text"],"thesis:degree_discipline":["Computer Science"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:26:17Z"}