Satisficing strategies for resource-limited policy search in dynamic environments

ABSTRACT

In this work, we examine the problem of searching for schedulable real-time control policies for resource-limited agents acting in dynamic environments. The dynamic properties of the environment and resource limitations of the agent render the problem of solving for an optimal policy infeasible. We therefore limit our search to a satisficing, rather than an optimal policy. We view the policy search as a search for a state reachability graph, with an action assigned to each of the states in the graph. In the search algorithm, we exploit properties of the reachability graphs to propagate failure conditions from inherent failure states to other states in the reachability graph, which allows us to exploit constraint satisfaction techniques to quickly remove some unacceptable policies from consideration. Our analysis and experiments show that, under certain conditions, such as when the "safe" states in the reachability graph are separated from the failure states by a relatively small set of states, we can use backtracking and memoization techniques that significantly improve the efficiency of the search algorithm.

REFERENCES

• 1: Aström, K.J.: Optimal control of Markov decision processes with incomplete state estimation. J. Math. Anal. Appl., (1965)10, 174--205.
• 2: Ella Marie Atkins , Edmund H. Durfee , Kang G. Shin, Plan generation and hard real-time execution with application to safe, autonomous flight, 1999
• 3: Boutilier C., Dean T., Hanks S.: Decision-Theoretic Planning: Structural Assumptions and Computational Leverage, Journal of Artificial Intelligence Research 1 (1999), 1--94.
• 4: Dechter R.: Learning while searching in constraint satisfaction problems, Proceedings AAAI'86 (1986).
• 5: Ginsberg M.: Dynamic backtracking, Journal of Artificial Intelligence Research 1 (1993), 25--46.
• 6: Li H., Atkins E., Durfee E., Shin K.: Practical State Probability Approximation for a Resource-Limited Real-Time Agent. Proceedings of the IJCAI-01 Workshop on Planning with Resources, (2001).
• 7: David John Musliner, CIRCA: the cooperative intelligent real-time control architecture, University of Michigan, Ann Arbor, MI, 1993
• 8: Musliner D., Durfee E., Shin K. CIRCA: A Cooperative Intelligent Real-Time Control Architecture, IEEE Transactions on Systems, Man, and Cybernetics (1993).
• 9: David J. Musliner , Edmund H. Durfee, World modeling for the dynamic construction of real-time control plans, Artificial Intelligence, v.74 n.1, p.83-127, March 1995 [doi>10.1016/0004-3702(94)00008-O]
• 10: Richard T., Richard B.: Nogood learning for Constraint Satisfaction, IC Parc Imperial College London.
• 11: Stuart J. Russell , Peter Norvig, Artificial intelligence: a modern approach, Prentice-Hall, Inc., Upper Saddle River, NJ, 1995
• 12: Schiex T., Verfaillie G.: Nogood Recording for Static and Dynamic Constraint Satisfaction Problems, Proceedings of the 5th IEEE International Conference on Tools with Artificial Intelligence (1993).
• 13: Smallwood R., Sondik E.J.: The optimal control of partially observable Markov processes over a finite horizon. (1973).
• 14: Zilberstein S, Russell, S.J. Anytime sensing, planning and action: A practical model for robot control. In Proc. 19th International Joint Conference on Artificial Intelligence, Chambery, France (1993).

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Backtracking

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Plan execution, formation, and generation

General Terms:
Algorithms, Design, Experimentation, Performance