Skip to main content

Dynamic Programming with Imprecise and Uncertain Information

  • Chapter
  • First Online:
Automatic Control, Robotics, and Information Processing

Part of the book series: Studies in Systems, Decision and Control ((SSDC,volume 296))

Abstract

Basic models of multistage fuzzy control are presented in which goals on the consecutively attained states (outputs) and constraints on the consecutively applied controls (inputs) are specified in an imprecise form as fuzzy sets defined in the space of states and controls, respectively. In such a setting, first, the classic problem of the multistage control of a deterministic system, given as a state transition equation, is considered followed by a discussion of the control of a stochastic system given as a Markov chain. For both cases the problems with the finite, fixed and specified termination time and infinite termination time are discussed. They and solved by using fuzzy dynamic programming in the case of the finite, fixed and specified termination time. In the case of the infinite termination time they are solved by using a policy iteration type algorithm. Some well known and successful applications of the models proposed are discussed.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 149.00
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 199.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info
Hardcover Book
USD 199.99
Price excludes VAT (USA)
  • Durable hardcover edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

References

  1. Abo-Sinna, M.A.: Multiple objective (fuzzy) dynamic programming problems: a survey and some applications. Appl. Math. Comput. 157(3), 861–888 (2004)

    MathSciNet  MATH  Google Scholar 

  2. Baldwin, J.F., Pilsworth, B.W.: Dynamic programming for fuzzy systems with fuzzy environment. J. Math. Anal. Appl. 85, 1–23 (1982)

    Article  MathSciNet  MATH  Google Scholar 

  3. Belarbi, K.H., Megri, F.: A stable model-based fuzzy predictive control based on fuzzy dynamic programming. IEEE Trans. Fuzzy Syst. 15(4), 746–754 (2007)

    Article  Google Scholar 

  4. Bellman, R.E.: Dynamic Programming. Princeton University Press (1957)

    Google Scholar 

  5. Bellman, R.E., Zadeh, L.A.: Decision making in a fuzzy environment. Manag. Sci. 17, 141–164 (1970)

    Article  MathSciNet  MATH  Google Scholar 

  6. Bertsekas, D.P.: Dynamic Programming and Stochastic Control. Academic Press, New York (1976)

    Google Scholar 

  7. Bertsekas, D.P., Shreve, S.E.: Stochastic Optimal Control: The Discrete Time Case. Academic Press, New York (1978)

    Google Scholar 

  8. Bertsekas, D.P.: Dynamic Programming: Deterministic and Stochastic Models. Prentice-Hall (1987)

    Google Scholar 

  9. Denardo, E.V.: Dynamic Programming: Models and Applications. Dover, Mineola, NY (2003)

    Google Scholar 

  10. Esogbue A.O.: Dynamic programming, fuzzy sets and the modeling of R&D management control systems. IEEE Trans. Syst. Man Cybern. SMC-13, 18–30 (1983)

    Google Scholar 

  11. Esogbue A.O.: A fuzzy dynamic programming model of intra-operative anesthesia administration. In: Kacprzyk, J., Yager, R.R. (eds.) Management Decision Support Systems Using Fuzzy Sets and Possibility Theory. Verlag TÜV Rheinland, Cologne, str. 155–161 (1985)

    Google Scholar 

  12. Esogbue, A.O.: Optimal clustering of fuzzy data via fuzzy dynamic programming. Fuzzy Sets Syst. 18, 283–298 (1986)

    Article  MathSciNet  MATH  Google Scholar 

  13. Esogbue, A.O.: Dynamic Programming for Optimal Water Resources Systems Analysis. Prentice-Hall, Englewood Cliffs, NJ (1989)

    Google Scholar 

  14. Esogbue, A.O., Ahipo, Z.M.: A fuzzy sets model for measuring the effectiveness of public participation in water resources planning. Water Resour. Bull. 18, 451–456 (1982)

    Article  Google Scholar 

  15. Esogbue, A.O., Bellman, R.E.: Fuzzy dynamic programming and its extensions. TIMS/Stud. Manag. Sci. 20, 147–167 (1984)

    MathSciNet  MATH  Google Scholar 

  16. Esogbue, A.O., Fedrizzi, M., Kacprzyk, J.: Fuzzy dynamic programming with stochastic systems. Kacprzyk, J., Fedrizzi, M. (eds.) Combining Fuzzy Imprecision with Probabilistic Uncertainty in Decision Making. Springer, Berlin/New York, str. 266–285 (1988)

    Google Scholar 

  17. Esogbue, A.O., Kacprzyk, J.: Fuzzy dynamic programming: a survey of main developments and applications. Fuzzy Sets Syst. 81, 31–45 (1996)

    Article  MATH  Google Scholar 

  18. Esogbue, A.O., Ramesh, V.: Dynamic programming and fuzzy allocation processes. Technical Memo No. 202, Department of Operations Research, Case Western University, Cleveland, OH (1970)

    Google Scholar 

  19. Esogbue, A.O., Theologidu, M., Guo, K.: On the application of fuzzy sets theory to the optimal flood control problem arising in water resources systems. Fuzzy Sets Syst. 48, 155–172 (1992)

    Article  Google Scholar 

  20. Filev, D., Angelov, P.: Fuzzy optimal control. Fuzzy Sets Syst. 47, 151–156 (1992)

    Article  MathSciNet  MATH  Google Scholar 

  21. Francelin, R.A., Kacprzyk, J., Gomide, F.A.C.: Neural network based algorithm for dynamic system optimization. Asian J. Control. 3(2), 131–142 (2001)

    Google Scholar 

  22. Francelin, R.A., Gomide, F.A.C., Kacprzyk, J.: A biologically inspired neural network for dynamic programming. Int. J. Neural Syst. 11(6), 561–572 (2001)

    Article  Google Scholar 

  23. Gál, L., Kóczy, L.T.: Advanced bacterial memetic algorithms. Acta Technica Jauriniensis, Series Intelligentia Combinatorica 1(3), 481–498 (2008)

    Google Scholar 

  24. Gluss, B.: Fuzzy multistage decision-making, fuzzy state and terminal regulators and their relationship to non-fuzzy quadratic state and terminal regulators. Int. J. Control 17, 177–192 (1972)

    Article  MathSciNet  MATH  Google Scholar 

  25. Howard, R.A.: Dynamic Programming and Markov Processes. MIT Press, Cambridge, MA (1960)

    Google Scholar 

  26. Howard, R.A.: Dynamic Probabilistic Systems, vol. 1 and 2. Wiley, New York (1971)

    Google Scholar 

  27. Huang, C.J., Lin, C.E., Huang, C.L.: Fuzzy approach for generator maintenance scheduling. Electr. Power Syst. Res. 24, 31–38 (1992)

    Article  Google Scholar 

  28. Iwamoto, S.: Fuzzy dynamic programming in stochastic environment. In: Yoshida, Y. (ed.) Dynamic Aspects in Fuzzy Decision Making, pp. 27–51. Physica-Verlag, Heidelberg and New York (2001)

    Google Scholar 

  29. Iwamoto, S., Sniedovich, M.: Sequential decision making in fuzzy environment. J. Math. Anal. Appl. 222, 208–224 (1998)

    Article  MathSciNet  MATH  Google Scholar 

  30. Iwamoto, S., Tsurusaki, K., Fujita, T.: On Markov policies for minimax decision processes. J. Math. Anal. Appl. 253, 58–78 (2001)

    Article  MathSciNet  MATH  Google Scholar 

  31. Kacprzyk, J.: Control of a non-fuzzy system in a fuzzy environment with a fuzzy termination time. Syst. Sci. 3, 320–334 (1977)

    MathSciNet  Google Scholar 

  32. Kacprzyk, J.: A branch-and-bound algorithm for the multistage control of a non-fuzzy system in a fuzzy environment. Control Cybern. 7, 51–64 (1978)

    Google Scholar 

  33. Kacprzyk, J.: Control of a stochastic system in a fuzzy environment with a fuzzy termination time. Syst. Sci. 4, 291–300 (1978)

    Google Scholar 

  34. Kacprzyk, J.: Decision-making in a fuzzy environment with fuzzy termination time. Fuzzy Sets Syst. 1, 169–179 (1978)

    Google Scholar 

  35. Kacprzyk, J.: A branch-and-bound algorithm for the multistage control of a fuzzy system in a fuzzy environment. Kybernetes 8, 139–147 (1979)

    Article  MATH  Google Scholar 

  36. Kacprzyk, J.: Control of a stochastic system in a fuzzy environment with Yager’s probability of a fuzzy event. Busefal 12, 77–88 (1982)

    MATH  Google Scholar 

  37. Kacprzyk, J.: Wieloetapowe Podejmowanie Decyzji w Warunkach Rozmyto”sci (in Polish). PWN, Warszawa–“L”od”z (1983)

    Google Scholar 

  38. Kacprzyk, J.: Multistage Decision Making under Fuzziness. Verlag TÜV Rheinland, Cologne (1983)

    Google Scholar 

  39. Kacprzyk, J.: A generalization of fuzzy multistage decision making and control via linguistic quantifiers. Int. J. Control. 38, 1249–1270 (1983)

    Google Scholar 

  40. Kacprzyk, J.: Yager’s probability of a fuzzy event in stochastic control under fuzziness. In: Gupta, M.M., Sanchez, M. (eds.) Fuzzy Information, Knowledge Representation and Decision Analysis, pp. 379–384. Pergamon Press, Oxford (1984)

    Google Scholar 

  41. Kacprzyk, J.: Towards human-consistent multistage decision making and control models via fuzzy sets and fuzzy logic. Bellman Memorial Issue (A.O. Esogbue, ed.). Fuzzy Sets Syst. 18, 299–314 (1986)

    Article  MATH  Google Scholar 

  42. Kacprzyk, J.: Stochastic systems in fuzzy environments: control. In: Singh, M.G. (ed.) Systems and Control Encyclopedia, pp. 4657–4661. Pergamon Press, Oxford (1987)

    Google Scholar 

  43. Kacprzyk, J.: Interpolative reasoning in optimal fuzzy control. In: Proceedings of Second IEEE International Conference on Fuzzy Systems—FUZZ–IEEE’93, vol. II, pp. 1259–1263 (1993)

    Google Scholar 

  44. Kacprzyk, J.: Interpolative reasoning for computationally efficient optimal fuzzy control. In: Proceedings of Fifth International Fuzzy Systems Association World Congress ’93 (Seoul, Korea), vol. II, str. 1270–1273 (1993)

    Google Scholar 

  45. Kacprzyk, J.: Fuzzy dynamic programming—battling against the curse of dimensionality via interpolative reasoning. In: Proceedings of Third International Conference on Fuzzy Logic, Neural Nets and Soft Computing—IIZUKA’94, pp. 245–246 (1994)

    Google Scholar 

  46. Kacprzyk, J.: Multistage fuzzy control using a genetic algorithm. Proc. Sixth World IFSA Congr. (Sao Paolo, Brazil) II, 225–228 (1995)

    Google Scholar 

  47. Kacprzyk, J.: A modified genetic algorithm for multistage control of a fuzzy system. In: Proceedings of Third European Congress on Intelligent Techniques and Soft Computing—EUFIT’95 (Aachen, Germany), vol. 1, pp. 463–466 (1995)

    Google Scholar 

  48. Kacprzyk, J.: Multistage control under fuzziness using genetic algorithms. Control Cybern. 25, 1181–1215 (1996)

    MathSciNet  MATH  Google Scholar 

  49. Kacprzyk, J.: A genetic algorithm for the multistage control of a fuzzy system in a fuzzy environment. Mathw. Soft Comput. I(3), 219–232 (1997)

    MathSciNet  MATH  Google Scholar 

  50. Kacprzyk, J.: Multistage Fuzzy Control. Wiley, Chichester (1997)

    Google Scholar 

  51. Kacprzyk, J.: Multistage control of a stochastic system in a fuzzy environment using a genetic algorithm. Int. J. Intell. Syst. 13, 1011–1023 (1998)

    Article  Google Scholar 

  52. Kacprzyk, J.: Wieloetapowe Sterowanie Rozmyte (in Polish). WNT, Warsaw (2001)

    Google Scholar 

  53. Kacprzyk, J.: Fuzzy dynamic programming: interpolative reasoning for an efficient derivation of optimal control policies. Control Cybern. 42(1), 63–84 (2013)

    MathSciNet  MATH  Google Scholar 

  54. Kacprzyk, J.: Multistage fuzzy control of a stochastic system using a bacterial genetic algorithm. In: Grzegorzewski, P., G“agolewski, M., Hryniewicz, O., Gil, M.A. (eds.) Strengthening Links Between Data Analysis and Soft Computing, pp. 273–284. Springer (2015)

    Google Scholar 

  55. Kacprzyk, J., Esogbue, A.O.: Fuzzy dynamic programming: main developments and applications. Fuzzy Sets Syst. 81, 31–45 (1996)

    Article  MathSciNet  MATH  Google Scholar 

  56. Kacprzyk, J., Iwański, C.: A generalization of discounted multistage decision making and control through fuzzy linguistic quantifiers: an attempt to introduce commonsense knowledge. Int. J. Control 45, 1909–1930 (1987)

    Article  MathSciNet  MATH  Google Scholar 

  57. Kacprzyk, J., Orlovski, S.A. (eds.): Optimization Models Using Fuzzy Sets and Possibility Theory. Reidel, Dordrecht (1987)

    Google Scholar 

  58. Kacprzyk, J., Orlovski, S.A.: Fuzzy optimization and mathematical programming: a brief introduction and survey. In: Kacprzyk, J., Orlovski, S.A. (pod red.) Optimization Models Using Fuzzy Sets and Possibility Theory. Reidel, Dordrecht, str. 50–72 (1987)

    Google Scholar 

  59. Kacprzyk, J., Romero, R.A., Gomide, F.A.C.: Involving objective and subjective aspects in multistage decision making and control under fuzziness: dynamic programming and neural networks. Int. J. Intell. Syst. 14(1), 79–104 (1999)

    Article  MATH  Google Scholar 

  60. Kacprzyk, J., Staniewski, P.: A new approach to the control of stochastic systems in a fuzzy environment, pp. 433–443. Archiwum Automatyki i Telemechaniki, XXV (1980)

    Google Scholar 

  61. Kacprzyk, J., Safteruk, K., Staniewski, P.: On the control of stochastic systems in a fuzzy environment over infinite horizon. Syst. Sci. 7, 121–131 (1981)

    MathSciNet  MATH  Google Scholar 

  62. Kacprzyk, J., Staniewski, P.: Long-term inventory policy-making through fuzzy decision-making models. Fuzzy Sets Syst. 8, 117–132 (1982)

    Article  MATH  Google Scholar 

  63. Kacprzyk, J., Staniewski, P.: Control of a deterministic system in a fuzzy environment over an infinite planning horizon. Fuzzy Sets Syst. 10, 291–298 (1983)

    Google Scholar 

  64. Kacprzyk, J., Straszak, A.: Determination of stable trajectories for integrated regional development using fuzzy decision models. IEEE Trans. Syst. Man Cybern. SMC-14, 310–313 (1984)

    Google Scholar 

  65. Kacprzyk, J., Yager, R.R.: Linguistic quantifiers and belief qualification in fuzzy multicriteria and multistage decision making. Control Cybern. 13, 155–173 (1984)

    Google Scholar 

  66. Kacprzyk, J., Yager, R.R.: “Softer” optimization and control models via fuzzy linguistic quantifiers. Inf. Sci. 34, 157–178 (1984)

    Google Scholar 

  67. Kacprzyk, J., Yager, R.R., Merigó, J.M.: Towards human-centric aggregation via ordered weighted aggregation operators and linguistic data summaries: a new perspective on Zadeh’s inspirations. IEEE Comput. Intell. Mag. 14(1), 16–30 (2019)

    Article  Google Scholar 

  68. Komolov, S.V., Makeev, S.P., G.P. Serov, Shakhnov, I.F.: On the problem of optimal control of a finite automaton with fuzzy constraints and fuzzy goal (in Russian). Kybernetika (Kiev) 6, 30–34 (1979)

    Google Scholar 

  69. Kras“lawski A., G“orak, A., Vogelpohl, A.: Fuzzy dynamic programming in the synthesis of distillation column systems. Comput. Chem. Eng. 13, 611–618 (1989)

    Google Scholar 

  70. Li, L., Lai, K.K.: Fuzzy dynamic programming approach to hybrid multiobjective multistage decision-making problems. Fuzzy Sets Syst. 117(1), 13–25 (2001)

    Article  MathSciNet  MATH  Google Scholar 

  71. Mamdani, E.H., Assilian, S.: An experiment in linguistic synthesis with a fuzzy logic controller. Int. J. Man-Mach. Stud. 7, 1–13 (1975)

    Article  MATH  Google Scholar 

  72. Morin, T.L., Esogbue, A.O.: Some efficient dynamic programming algorithms for the optimal sequencing and scheduling in water supply projects. Water Resour. 7, 479–484 (1971)

    Article  Google Scholar 

  73. Narshima, S.V., Tiwari, R.N., Sastry, K.S.: Dynamic programming approach to multiple objective control problems having deterministic or fuzzy goals. Fuzzy Sets Syst. 57, 195–202 (1993)

    Article  MathSciNet  MATH  Google Scholar 

  74. Nawa, N.E., Furuhashi, T., Hashiyama, T., Uchikawa, Y.: A Study on the discovery of relevant fuzzy rules using pseudo-bacterial genetic algorithm. IEEE Trans. Ind. Electron. 46(6), 1080–1089 (1999)

    Article  Google Scholar 

  75. Nawa, N.E., Furuhashi, T.: Fuzzy system parameters discovery by bacterial evolutionary algorithm. IEEE Trans. Fuzzy Syst. 7(5), 608–616 (1999)

    Article  Google Scholar 

  76. Nguyen, D.P., Phan, V.T.: The fuzzy dynamic programming problems. J. Intell. Fuzzy Syst. 30(3), 1663–1674 (2016)

    Article  MATH  Google Scholar 

  77. Patra, S., Goswami, S.K., Goswami, B.: Fuzzy based fast dynamic programming solution of unit commitment with ramp constraints. Expert Syst. 26(4), 307–319 (2009)

    Article  Google Scholar 

  78. Pedrycz, W.: Fuzzy Control and Fuzzy Systems. Research Studies, 2nd edn. Press/Wiley, Taunton/New York (1993)

    Google Scholar 

  79. Pedrycz, W. (ed.): Fuzzy Modelling: Paradigms and Practice. Kluwer, Boston (1996)

    Google Scholar 

  80. Puterman, M.L.: Markov Decision Processes. Discrete Stochastic Dynamic Programming, Wiley, New York (1994)

    Google Scholar 

  81. Sirbiladze, G.: Fuzzy dynamic programming problem for extremal fuzzy dynamic dystem. In: Lodwick, W.E., Kacprzyk, J. (eds.) Fuzzy Optimization—Recent Advances and Applications, pp. 231–270, Springer, Heidelberg (2010)

    Google Scholar 

  82. Sniedovich, M.: Dynamic Programming. Marcel Dekker, New York (1992)

    Google Scholar 

  83. Sniedovich, M.: Dynamic Programming: Foundations and Principles. Taylor and Francis (2010)

    Google Scholar 

  84. Steele, K, Stefansson, H.O.: Decision theory. In: Stanford Encyclopedia of Philosophy (2015). ISSN 1095-5054 (https://plato.stanford.edu/entries/decision-theory/)

  85. Stein, W.E.: Optimal stopping in a fuzzy environment. Fuzzy Sets Syst. 3, 253–259 (1980)

    Article  MathSciNet  MATH  Google Scholar 

  86. Su, C.C, Hsu, Y.Y.: Fuzzy dynamic programming: An application to unit commitment. IEEE Trans. Power Syst. PS-6, 1231–1237 (1991)

    Google Scholar 

  87. Sugeno, M., Yasukawa, T.: A fuzzy-logic-based approach to qualitative modeling. IEEE Trans. Fuzzy Syst. 1, 7–31 (1993)

    Article  Google Scholar 

  88. Sugianto, L.F., Mielczarski, W.: Dynamic programming application to optimize spare parts inventory. Control Cyberne. 26(1), 111–130 (1997)

    MathSciNet  MATH  Google Scholar 

  89. Tang, Y., He, W., Ni, Z., Zhong, X., Xu, X.: Fuzzy-based goal representation adaptive dynamic programming. IEEE Trans. Fuzzy Syst. 24(5), 1159–1175 (2016)

    Article  Google Scholar 

  90. Weber, K., Sun, Z.: Fuzzy stochastic dynamic programming for marketing decision support. Int. J. Intell. Syst. 15(8), 763–783 (2000)

    Article  MATH  Google Scholar 

  91. Wygralak, M.: Intelligent Counting Under Information Imprecision: Applications to Intelligent Systems and Decision Support. Springer, Heidelberg (2013)

    Google Scholar 

  92. Yager, R.R.: A note on probabilities of fuzzy events. Inf. Sci. 18, 113–129 (1979)

    Article  MathSciNet  MATH  Google Scholar 

  93. Yager, R.R., Filev, D.P.: Foundations of Fuzzy Control. Wiley, New York (1992)

    Google Scholar 

  94. Yager, R.R., Kacprzyk, J. (eds.): The Ordered Weighted Averaging Operators: Theory. Methodology and Applications, Kluwer, Boston, MA (1997)

    Google Scholar 

  95. Yoshida, Y.: Markov chains with a transition possibility measure and fuzzy dynamic programming. Fuzzy Sets Syst. 66, 39–57 (1994)

    Article  MathSciNet  MATH  Google Scholar 

  96. Yoshida, Y. (ed.): Dynamical Aspects in Fuzzy Decision Making. Physica-Verlag, Heidelberg and New York (2001)

    Google Scholar 

  97. Zadeh, L.A.: Fuzzy sets. Inf. Control 8, 338–353 (1965)

    Article  MATH  Google Scholar 

  98. Zadeh, L.A.: Probability measures of fuzzy events. J. Math. Anal. Appl. 23, 421–427 (1968)

    Article  MathSciNet  MATH  Google Scholar 

  99. Zadeh, L.A.: A rationale for fuzzy control. Meas. Control 34, 3–4 (1972)

    Article  Google Scholar 

  100. Zadeh, L.A.: Outline of a new approach to the analysis of complex systems and decision processes. IEEE Trans. Syst. Man Cybern. SMC-2: 28–44 (1973)

    Google Scholar 

  101. Zadeh, L.A.: A computational approach to fuzzy quantifiers in natural languages. Comput. Math. Appl. 9, 149–184 (1983)

    Article  MathSciNet  MATH  Google Scholar 

  102. Zadeh, L.A.: Fuzzy probabilities. Inf. Process. Manag. 20, 363–372 (1986)

    Article  MATH  Google Scholar 

  103. Zadeh, L.A., Kacprzyk, J. (eds.): Fuzzy Logic for the Management of Uncertainty. Wiley, New York (1992)

    Google Scholar 

  104. Zadeh, L.A., Kacprzyk, J. (eds.): Computing with Words in Information/Intelligent Systems. 1. Foundations, 2. Applications. Physica-Verlag, Heidelberg and New York (1999)

    Google Scholar 

  105. Zimmermann, H.-J.: Fuzzy Set Theory and its Applications, 2nd edn. Kluwer, Boston (1991)

    Google Scholar 

Download references

Author information

Authors and Affiliations

Authors

Corresponding author

Correspondence to Janusz Kacprzyk .

Editor information

Editors and Affiliations

Rights and permissions

Reprints and permissions

Copyright information

© 2021 The Editor(s) (if applicable) and The Author(s), under exclusive license to Springer Nature Switzerland AG

About this chapter

Check for updates. Verify currency and authenticity via CrossMark

Cite this chapter

Kacprzyk, J. (2021). Dynamic Programming with Imprecise and Uncertain Information. In: Kulczycki, P., Korbicz, J., Kacprzyk, J. (eds) Automatic Control, Robotics, and Information Processing. Studies in Systems, Decision and Control, vol 296. Springer, Cham. https://doi.org/10.1007/978-3-030-48587-0_13

Download citation

Publish with us

Policies and ethics