משוואות בלמן

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש

משוואת בלמןאנגלית: Bellman Equation) הקרויה על שם מפתחה ריצ'רד בלמן היא תנאי הכרחי לאופטימליות בפתרון בעיית בקרה באמצעות תכנון דינמי. משוואות בלמן מתבססות על עקרון האופטימליות של בלמן הגורס באופן רקורסיבי כי מדיניות החלטה אופטימלית הינה אופטימלית ביחס לכל מצב התחלתי והחלטה התחלתית וכמו כן מהווה מדיניות החלטה אופטימלית ביחס לכל מצב והחלטה שנקרים בדרכה.

ניסוח כללי[עריכת קוד מקור | עריכה]

בצורתה הבסיסית, מנוסחת משוואת בלמן עבור תהליך החלטה בזמן בדיד t=0,1,2,... כך שהמצב בזמן t נתון על ידי x_t. פונקציית המעברים של המערכת נתונה כ x_{t+1}=T(x_t,a_t) וקבוצת ההחלטות (הפעולות) שניתן לבצע במצב נתון x_t נתונה כ \Gamma(x_t). כמו כן נתונים לנו הערך המיידי F(x_t,a_t) לביצוע החלטה אפשרית כלשהי במצב מסוים ופקטור היוון 0<\beta<1. משוואת בלמן עבור מדיניות ההחלטה האופטימלית דורשת שיתקיים לכל מצב x_t:

V(x_t) = \max_{a_t \in \Gamma (x_t) } \{ F(x_t,a_t) + \beta V(T(x_t,a_t)) \}

כאשר V(x_t) היא פונקציית הערך הכולל עבור ביצוע החלטות החל ממצב x_t.