IP Library › Granted Patent US 12,675,731
Granted Patent B2
US 12,675,731 · App. 17/660,036 · Granted Jul 7, 2026

Action space reduction for planning domains

Inventors: Harsha Kokel (Richardson, TX); Junkyu Lee (San Diego, CA); Michael Katz (Goldens Bridge, NY); Shirin Sohrabi Araghi (Briarcliff Manor, NY); Kavitha Srinivas (Port Chester, NY)
Assignee: International Business Machines Corporation
G06N20/00G06N7/01
View Patent ↗
Loading inventors, assignments & file history…
Monitor This Case
Get email alerts when status or documents change.
Order Certified Copies
Most orders are placed with the USPTO same day — all within 24 business hours.
Order via The Patent Place →
Pre-filled with this patent's details
Quick Facts
Patent No.
US 12,675,731
App. No.
17/660,036
Filed
Apr 21, 2022
Granted
Jul 7, 2026
Kind
B2
Art Unit
2144
USPC
706/12
Abstract

Technology for: (i) receiving a domain-dependent artificial intelligence planning problem including definitions for a plurality of operators; (ii) creating an initial version of a label set, which defines an initial version of an action space, with the label set including a plurality of labels, and with each label of the plurality of labels respectively corresponding to the operators of the plurality of operators; (iii) performing, automatically and by machine logic, a label reduction on the initial version of the label set to obtain a reduced version of the label set that defines a reduced action space; and (iv) recasting the artificial planning problem as a first Markov decision process using the reduced version of label set.

Claims (50)

1 . A computer-implemented method (CIM) to save computer resources in execution of reinforcement learning artificial intelligence software, the CIM comprising:

receiving a domain-dependent artificial intelligence planning problem including definitions for a plurality of operators, the domain-dependent artificial intelligence planning problem a model-based approach relying on a symbolic model to guide a search for a solution to the domain-dependent artificial intelligence planning problem;

creating an initial version of a label set, which defines an initial version of an action space, with the label set including a plurality of labels, and with each label of the plurality of labels respectively corresponding to the operators of the plurality of operators;

performing, automatically and by machine logic, a label reduction on the initial version of the label set to obtain a reduced version of the label set that defines a reduced action space;

recasting the artificial planning problem as a first Markov decision process, the first Markov decision process using the reduced version of the label set generated by the machine logic; and

resolving the artificial intelligence planning problem relying on the symbolic model and outputting a planning recommendation by performing reinforcement learning using the first Markov decision process with the reduced version of the label set generated by the machine logic.

2 . The CIM of claim 1 wherein the performance of the label reduction includes:

determination, by machine logic, of a mutex group of operators from the plurality of operators; and

using the mutex group of state dependent operators to reduce a number of labels in the reduced version of the action space relative to a number of labels in the original version of the action space.

3 . The CIM of claim 1 further comprising:

translating the artificial intelligence planning problem to delete-free planning terms.

4 . The CIM of claim 1 further comprising:

exploring the space of plans to obtain a seed set of high quality.

5 . The CIM of claim 1 wherein the performance of label reduction includes:

finding a mutex group via reduction of operator parameters, such that the mutex group is found separately for each operator of the plurality of operators.

6 . A computer program product (CPP) to save computer resources in execution of reinforcement learning artificial intelligence software, the CIM comprising:

a set of storage device(s); and

computer code stored collectively in the set of storage device(s), with the computer code including data and instructions to cause a processor(s) set to perform at least the following operations:

receiving a domain-dependent artificial intelligence planning problem including definitions for a plurality of operators, the domain-dependent artificial intelligence planning problem a model-based approach relying on a symbolic model to guide a search for a solution to the domain-dependent artificial intelligence planning problem,

creating an initial version of a label set, which defines an initial version of an action space, with the label set including a plurality of labels, and with each label of the plurality of labels respectively corresponding to the operators of the plurality of operators,

performing, automatically and by machine logic, a label reduction on the initial version of the label set to obtain a reduced version of the label set that defines a reduced action space;

recasting the artificial planning problem as a first Markov decision process, the first Markov decision process using the reduced version of the label set generated by the machine logic; and

resolving the artificial intelligence planning problem relying on the symbolic model and outputting a planning recommendation by performing reinforcement learning using the first Markov decision process with the reduced version of the label set generated by the machine logic.

7 . The CPP of claim 6 wherein the performance of the label reduction includes:

determination, by machine logic, of a mutex group of operators from the plurality of operators; and

using the mutex group of state dependent operators to reduce a number of labels in the reduced version of the action space relative to a number of labels in the original version of the action space.

8 . The CPP of claim 6 wherein the computer code further includes instructions for causing the processor(s) set to perform the following operation(s):

translating the artificial intelligence planning problem to delete-free planning terms.

9 . The CPP of claim 6 wherein the computer code further includes instructions for causing the processor(s) set to perform the following operation(s):

exploring the space of plans to obtain a seed set of high quality.

10 . The CPP of claim 6 wherein the performance of label reduction includes:

finding a mutex group via reduction of operator parameters, such that the mutex group is found separately for each operator of the plurality of operators.

11 . A computer system (CS) to save computer resources in execution of reinforcement learning artificial intelligence software, comprising:

a processor(s) set;

a set of storage device(s); and

computer code stored collectively in the set of storage device(s), with the computer code including data and instructions to cause the processor(s) set to perform at least the following operations:

receiving a domain-dependent artificial intelligence planning problem including definitions for a plurality of operators, the domain-dependent artificial intelligence planning problem a model-based approach relying on a symbolic model to guide a search for a solution to the domain-dependent artificial intelligence planning problem,

creating an initial version of a label set, which defines an initial version of an action space, with the label set including a plurality of labels, and with each label of the plurality of labels respectively corresponding to the operators of the plurality of operators,

performing, automatically and by machine logic, a label reduction on the initial version of the label set to obtain a reduced version of the label set that defines a reduced action space;

recasting the artificial planning problem as a first Markov decision process, the first Markov decision process using the reduced version of the label set generated by the machine logic; and

resolving the artificial intelligence planning problem relying on the symbolic model and outputting a planning recommendation by performing reinforcement learning using the first Markov decision process with the reduced version of the label set generated by the machine logic.

12 . The CS of claim 11 wherein the performance of the label reduction includes:

determination, by machine logic, of a mutex group of operators from the plurality of operators; and

using the mutex group of state dependent operators to reduce a number of labels in the reduced version of the action space relative to a number of labels in the original version of the action space.

13 . The CS of claim 11 wherein the computer code further includes instructions for causing the processor(s) set to perform the following operation(s):

translating the artificial intelligence planning problem to delete-free planning terms.

14 . The CS of claim 11 wherein the computer code further includes instructions for causing the processor(s) set to perform the following operation(s):

exploring the space of plans to obtain a seed set of high quality.

15 . The CS of claim 11 wherein the performance of label reduction includes:

finding a mutex group via reduction of operator parameters, such that the mutex group is found separately for each operator of the plurality of operators.

Assignments (1)
ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded Apr 21, 2022
From: KOKEL, HARSHA; LEE, JUNKYU; KATZ, MICHAEL; SOHRABI ARAGHI, SHIRIN; SRINIVAS, KAVITHA
To: INTERNATIONAL BUSINESS MACHINES CORPORATION
Reel/Frame 059660/0482 →
Continuity (1)
Related Publication 20230342653A1 · Oct 26, 2023
References Cited (63)
US 9747550B2 · Hassanzadeh · 2017 [cited by applicant]
US 10475537B2 · Purdie · 2019 [cited by applicant]
US 10783441B2 · Riabov · 2020 [cited by applicant]
US 11030561B2 · Chang · 2021 [cited by applicant]
US 11061718B2 · Vukovic · 2021 [cited by applicant]
US 11237933B2 · Riabov · 2022 [cited by applicant]
US 20130185119A1 · Palao · 2013 [cited by applicant]
US 20150227589A1 · Chakrabarti · 2015 [cited by examiner]
US 20190265703A1 · Hicok · 2019 [cited by applicant]
US 20210004741A1 · Katz · 2021 [cited by applicant]
US 20210089958A1 · Theocharous · 2021 [cited by examiner]
US 20210216879A1 · Katz · 2021 [cited by applicant]
US 20210326695A1 · Vitebsky · 2021 [cited by examiner]
US 20220253743A1 · Wang · 2022 [cited by examiner]
US 20230016233A1 · Gubbi Lakshminarasimha · 2023 [cited by examiner]
US 20240330301A1 · Kokel et al. · 2024 [cited by applicant]
Sievers, Silvan. “Merge-and-shrink heuristics for classical planning: Efficient implementation and partial abstractions.” Proceedings of the International Symposium on Combinatorial Search. vol. 9. No. 1. 2018 (Year: 20… [cited by examiner]
Robinson, Nathan, Sheila A. McIlraith, and David Toman. “Query Optimization Revisited: An AI Planning Perspective.” SPARK 2013 (Year: 2013). [cited by examiner]
Bao, et al., “Deep Learning-based Job Placement in Distributed Machine Learning Clusters”, In IEEE InfoCom 2019—IEEE Conference on Computer Communications, Apr. 2019, pp. 505-513. [cited by applicant]
Botea, et al., “Macro-FF: Improving AI Planning with Automatically Learned Macro-Operators”, Journal of Artificial Intelligence Research, 24, Oct. 2005, 41 pgs. [cited by applicant]
Boutilier, et al., “Symbolic Dynamic Programming for First-Order MDPs”, IJCAI International Joint Conference on Artificial Intelligence, Feb. 11, 2002, 8 pgs. [cited by applicant]
Dong, et al., “Neural Logic Machines”, Published as a conference paper at ICLR 2019, Apr. 26, 2019, 22 pgs., arXiv:1904.11694v1 [cs.AI]. [cited by applicant]
Dulac-Arnold, et al., “Fast Reinforcement Learning with Large Action Sets Using Error-Correcting Output Codes For MDP Factorization”, In Joint European Conference on Machine Learning and Knowledge Discovery in Databases… [cited by applicant]
Dzeroski, et al., “Relational Reinforcement Learning”, Machine Learning, 43, 2001, 46 pgs, 2001 Kluwer Academic Publishers, Manufactured in The Netherlands. [cited by applicant]
Fern, et al., “Approximate Policy Iteration with a Policy Language Bias”, Advances in Neural Information Processing Systems 16 (NIPS 2003), 8 pgs. [cited by applicant]
Gehring, et al., “Reinforcement Learning for Classical Planning: Viewing Heuristics as Dense Reward Generators”, PRL Workshop at ICAPS 2021, Sep. 30, 2021, 15 pgs., arXiv:2109.14830v1 [cs.AI]. [cited by applicant]
Jiang, et al., “Neural Logic Reinforcement Learning”, Proceedings of the 36 th International Conference on Machine Learning, Long Beach, California, PMLR 97, Jul. 10, 2019, 10 pgs., arXiv:1904.10729v2 [cs.LG]. [cited by applicant]
Rivlin, et al., “Generalized Planning with Deep Reinforcement Learning”, May 6, 2020, 13 pgs., arXiv:2005.02305v1 [cs.AI]. [cited by applicant]
Silver, et al., “PDDLGym: Gym Environments from PDDL Problems”, MIT Computer Science and Artificial Intelligence Laboratory, Sep. 17, 2020, 8 pgs., arXiv:2002.06432v2 [cs.AI]. [cited by applicant]
Vallati, et al., “On the Importance of Domain Model Configuration for Automated Planning Engines”, Journal of Automated Reasoning, arXiv:2010.07710v1 [cs.AI], Oct. 15, 2020, 49 pgs. [cited by applicant]
Zahavy, et al., “Learn What Not to Learn: Action Elimination with Deep Reinforcement Learning”, 32nd Conference on Neural Information Processing Systems (NeurIPS 2018), Montreal, Canada, 2018, 12 pgs. [cited by applicant]
Appendix P—List of IBM Patents or Patent Applications Treated as Related, Filed herewith, 2 Pages. [cited by applicant]
Backstrom, Christer, “Complexity Results for SAS Planning”, Computational Intelligence, vol. 11, Nov. 4, 1995, 34 pages. [cited by applicant]
Bamford, Christopher et al., “Generalising Discrete Action Spaces with Conditional Action Trees”, 2021 IEEE Conference on Games (CoG), Aug. 17-20, 2021, 8 pages. [cited by applicant]
Boutilier, Craig et al., “Planning and Learning with Stochastic Action Sets”, Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence (IJCAI-18), Jul. 13-19, 2018, 9 pages. [cited by applicant]
Correa, Augusto B. et al., “Delete-Relaxation Heuristics for Lifted Classical Planning”, Proceedings of the Thirty-First International Conference on Automated Planning and Scheduling (ICAPS 2021), Aug. 2-13, 2021, 9 pag… [cited by applicant]
Correa, et al., “Lifted Successor Generation Using Query Optimization Techniques”, Proceedings of the Thirtieth International Conference on Automated Planning and Scheduling (ICAPS 2020), Jun. 1, 2020, 10 pgs. [cited by applicant]
Fiser, Daniel, “Lifted Fact-Alternating Mutex Groups and Pruned Grounding of Classical Planning Problems”, Thirty-Fourth AAAI Conference on Artificial Intelligence (AAAI-20), Feb. 7-12, 2020, 8 pages. [cited by applicant]
Gefen, Avitan et al., “The Minimal Seed Set Problem”, Proceedings of the Twenty-First International Conference on Automated Planning and Scheduling (ICAPS 2011), Jun. 11-16, 2011, 4 pages. [cited by applicant]
Geiber, Florian et al., “Trial-Based Heuristic Tree Search for MDPs with Factored Action Spaces”, Thirteenth International Symposium on Combinatorial Search (SoCS 2020), May 26-28, 2020, 10 pages. [cited by applicant]
Guestrin, Carlos et al., “Coordinated Reinforcement Learning”, Nineteenth International Conference on Machine Learning (ICML-2002), Jul. 8-12, 2002, 8 pages. [cited by applicant]
Haslum, Patrik, “Computing Genome Edit Distances using Domain-Independent Planning”, Proceedings of the Twenty-First International Conference on Automated Planning and Scheduling (ICAPS 2011), Jun. 11-16, 2011, 7 pages. [cited by applicant]
Helmert, Malte et al., “Merge-and-Shrink Abstraction: A Method for Generating Lower Bounds in Factored State Spaces”, Journal of the ACM, vol. 61, No. 3, Article 16, May 2014, 63 pages. [cited by applicant]
Helmert, Malte et al., “The Fast Downward Planning System”, Journal of Artificial Intelligence Research 26 (2006) 191-246, Jul. 2006, 56 pages. [cited by applicant]
Helmert, Malte, “Concise finite-domain representations for PDDL planning tasks”, Artificial Intelligence, vol. 173, Nos. 5/6, 503-535, Apr. 2009, 33 pages. [cited by applicant]
Hoffman, Matthew W. et al., “Acme: A Research Framework for Distributed Reinforcement Learning”, arXiv:2006.00979v2 [cs.LG], Sep. 20, 2022, 36 pages. [cited by applicant]
Huang, Shengyi et al., “A Closer Look at Invalid Action Masking in Policy Gradient Algorithms”, Thirty-Fifth International Florida AI Research Society Conference (FLAIRS 2022), May 15-18, 2022, 6 pages. [cited by applicant]
Kanervisto, Anssi et al., “Action Space Shaping in Deep Reinforcement Learning”, 2020 IEEE Conference on Games (CoG 2020), Aug. 24-27, 2020, 8 pages. [cited by applicant]
Kokel, et al., “How to Reduce Action Space for Planning Domains? (Student Abstract)”, The Thirty-Sixth AAAI Conference on Artificial Intelligence (AAAI-22), Jun. 28, 2022, 2 pgs. [cited by applicant]
Kokel, et al., “Identification of Actions in Artificial Intelligence Planning”, filed Mar. 28, 2023, U.S. Appl. No. 18/127,357, 54 pgs. [cited by applicant]
Lauer, Pascal et al., “Polynomial-Time in PDDL Input Size: Making the Delete Relaxation Feasible for Lifted Planning”, Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence (IJCAI-21), A… [cited by applicant]
Matloob, Rami et al., “Exploring Organic Synthesis with State-of-the-Art Planning Techniques”, Scheduling and Planning Applications woRKshop (SPARK) at ICAPS, Jun. 14, 2016, 10 pages. [cited by applicant]
Mcdermott, Drew, “The 1998 AI Planning Systems Competition”, AI Magazine vol. 21 No. 2, Summer 2000, Jun. 15, 2000, 22 pages. [cited by applicant]
Nelson, Mark J., “Estimates for the Branching Factors of Atari Games”, 2021 IEEE Conference on Games (CoG), Aug. 17-20, 2021, 5 pages. [cited by applicant]
Pazis, Jason et al., “Reinforcement Learning in Multidimensional Continuous Action Spaces”, IEEE Symposium on Adaptive Dynamic Programming and Reinforcement, Apr. 11-15, 2011, 8 pages. [cited by applicant]
Riabov, Anton et al., “Planning-Based Reasoning for Automated Large-Scale Data Analysis”, Proceedings of the Twenty-Fifth International Conference on Automated Planning and Scheduling, Jun. 7-11, 2015, 9 pages. [cited by applicant]
Sievers, Silvan et al., “Generalized Label Reduction for Merge-and-Shrink Heuristics”, Proceedings of the Twenty-Eighth AAAI Conference on Artificial Intelligence (AAAI-14), Jul. 27-31, 2014, 9 pages. [cited by applicant]
Sohrabi, Shirin et al., “An AI Planning Solution to Scenario Generation for Enterprise Risk Management”, Thirty-Second AAAI Conference on Artificial Intelligence (AAAI-18), Feb. 2-7, 2018, 8 pages. [cited by applicant]
Sohrabi, Shirin et al., “Hypothesis Exploration for Malware Detection using Planning”, Proceedings of the Twenty-Seventh AAAI Conference on Artificial Intelligence, Jul. 14-18, 2013, 7 pages. [cited by applicant]
Sohrabi, Shirin et al., “State Projection via AI Planning”, Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence (AAAI-17), Feb. 4-9, 2017, 7 pages. [cited by applicant]
Ullman, Jeffrey D., “Principles of Database and Knowledge-Base Systems, vol. II”, Computer Science Press, Nov. 1, 1990, 3 pages. [cited by applicant]
Sohrabi, et al., Scenario Planning for Enterprise Risk Management, Proceedings of Application Showcase Program at the 27th International Conference on Automated Planning and Scheduling, Jun. 2017, 3 pages. [cited by applicant]
Horcik et al. ‘Endomorphisms of Lifted Planning Problems, Proceedings of the Thirty-First International Conference on Automated Planning and Scheduling, May 17, 2021, 10 pages, vol. 31. [cited by applicant]