{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/29488"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/29488","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Solving Automated Planning Problems with Parallel Decomposition","abstract":"In this dissertation, we present a parallel decomposition method to address the complexity of solving automated planning problems. We have found many planning problems have good locality which means their actions can be clustered in such a way that nearby actions in the solution plan are usually also from the same cluster. We have also observed that the problem structure is regular and has lots of repetitions. The repetitions come from symmetric objects in the planning problem and a simplified instance with similar problem structure can be generated by reducing the number of symmetric objects. We improve heuristic search in planning by utilizing locality and symmetry and applying parallel decomposition. Our parallel decomposition approach exploits these structural properties in a domain-independent way in three steps: action partitioning, constraint resolution, and subproblem solutions. In each step, we propose solutions to exploit localities and symmetries for minimizing solution time. Our key contribution lies in the design of simplification and generalization procedures to find good heuristics in action partitioning and constraint resolution. In application of our method to solve propositional and temporal planning problems in three of the past International Planning Competitions, our results show that $\\SGPlansix$, our proposed planner, can solve more instances than other top planners. We demonstrate $\\SGPlansix$ performs well when action partitioning is useful in decreasing heuristic value. We also show $\\SGPlansix$ can achieve better quality-time trade-off. By using the symmetry and locality, we are able to achieve good coverage using our domain-independent planner but still have good performance like domain-specific planners.","abstract_html":"In this dissertation, we present a parallel decomposition method to address the complexity of solving automated planning problems. We have found many planning problems have good locality which means their actions can be clustered in such a way that nearby actions in the solution plan are usually also from the same cluster. We have also observed that the problem structure is regular and has lots of repetitions. The repetitions come from symmetric objects in the planning problem and a simplified instance with similar problem structure can be generated by reducing the number of symmetric objects. We improve heuristic search in planning by utilizing locality and symmetry and applying parallel decomposition. Our parallel decomposition approach exploits these structural properties in a domain-independent way in three steps: action partitioning, constraint resolution, and subproblem solutions. In each step, we propose solutions to exploit localities and symmetries for minimizing solution time. Our key contribution lies in the design of simplification and generalization procedures to find good heuristics in action partitioning and constraint resolution. In application of our method to solve propositional and temporal planning problems in three of the past International Planning Competitions, our results show that $\\SGPlansix$, our proposed planner, can solve more instances than other top planners. We demonstrate $\\SGPlansix$ performs well when action partitioning is useful in decreasing heuristic value. We also show $\\SGPlansix$ can achieve better quality-time trade-off. By using the symmetry and locality, we are able to achieve good coverage using our domain-independent planner but still have good performance like domain-specific planners.","abstract_has_math":true,"creators":["Hsu, Chih-Wei"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":["Wah, Benjamin W.","DeJong, Gerald F.","LaValle, Steven M.","Wong, Martin D.F."],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2012,"date_issued":"2012-02-01T00:48:57Z","date_published":"2012-02-01T00:48:57Z","updated_at":"2026-07-22T22:25:27Z","subjects":["Planning","Scheduling","Parallel Decomposition","Action Partitioning Heuristic Search"],"languages":["en"],"rights":["Copyright 2011 Chih-Wei Hsu"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/29488","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Wah, Benjamin W.","DeJong, Gerald F.","LaValle, Steven M.","Wong, Martin D.F."]},{"key":"dc:creator","label":"Author","values":["Hsu, Chih-Wei"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2012-02-01T00:48:57Z","2014-02-01T11:00:30Z","2011-12"]},{"key":"dc:type","label":"Dc Type","values":["Dissertation / Thesis","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":["Planning","Scheduling","Parallel Decomposition","Action Partitioning Heuristic Search"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2011 Chih-Wei Hsu"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/29488"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["In this dissertation, we present a parallel decomposition method to address the complexity of solving automated planning problems. We have found many planning problems have good locality which means their actions can be clustered in such a way that nearby actions in the solution plan are usually also from the same cluster. We have also observed that the problem structure is regular and has lots of repetitions. The repetitions come from symmetric objects in the planning problem and a simplified instance with similar problem structure can be generated by reducing the number of symmetric objects. We improve heuristic search in planning by utilizing locality and symmetry and applying parallel decomposition. Our parallel decomposition approach exploits these structural properties in a domain-independent way in three steps: action partitioning, constraint resolution, and subproblem solutions. In each step, we propose solutions to exploit localities and symmetries for minimizing solution time. Our key contribution lies in the design of simplification and generalization procedures to find good heuristics in action partitioning and constraint resolution. In application of our method to solve propositional and temporal planning problems in three of the past International Planning Competitions, our results show that $\\SGPlansix$, our proposed planner, can solve more instances than other top planners. We demonstrate $\\SGPlansix$ performs well when action partitioning is useful in decreasing heuristic value. We also show $\\SGPlansix$ can achieve better quality-time trade-off. By using the symmetry and locality, we are able to achieve good coverage using our domain-independent planner but still have good performance like domain-specific planners.","Item withdrawn by Katherine Eriksen (eriksen3@illinois.edu) on 2011-11-30T15:43:53Z Item was in collections: University of Illinois Theses & Dissertations (ID: 1) No. of bitstreams: 2 draft.tex: 4592 bytes, checksum: 1e758c4faa7050a56fb8df6dd67034dd (MD5) Hsu_ChihWei.pdf: 1622379 bytes, checksum: 749ce549bc4f085bb210b261c576bf13 (MD5)","Made available in DSpace on 2012-02-01T00:48:57Z (GMT). No. of bitstreams: 3 Hsu_ChihWei.pdf: 1622243 bytes, checksum: 1a7a8ffcb5964f5f80a60c017ad11992 (MD5) license.txt: 4054 bytes, checksum: a49e13f30833056bb5cd2d017b897cf4 (MD5) draft.tex: 4592 bytes, checksum: 1e758c4faa7050a56fb8df6dd67034dd (MD5)","Item marked as restricted to the 'UIUC Users [automated]' Group (id=2) by William Ingram (wingram2@illinois.edu) on 2012-02-01T00:50:42Z Item is restricted until 2014-02-01T00:50:07Z","Item reinstated by Sarah Shreeves (sshreeve@illinois.edu) on 2014-02-01T11:00:30Z Item was in collections: Graduate Theses and Dissertations at Illinois (ID: 204) Dissertations and Theses - Computer Science (ID: 587) No. of bitstreams: 4 Hsu_ChihWei.pdf.txt: 229439 bytes, checksum: f279fb15ed8119fd4b06b59389cf9d04 (MD5) Hsu_ChihWei.pdf: 1622243 bytes, checksum: 1a7a8ffcb5964f5f80a60c017ad11992 (MD5) license.txt: 4054 bytes, checksum: a49e13f30833056bb5cd2d017b897cf4 (MD5) draft.tex: 4592 bytes, checksum: 1e758c4faa7050a56fb8df6dd67034dd (MD5)","Item released from any restrictions by Sarah Shreeves (sshreeve@illinois.edu) on 2014-02-01T11:00:30Z"]},{"key":"dc:title","label":"Title","values":["Solving Automated Planning Problems with Parallel Decomposition"]}]}],"canonical_facts":{"dc:contributor":["Wah, Benjamin W.","DeJong, Gerald F.","LaValle, Steven M.","Wong, Martin D.F."],"dc:creator":["Hsu, Chih-Wei"],"dc:date":["2012-02-01T00:48:57Z","2014-02-01T11:00:30Z","2011-12"],"dc:description":["In this dissertation, we present a parallel decomposition method to address the complexity of solving automated planning problems. We have found many planning problems have good locality which means their actions can be clustered in such a way that nearby actions in the solution plan are usually also from the same cluster. We have also observed that the problem structure is regular and has lots of repetitions. The repetitions come from symmetric objects in the planning problem and a simplified instance with similar problem structure can be generated by reducing the number of symmetric objects. We improve heuristic search in planning by utilizing locality and symmetry and applying parallel decomposition. Our parallel decomposition approach exploits these structural properties in a domain-independent way in three steps: action partitioning, constraint resolution, and subproblem solutions. In each step, we propose solutions to exploit localities and symmetries for minimizing solution time. Our key contribution lies in the design of simplification and generalization procedures to find good heuristics in action partitioning and constraint resolution. In application of our method to solve propositional and temporal planning problems in three of the past International Planning Competitions, our results show that $\\SGPlansix$, our proposed planner, can solve more instances than other top planners. We demonstrate $\\SGPlansix$ performs well when action partitioning is useful in decreasing heuristic value. We also show $\\SGPlansix$ can achieve better quality-time trade-off. By using the symmetry and locality, we are able to achieve good coverage using our domain-independent planner but still have good performance like domain-specific planners.","Item withdrawn by Katherine Eriksen (eriksen3@illinois.edu) on 2011-11-30T15:43:53Z Item was in collections: University of Illinois Theses & Dissertations (ID: 1) No. of bitstreams: 2 draft.tex: 4592 bytes, checksum: 1e758c4faa7050a56fb8df6dd67034dd (MD5) Hsu_ChihWei.pdf: 1622379 bytes, checksum: 749ce549bc4f085bb210b261c576bf13 (MD5)","Made available in DSpace on 2012-02-01T00:48:57Z (GMT). No. of bitstreams: 3 Hsu_ChihWei.pdf: 1622243 bytes, checksum: 1a7a8ffcb5964f5f80a60c017ad11992 (MD5) license.txt: 4054 bytes, checksum: a49e13f30833056bb5cd2d017b897cf4 (MD5) draft.tex: 4592 bytes, checksum: 1e758c4faa7050a56fb8df6dd67034dd (MD5)","Item marked as restricted to the 'UIUC Users [automated]' Group (id=2) by William Ingram (wingram2@illinois.edu) on 2012-02-01T00:50:42Z Item is restricted until 2014-02-01T00:50:07Z","Item reinstated by Sarah Shreeves (sshreeve@illinois.edu) on 2014-02-01T11:00:30Z Item was in collections: Graduate Theses and Dissertations at Illinois (ID: 204) Dissertations and Theses - Computer Science (ID: 587) No. of bitstreams: 4 Hsu_ChihWei.pdf.txt: 229439 bytes, checksum: f279fb15ed8119fd4b06b59389cf9d04 (MD5) Hsu_ChihWei.pdf: 1622243 bytes, checksum: 1a7a8ffcb5964f5f80a60c017ad11992 (MD5) license.txt: 4054 bytes, checksum: a49e13f30833056bb5cd2d017b897cf4 (MD5) draft.tex: 4592 bytes, checksum: 1e758c4faa7050a56fb8df6dd67034dd (MD5)","Item released from any restrictions by Sarah Shreeves (sshreeve@illinois.edu) on 2014-02-01T11:00:30Z"],"dc:identifier":["http://hdl.handle.net/2142/29488"],"dc:language":["en"],"dc:rights":["Copyright 2011 Chih-Wei Hsu"],"dc:subject":["Planning","Scheduling","Parallel Decomposition","Action Partitioning Heuristic Search"],"dc:title":["Solving Automated Planning Problems with Parallel Decomposition"],"dc:type":["Dissertation / Thesis","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:25:27Z"}