Solving hybrid decision-control problems through conflict-directed branch & bound
Thesis (M. Eng.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2004.
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | en_US |
| Published: |
Massachusetts Institute of Technology
2005
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/28429 |
| _version_ | 1811074084697538560 |
|---|---|
| author | Krishnan, Raj, 1980- |
| author2 | Brian C. Williams. |
| author_facet | Brian C. Williams. Krishnan, Raj, 1980- |
| author_sort | Krishnan, Raj, 1980- |
| collection | MIT |
| description | Thesis (M. Eng.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2004. |
| first_indexed | 2024-09-23T09:42:55Z |
| format | Thesis |
| id | mit-1721.1/28429 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T09:42:55Z |
| publishDate | 2005 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/284292019-04-11T09:22:34Z Solving hybrid decision-control problems through conflict-directed branch & bound Solving HDCPs through CD-B&B Krishnan, Raj, 1980- Brian C. Williams. Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science. Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science. Electrical Engineering and Computer Science. Thesis (M. Eng.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2004. "February 2, 2004." Includes bibliographical references (leaf 103). 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 by Raj Krishnan. M.Eng. 2005-09-26T20:24:01Z 2005-09-26T20:24:01Z 2004 Thesis http://hdl.handle.net/1721.1/28429 56993912 en_US 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. http://dspace.mit.edu/handle/1721.1/7582 103 leaves 6605027 bytes 6616998 bytes application/pdf application/pdf application/pdf Massachusetts Institute of Technology |
| spellingShingle | Electrical Engineering and Computer Science. Krishnan, Raj, 1980- Solving hybrid decision-control problems through conflict-directed branch & bound |
| title | Solving hybrid decision-control problems through conflict-directed branch & bound |
| title_full | Solving hybrid decision-control problems through conflict-directed branch & bound |
| title_fullStr | Solving hybrid decision-control problems through conflict-directed branch & bound |
| title_full_unstemmed | Solving hybrid decision-control problems through conflict-directed branch & bound |
| title_short | Solving hybrid decision-control problems through conflict-directed branch & bound |
| title_sort | solving hybrid decision control problems through conflict directed branch bound |
| topic | Electrical Engineering and Computer Science. |
| url | http://hdl.handle.net/1721.1/28429 |
| work_keys_str_mv | AT krishnanraj1980 solvinghybriddecisioncontrolproblemsthroughconflictdirectedbranchbound AT krishnanraj1980 solvinghdcpsthroughcdbb |