{"id":{"repo_id":"wustl","oai_identifier":"oai:openscholarship.wustl.edu:etd-1933"},"canonical_url":"https://search.dev.ndltd.org/etd/wustl/oai:openscholarship.wustl.edu:etd-1933","repository":{"repo_id":"wustl","name":"Washington University in St. Louis","base_url":"https://openscholarship.wustl.edu/do/oai/"},"display":{"title":"Partial Order Reduction for Planning","abstract":"Partial Order Reduction: POR) is a technique that reduces the search space by recognizing interchangeable orders between actions and expanding only a subset of all possible orders during the search. It has been extensively studied in model checking and has proven to be an enabling technique for reducing the search space and costs. Several POR algorithms have been proposed in planning, including the Expansion Core: EC) and Stratified Planning: SP) algorithms. Being orthogonal to the development of accurate heuristic functions, these reduction methods show great potential to improve the planning efficiency from a new perspective. However, it is unclear how these POR methods relate to each other and whether there exist stronger reduction methods. In this thesis, we have proposed a unifying theory that provides a necessary and sufficient condition for two actions to be semi-commutative. We have also revealed that semi-commutativity is the central property that enables POR. We have also interpreted both EC and SP algorithms using this new theory. Further, we have proposed new, stronger POR algorithms based on the new theory. We have also applied these new algorithms to solve benchmark problems across various planning domains. Experimental results have shown significant search cost reduction.","abstract_html":"Partial Order Reduction: POR) is a technique that reduces the search space by recognizing interchangeable orders between actions and expanding only a subset of all possible orders during the search. It has been extensively studied in model checking and has proven to be an enabling technique for reducing the search space and costs. Several POR algorithms have been proposed in planning, including the Expansion Core: EC) and Stratified Planning: SP) algorithms. Being orthogonal to the development of accurate heuristic functions, these reduction methods show great potential to improve the planning efficiency from a new perspective. However, it is unclear how these POR methods relate to each other and whether there exist stronger reduction methods. In this thesis, we have proposed a unifying theory that provides a necessary and sufficient condition for two actions to be semi-commutative. We have also revealed that semi-commutativity is the central property that enables POR. We have also interpreted both EC and SP algorithms using this new theory. Further, we have proposed new, stronger POR algorithms based on the new theory. We have also applied these new algorithms to solve benchmark problems across various planning domains. Experimental results have shown significant search cost reduction.","abstract_has_math":false,"creators":["Xu, You"],"institution":null,"degree_name":"Master of Arts (MA)","degree_level":"Thesis","degree_discipline":"Computer Science and Engineering","degree_department":null,"school":null,"contributors":["Yixin Chen"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2009,"date_issued":"2009-01-01T08:00:00Z","date_published":"2009-01-01T08:00:00Z","updated_at":"2026-07-24T06:12:48Z","subjects":["planning","space reduction"],"languages":["English (en)"],"rights":[],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier.doi","label":"DOI","values":["https://doi.org/10.7936/K7P26W5D"],"render_values":[{"text":"https://doi.org/10.7936/K7P26W5D","href":"https://doi.org/10.7936/K7P26W5D","code":true}]}]},"links":{"outbound_url":"https://openscholarship.wustl.edu/etd/934","outbound_label":"Repository record","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Yixin Chen"]},{"key":"dc:creator","label":"Author","values":["Xu, You"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.available","label":"Dc Date Available","values":["2013-05-25T07:00:00Z"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science and Engineering"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Thesis"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Master of Arts (MA)"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["planning","space reduction"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["English (en)"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["https://openscholarship.wustl.edu/etd/934"]},{"key":"dc:identifier.doi","label":"DOI","values":["https://doi.org/10.7936/K7P26W5D"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["Partial Order Reduction: POR) is a technique that reduces the search space by recognizing interchangeable orders between actions and expanding only a subset of all possible orders during the search. It has been extensively studied in model checking and has proven to be an enabling technique for reducing the search space and costs. Several POR algorithms have been proposed in planning, including the Expansion Core: EC) and Stratified Planning: SP) algorithms. Being orthogonal to the development of accurate heuristic functions, these reduction methods show great potential to improve the planning efficiency from a new perspective. However, it is unclear how these POR methods relate to each other and whether there exist stronger reduction methods. In this thesis, we have proposed a unifying theory that provides a necessary and sufficient condition for two actions to be semi-commutative. We have also revealed that semi-commutativity is the central property that enables POR. We have also interpreted both EC and SP algorithms using this new theory. Further, we have proposed new, stronger POR algorithms based on the new theory. We have also applied these new algorithms to solve benchmark problems across various planning domains. Experimental results have shown significant search cost reduction."]},{"key":"dc:title","label":"Title","values":["Partial Order Reduction for Planning"]}]}],"canonical_facts":{"dc:contributor":["Yixin Chen"],"dc:creator":["Xu, You"],"dc:date.available":["2013-05-25T07:00:00Z"],"dc:description.abstract":["Partial Order Reduction: POR) is a technique that reduces the search space by recognizing interchangeable orders between actions and expanding only a subset of all possible orders during the search. It has been extensively studied in model checking and has proven to be an enabling technique for reducing the search space and costs. Several POR algorithms have been proposed in planning, including the Expansion Core: EC) and Stratified Planning: SP) algorithms. Being orthogonal to the development of accurate heuristic functions, these reduction methods show great potential to improve the planning efficiency from a new perspective. However, it is unclear how these POR methods relate to each other and whether there exist stronger reduction methods. In this thesis, we have proposed a unifying theory that provides a necessary and sufficient condition for two actions to be semi-commutative. We have also revealed that semi-commutativity is the central property that enables POR. We have also interpreted both EC and SP algorithms using this new theory. Further, we have proposed new, stronger POR algorithms based on the new theory. We have also applied these new algorithms to solve benchmark problems across various planning domains. Experimental results have shown significant search cost reduction."],"dc:identifier":["https://openscholarship.wustl.edu/etd/934"],"dc:identifier.doi":["https://doi.org/10.7936/K7P26W5D"],"dc:language":["English (en)"],"dc:subject":["planning","space reduction"],"dc:title":["Partial Order Reduction for Planning"],"thesis:degree_discipline":["Computer Science and Engineering"],"thesis:degree_level":["Thesis"],"thesis:degree_name":["Master of Arts (MA)"]},"updated_at":"2026-07-24T06:12:48Z"}