{"id":{"repo_id":"mit","oai_identifier":"oai:dspace.mit.edu:1721.1/92971"},"canonical_url":"https://search.dev.ndltd.org/etd/mit/oai:dspace.mit.edu:1721.1/92971","repository":{"repo_id":"mit","name":"MIT","base_url":"https://dspace.mit.edu/oai/request"},"display":{"title":"convex segmentation and mixed-integer footstep planning for a walking robot","abstract":"This work presents a novel formulation of the footstep planning problem as a mixed-integer convex optimization. The footstep planning problem involves choosing a set of footstep locations which a walking robot can follow to safely reach a goal through an environment with obstacles. Rather than attempting to avoid the obstacles, which would require nonconvex constraints, we use integer variables to assign each footstep to a convex region of obstacle-free terrain, while simultaneously optimizing its pose within that safe region. Since existing methods for generating convex obstacle-free regions were ill-suited to this task, we also present IRIS (Iterative Regional In Inflation by Semidefinite programming), a new method to generate such regions through a series of convex optimizations. Combining IRIS with the mixed-integer optimization gives a complete footstep planning architecture, which can produce complex footstep plans on height map data constructed from onboard sensors. We demonstrate the footstep planner in simulated environments and with real data sensed by the Atlas humanoid, and we discuss future applications to running robots, aerial vehicles, and robots with more than two legs.","abstract_html":"This work presents a novel formulation of the footstep planning problem as a mixed-integer convex optimization. The footstep planning problem involves choosing a set of footstep locations which a walking robot can follow to safely reach a goal through an environment with obstacles. Rather than attempting to avoid the obstacles, which would require nonconvex constraints, we use integer variables to assign each footstep to a convex region of obstacle-free terrain, while simultaneously optimizing its pose within that safe region. Since existing methods for generating convex obstacle-free regions were ill-suited to this task, we also present IRIS (Iterative Regional In Inflation by Semidefinite programming), a new method to generate such regions through a series of convex optimizations. Combining IRIS with the mixed-integer optimization gives a complete footstep planning architecture, which can produce complex footstep plans on height map data constructed from onboard sensors. We demonstrate the footstep planner in simulated environments and with real data sensed by the Atlas humanoid, and we discuss future applications to running robots, aerial vehicles, and robots with more than two legs.","abstract_has_math":false,"creators":["Deits, Robin L. H. (Robin Lloyd Henderson)"],"institution":"Massachusetts Institute of Technology","degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":"Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science.","school":null,"contributors":[],"advisors":["Russ Tedrake."],"committee_chairs":[],"committee_members":[],"year":2014,"date_issued":"2014","date_published":"2014","updated_at":"2026-07-22T22:22:22Z","subjects":["Electrical Engineering and Computer Science."],"languages":["eng"],"rights":["M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission."],"rights_urls":["http://dspace.mit.edu/handle/1721.1/7582"],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/1721.1/92971","outbound_label":"Handle","outbound_source":"dc:identifier.uri"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.advisor","label":"Advisor","values":["Russ Tedrake."]},{"key":"dc:contributor.department","label":"Department","values":["Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science."]},{"key":"dc:contributor.other","label":"Dc Contributor Other","values":["Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science."]},{"key":"dc:creator","label":"Author","values":["Deits, Robin L. H. (Robin Lloyd Henderson)"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2015-01-20T15:31:08Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2015-01-20T15:31:08Z"]},{"key":"dc:date.issued","label":"Date","values":["2014"]},{"key":"dc:publisher","label":"Institution","values":["Massachusetts Institute of Technology"]},{"key":"dc:type","label":"Dc Type","values":["Thesis"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Electrical Engineering and 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":["M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission."]},{"key":"dc:rights.uri","label":"Rights URI","values":["http://dspace.mit.edu/handle/1721.1/7582"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.uri","label":"Identifier URI","values":["http://hdl.handle.net/1721.1/92971"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Thesis: S.M., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2014.","This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections.","Cataloged from student-submitted PDF version of thesis.","Includes bibliographical references (pages 77-82)."]},{"key":"dc:description.abstract","label":"Abstract","values":["This work presents a novel formulation of the footstep planning problem as a mixed-integer convex optimization. The footstep planning problem involves choosing a set of footstep locations which a walking robot can follow to safely reach a goal through an environment with obstacles. Rather than attempting to avoid the obstacles, which would require nonconvex constraints, we use integer variables to assign each footstep to a convex region of obstacle-free terrain, while simultaneously optimizing its pose within that safe region. Since existing methods for generating convex obstacle-free regions were ill-suited to this task, we also present IRIS (Iterative Regional In Inflation by Semidefinite programming), a new method to generate such regions through a series of convex optimizations. Combining IRIS with the mixed-integer optimization gives a complete footstep planning architecture, which can produce complex footstep plans on height map data constructed from onboard sensors. We demonstrate the footstep planner in simulated environments and with real data sensed by the Atlas humanoid, and we discuss future applications to running robots, aerial vehicles, and robots with more than two legs."]},{"key":"dc:description.degree","label":"Dc Description Degree","values":["S.M."]},{"key":"dc:title","label":"Title","values":["convex segmentation and mixed-integer footstep planning for a walking robot"]}]}],"canonical_facts":{"dc:contributor.advisor":["Russ Tedrake."],"dc:contributor.department":["Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science."],"dc:contributor.other":["Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science."],"dc:creator":["Deits, Robin L. H. (Robin Lloyd Henderson)"],"dc:date.accessioned":["2015-01-20T15:31:08Z"],"dc:date.available":["2015-01-20T15:31:08Z"],"dc:date.issued":["2014"],"dc:description":["Thesis: S.M., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2014.","This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections.","Cataloged from student-submitted PDF version of thesis.","Includes bibliographical references (pages 77-82)."],"dc:description.abstract":["This work presents a novel formulation of the footstep planning problem as a mixed-integer convex optimization. The footstep planning problem involves choosing a set of footstep locations which a walking robot can follow to safely reach a goal through an environment with obstacles. Rather than attempting to avoid the obstacles, which would require nonconvex constraints, we use integer variables to assign each footstep to a convex region of obstacle-free terrain, while simultaneously optimizing its pose within that safe region. Since existing methods for generating convex obstacle-free regions were ill-suited to this task, we also present IRIS (Iterative Regional In Inflation by Semidefinite programming), a new method to generate such regions through a series of convex optimizations. Combining IRIS with the mixed-integer optimization gives a complete footstep planning architecture, which can produce complex footstep plans on height map data constructed from onboard sensors. We demonstrate the footstep planner in simulated environments and with real data sensed by the Atlas humanoid, and we discuss future applications to running robots, aerial vehicles, and robots with more than two legs."],"dc:description.degree":["S.M."],"dc:identifier.uri":["http://hdl.handle.net/1721.1/92971"],"dc:language.iso":["eng"],"dc:publisher":["Massachusetts Institute of Technology"],"dc:rights":["M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission."],"dc:rights.uri":["http://dspace.mit.edu/handle/1721.1/7582"],"dc:subject":["Electrical Engineering and Computer Science."],"dc:title":["convex segmentation and mixed-integer footstep planning for a walking robot"],"dc:type":["Thesis"]},"updated_at":"2026-07-22T22:22:22Z"}