{"id":{"repo_id":"mit","oai_identifier":"oai:dspace.mit.edu:1721.1/28429"},"canonical_url":"https://search.dev.ndltd.org/etd/mit/oai:dspace.mit.edu:1721.1/28429","repository":{"repo_id":"mit","name":"MIT","base_url":"https://dspace.mit.edu/oai/request"},"display":{"title":"Solving hybrid decision-control problems through conflict-directed branch & bound","abstract":"There exists a large class of problems that incorporate both logical decision and algebraic constraints. For example, in cooperative path planning (CPP) problem, obstacle avoidance can be achieved by selecting a direction in which to avoid every obstacle, which in turn imposes an inequality constraint. Traditionally, these hybrid decision-control problems (HDCPs) are encoded in a binary integer program (BIP). These BIPs are solved using Branch and Bound (B&B) techniques. Two problems arise with this approach. First, binary arithmetic is not a natural representation for expressing complex logical choices. Propositional and higher order logics offer a more natural encoding, and computational methods exploit this encoding. Second, current BIP solution methods are to slow to solve large HDCPs online. To address these problems, this thesis introduces an approach that unifies representations and solution methods for logic and mathematical programming. To address representational adequacy, this thesis introduces the Clausal Linear Program (CLP) formulation, which encodes logical choice using propositional clauses and continuous control decisions using linear inequalities. CLPs offer a more compact and natural encoding than BIPs for many problems of logical choice. To address computational efficiency, this thesis introduces a branch and bound method for solving CLPs, analogous to BIP-B&B. This method is then unified with conflict-directed search and unit propagation. The resulting method, CDCL-B&B, searches in a best first order, while using conflicts to steer the search away from inconsistencies. Randomized experiments on CPP problems were performed using CDCL-B&B and a BIP-B&B algorithm. Results showed that CDCL-B&B improved time efficiency by","abstract_html":"There exists a large class of problems that incorporate both logical decision and algebraic constraints. For example, in cooperative path planning (CPP) problem, obstacle avoidance can be achieved by selecting a direction in which to avoid every obstacle, which in turn imposes an inequality constraint. Traditionally, these hybrid decision-control problems (HDCPs) are encoded in a binary integer program (BIP). These BIPs are solved using Branch and Bound (B&B) techniques. Two problems arise with this approach. First, binary arithmetic is not a natural representation for expressing complex logical choices. Propositional and higher order logics offer a more natural encoding, and computational methods exploit this encoding. Second, current BIP solution methods are to slow to solve large HDCPs online. To address these problems, this thesis introduces an approach that unifies representations and solution methods for logic and mathematical programming. To address representational adequacy, this thesis introduces the Clausal Linear Program (CLP) formulation, which encodes logical choice using propositional clauses and continuous control decisions using linear inequalities. CLPs offer a more compact and natural encoding than BIPs for many problems of logical choice. To address computational efficiency, this thesis introduces a branch and bound method for solving CLPs, analogous to BIP-B&B. This method is then unified with conflict-directed search and unit propagation. The resulting method, CDCL-B&B, searches in a best first order, while using conflicts to steer the search away from inconsistencies. Randomized experiments on CPP problems were performed using CDCL-B&B and a BIP-B&B algorithm. Results showed that CDCL-B&B improved time efficiency by","abstract_has_math":false,"creators":["Krishnan, Raj, 1980-"],"institution":"Massachusetts Institute of Technology","degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":"Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science.","school":null,"contributors":[],"advisors":["Brian C. Williams."],"committee_chairs":[],"committee_members":[],"year":2004,"date_issued":"2004","date_published":"2004","updated_at":"2026-07-22T22:21:05Z","subjects":["Electrical Engineering and Computer Science."],"languages":["en_US"],"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/28429","outbound_label":"Handle","outbound_source":"dc:identifier.uri"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.advisor","label":"Advisor","values":["Brian C. Williams."]},{"key":"dc:contributor.department","label":"Department","values":["Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science."]},{"key":"dc:contributor.other","label":"Dc Contributor Other","values":["Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science."]},{"key":"dc:creator","label":"Author","values":["Krishnan, Raj, 1980-"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2005-09-26T20:24:01Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2005-09-26T20:24:01Z"]},{"key":"dc:date.issued","label":"Date","values":["2004"]},{"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":["en_US"]},{"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/28429"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Thesis (M. Eng.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2004.","\"February 2, 2004.\"","Includes bibliographical references (leaf 103)."]},{"key":"dc:description.abstract","label":"Abstract","values":["There exists a large class of problems that incorporate both logical decision and algebraic constraints. For example, in cooperative path planning (CPP) problem, obstacle avoidance can be achieved by selecting a direction in which to avoid every obstacle, which in turn imposes an inequality constraint. Traditionally, these hybrid decision-control problems (HDCPs) are encoded in a binary integer program (BIP). These BIPs are solved using Branch and Bound (B&B) techniques. Two problems arise with this approach. First, binary arithmetic is not a natural representation for expressing complex logical choices. Propositional and higher order logics offer a more natural encoding, and computational methods exploit this encoding. Second, current BIP solution methods are to slow to solve large HDCPs online. To address these problems, this thesis introduces an approach that unifies representations and solution methods for logic and mathematical programming. To address representational adequacy, this thesis introduces the Clausal Linear Program (CLP) formulation, which encodes logical choice using propositional clauses and continuous control decisions using linear inequalities. CLPs offer a more compact and natural encoding than BIPs for many problems of logical choice. To address computational efficiency, this thesis introduces a branch and bound method for solving CLPs, analogous to BIP-B&B. This method is then unified with conflict-directed search and unit propagation. The resulting method, CDCL-B&B, searches in a best first order, while using conflicts to steer the search away from inconsistencies. Randomized experiments on CPP problems were performed using CDCL-B&B and a BIP-B&B algorithm. Results showed that CDCL-B&B improved time efficiency by"]},{"key":"dc:description.degree","label":"Dc Description Degree","values":["M.Eng."]},{"key":"dc:format.mimetype","label":"Dc Format Mimetype","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Solving hybrid decision-control problems through conflict-directed branch & bound"]}]}],"canonical_facts":{"dc:contributor.advisor":["Brian C. Williams."],"dc:contributor.department":["Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science."],"dc:contributor.other":["Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science."],"dc:creator":["Krishnan, Raj, 1980-"],"dc:date.accessioned":["2005-09-26T20:24:01Z"],"dc:date.available":["2005-09-26T20:24:01Z"],"dc:date.issued":["2004"],"dc:description":["Thesis (M. Eng.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2004.","\"February 2, 2004.\"","Includes bibliographical references (leaf 103)."],"dc:description.abstract":["There exists a large class of problems that incorporate both logical decision and algebraic constraints. For example, in cooperative path planning (CPP) problem, obstacle avoidance can be achieved by selecting a direction in which to avoid every obstacle, which in turn imposes an inequality constraint. Traditionally, these hybrid decision-control problems (HDCPs) are encoded in a binary integer program (BIP). These BIPs are solved using Branch and Bound (B&B) techniques. Two problems arise with this approach. First, binary arithmetic is not a natural representation for expressing complex logical choices. Propositional and higher order logics offer a more natural encoding, and computational methods exploit this encoding. Second, current BIP solution methods are to slow to solve large HDCPs online. To address these problems, this thesis introduces an approach that unifies representations and solution methods for logic and mathematical programming. To address representational adequacy, this thesis introduces the Clausal Linear Program (CLP) formulation, which encodes logical choice using propositional clauses and continuous control decisions using linear inequalities. CLPs offer a more compact and natural encoding than BIPs for many problems of logical choice. To address computational efficiency, this thesis introduces a branch and bound method for solving CLPs, analogous to BIP-B&B. This method is then unified with conflict-directed search and unit propagation. The resulting method, CDCL-B&B, searches in a best first order, while using conflicts to steer the search away from inconsistencies. Randomized experiments on CPP problems were performed using CDCL-B&B and a BIP-B&B algorithm. Results showed that CDCL-B&B improved time efficiency by"],"dc:description.degree":["M.Eng."],"dc:format.mimetype":["application/pdf"],"dc:identifier.uri":["http://hdl.handle.net/1721.1/28429"],"dc:language.iso":["en_US"],"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":["Solving hybrid decision-control problems through conflict-directed branch & bound"],"dc:type":["Thesis"]},"updated_at":"2026-07-22T22:21:05Z"}