برق, مهندسی 1602 بازدید

در آموزش‌های قبلی مجله فرادرس، با کنترل بهینه آشنا شدیم. حل معادلاتی که در رگولاتورهای مرتبه دوم خطی به دست آوردیم، تحت شرایط غیر از حالت ماندگار کار دشواری است. در این موارد می‌توان از روش‌های عددی استفاده کرد. یکی از این روش‌ها، برنامه ریزی پویا (Dynamic Programming) است که می‌توان به راحتی آن را به مسئله گسسته رگولاتور مرتبه دوم خطی (LQR) اعمال کرد. برنامه‌ریزی پویا یک روش کارآمد برای حل انواع خاصی از مسائل بهینه‌سازی است و اولین بار، «ریچارد بلمن» (Richard Bellman) آن را ارائه کرد.

روش برنامه ریزی پویا انعطاف‌پذیری بالایی دارد و می‌توان از آن برای حل مسائل متنوعی استفاده کرد. از این مسائل می‌توان به مسیریابی، صرف کمترین هزینه در جابه‌جایی بین دو شهر، برنامه‌ریزی موجودی، کنترل بهینه و… اشاره کرد. هدف اصلی در برنامه ریزی پویا محاسبه یک تابع هزینه در هر حالت است. وقتی نقشه این تابع هزینه به دست آید، قانون کنترل بهینه را می‌توان از یک حالت به حالت دیگر که هزینه را کمینه می‌کند به دست آورد. مسئله عمومی برنامه‌ریزی پویا را می‌توان به صورت زیر نمایش داد:

$$ \large J ( x [ k ] ) = \underbrace { m i n } _ { u [ k ] } \left [ L ( x [ k ] , u [ k ] , x [ k + 1 ] ) + J ( x [ k + 1 ] ) \right ] $$

در بسیاری از موارد، عبارت بالا به صورت زیر اصلاح می‌شود:

 $$ \large J ( x [ k ] ) = \underbrace { m i n } _ { u [ k ] } \left [ L ( x [ k ] , u [ k ] , x [ k + 1 ] ) + \gamma J ( x [ k + 1 ] ) \right ] $$

عامل $$ \gamma $$ مقادیر آینده هزینه رو به جلو را کاهش می‌دهد. اگر $$ \gamma = 0 $$، آنگاه در الگوریتم، از مقدار هزینه رو به جلو کاملاً چشم‌پوشی می‌شود، در حالی که اگر $$ \gamma$$ بزرگ باشد، مقادیر آینده مورد توجه بیشتری قرار می‌گیرند. وجود $$ \gamma$$ در آن دسته از روش‌های عددی نیز مفید است که در آن‌ها مقدار هزینه رو به جلو را برای شروع نمی‌دانیم و آن را به صورت بازگشتی تخمین می‌زنیم. ضریب $$ \gamma$$ اثرات مفروضات اشتباه اولیه را کاهش می‌دهد.

بنابراین، با استفاده از برنامه ریزی پویا حل مسئله کنترل بهینه به یافتن تابع هزینه رو به جلو تقلیل می‌یابد. این کار را می‌توان با حل رو به عقب از حالت مطلوب تا به همه مقادیر اولیه ممکن انجام داد. وقتی این تابع هزینه رو به جلو را یافتیم، قانون کنترل بهینه به یافتن مسیری می‌انجامد که تابع هزینه را از وضعیت فعلی به یک وضعیت آینده کمینه می‌کند. روش برنامه ریزی پویا یک الگوریتم بسیار عمومی است و می‌توان آن را به مسائل بهینه‌سازی اعمال کرد که در آن‌ها هزینه رو به جلو و هزینه جابه‌جایی از یک حالت به حالت دیگر، جمع شونده است. قبل از پرداختن به جزئیات الگوریتم، یک مثال ساده را بیان می‌کنیم.

مثالی از برنامه ریزی پویا

مسئله یافتن کوتاه‌ترین مسیر بین یک هدف و هر نقطه شروع را روی شبکه شکل زیر در نظر بگیرید. فرض می‌کنیم فقط به سمت چپ، راست، بالا و پایین می‌توانیم حرکت کنیم و هر حرکت یک واحد هزینه دارد.

شکل ۱: تشکیل برنامه‌ریزی پویا 
شکل ۱: تشکیل برنامه‌ریزی پویا

در مثال بالا، محاسبه مسیر بهینه با شروع از شرایط اولیه دشوار است. کار ساده‌تر، محاسبه هزینه رو به جلو با شروع از یک هدف (GOAL) و بازگشت به عقب است. بعد از گام اول، خانه بالا و پایین هدف، هزینه رو به جلویی برابر با ۱ خواهد داشت.

شکل ۲: هزینه رو به جلو بعد از یک گام برگشت به عقب
شکل ۲: هزینه رو به جلو بعد از یک گام برگشت به عقب

می‌توانیم این گام را برای چهار چرخه بعدی انجام دهیم که در آن، هزینه رو به جلوی متناظر با هر خانه در شکل زیر مشخص شده است. توجه کنید که سلول‌های بالا و سمت راستِ خانه متناظر با ۵ امتیاز، هر دو امتیاز ۶ دارند.

شکل ۳:‌ هزینه رو به جلو بعد از یک مرحله بازگشت به عقب
شکل ۳:‌ هزینه رو به جلو بعد از یک مرحله بازگشت به عقب

نقشه هزینه رو به جلو برای موقعیت هدف مطابق شکل زیر است.

شکل ۴: هزینه رو به جلو بعد از دو گام برگشت به عقب
شکل ۴: هزینه رو به جلو بعد از دو گام برگشت به عقب

پس از صرف هزینه لازم برای پیکربندی شبکه هدف، می‌توانیم از هر نقطه‌ای از شبکه شروع کرده و با دنبال کردن مسیری که مجموع عمل (۱) و هزینه رو به جلو را کمینه می‌کند، به هدف برسیم. این الگوریتم، همان برنامه ریزی پویا است.

برنامه ریزی پویا برای کنترل رگولاتور خطی درجه دوم

در این بخش روند بالا برای محاسبه کنترل بهینه را برای یک سیستم خطی به فرم زیر بیان می‌کنیم:

$$ \large X [ k ] = A X [ k – 1 ] + B u [ k – 1 ] $$

می‌خواهیم کنترل‌کننده‌ای برای تابع هزینه زیر طراحی کنیم:

$$ \large J ( x [ k ] ) = \underbrace { m i n } _ { u [ k ] } \left [ \frac { 1 } { 2 } \left ( X [ k ] ^ T Q X [ k ] + u [ k ] ^ T R u [ k ] \right ) + J ( x [ k + 1 ] ) \right ] $$

که عبارتِ

$$ \large J ( x [ N ] ) = \frac { 1 } { 2 } X [ N ] ^ T S _ N X [ N ] , $$

هزینه در انتهای هر چرخه است. برنامه‌ریزی پویا را با گام برداشتن به عقب از $$N$$ شروع می‌کنیم:

$$ \large J ( x [ N – 1 ] ) = \underbrace { m i n } _ { u [ N – 1 ] } \left [ \frac { 1 } { 2 } \left ( X [ N – 1 ] ^ T Q X [ N – 1 ] +u [ N – 1 ] ^ T R u [ N – 1 ] \right ) + J ( x [ N ] ) \right ] $$

از آنجایی که $$ J ( x [ N ] ) = \frac { 1 } { 2 } X [ N ] ^ T S _ N X [ N ] $$، داریم:

$$ \large J ( x [ N ] ) = \frac { 1 } { 2 } \left ( A X [ N – 1 ] + B u [ N – 1 ] \right ) ^ T S _ N ( A X [ N – 1 ] + B u [ N – 1 ] ) , $$

بنابراین:

$$ \large J ( x [ N – 1 ] ) = \underbrace { m i n } _ { u [ N – 1 ] } \left [ \frac { 1 } { 2 } \left ( X [ N – 1 ] ^ T Q X [ N – 1 ] + u [ N – 1 ] ^ T R u [ N – 1 ] \right ) \\ \large + \frac { 1 } { 2 } ( A X [ N – 1 ] + B u [ N – 1 ] ) ^ T S _ N ( A X [ N – 1 ] + B u [ N – 1 ] ) \right ] $$

توجه کنید که $$ x[N-1] $$ به $$ u[N-1] $$ وابسته نیست. بنابراین، هزینه رو به جلوی بهینه را می‌توان با استفاده از مشتقات ماتریسی و مشتق‌گیری نسبت به $$ u[N-1] $$ محاسبه کرد:

$$ \large \frac { \partial J ( x [ N – 1 ] ) } { \partial u [ N – 1 ] } = \left [ u [ N – 1 ] ^ T R + ( A X [ N – 1 ] + B u [ N – 1 ] ) ^ T S _ N B \right ] = 0 $$

از آنجایی که $$R$$ و $$ S _ N $$ متقارن هستند، می‌توان نوشت:

$$ \large R u [ N – 1 ] + B ^ T S _ N ( A X [ N – 1 ] + B u [ N – 1 ] ) = 0 $$

$$ \large u [ N – 1 ] = – ( R + B ^ T S _ N B ) ^ { – 1 } B ^ T S _ N A X [ N – 1 ] $$

کنترل بالا را می‌توان به صورت $$ u[N-1] = – K_{N-1} X[N-1] $$ نوشت که در آن:

$$ \large K _ { N – 1 } = ( R + B ^ T S _ N B ) ^ { – 1 } B ^ T S _ N A X [ N – 1 ] $$

اکنون تابع هزینه $$ J(x[N-1]) $$ را می‌توان به صورت زیر نوشت:

$$ \large J ( x [ N – 1 ] ) = \left [ \frac { 1 } { 2 } \left ( X [ N – 1 ] ^ T Q X [ N – 1 ] + u [ N – 1 ] ^ T R u [ N – 1 ] \right ) + J ( x [ N ] ) \right ] $$

$$ \large J ( x [ N – 1 ] ) = \frac { 1 } { 2 } \left [ \left ( X [ N – 1 ] ^ T Q X [ N – 1 ] + X [ N – 1 ] ^ T K _ { N – 1 } ^ T R K _ { N – 1 } u [ N – 1 ] \right ) \\ \large + X [ N – 1 ] ^ T ( A – B K _ { N – 1 } ) ^ T S _ N ( A – B K _ { N – 1 } X [ N – 1 ] ) \right ] $$

اگر $$ J(x[N-1] ) $$ را به صورت $$ \frac{1}{2} X[N-1]^T S_{N-1} X[N-1] $$ بنویسیم، آنگاه:

$$ \large S _ { N – 1 } = Q + K _ { N – 1 } ^ T R K _ { N – 1 } + ( A – B K _ { N – 1 } ) ^ T S _ N ( A – B K _ { N – 1 } ) $$

عبارت بالا همان معادله ریکاتی است که قبلاً‌ درباره آن صحبت کردیم و در آن $$S$$ به جای $$P$$ قرار گرفته است. اکنون عبارت هزینه رو به جلو بین $$ ( N-2) $$ و $$ ( N-1) $$ برابر است با:

$$ \large J ( x [ N – 2 ] ) = \frac { 1 } { 2 } \underbrace { m i n } _ { u [ N – 2 ] } \left [ \left ( X [ N – 2 ] ^ T Q X [ N – 2 ] + u [ N – 2 ] ^ T R u [ N – 2 ] \right ) + J ( x [ N – 1 ] \right ] $$

که در آن:

$$ \large J ( x [ N – 1 ] ) = \frac { 1 } { 2 } X [ N – 1 ] ^ T S _ { N – 1 } X [ N – 1 ] , $$

برنامه‌ریزی پویا برای سیستم‌های پیوسته شامل گسسته‌سازی هزینه رو به جلو با محاسبه هزینه بین یک بازه و بازه بعدی به عنوان انتگرال هزینه کنترل است.

مثال برنامه ریزی پویا برای LQR

سیستمی با معادله $$ \ddot{x} = u $$ را در نظر بگیرید. می‌خواهیم کنترلی را پیدا کنیم که تابع هزینه زیر را کمینه کند:

$$ \large J = \frac { 1 } { 2 } \int _ { u = 0 } ^ 1 u ^ 2 d t $$

که هزینه نهایی برای کمینه شدن برابر است با:‌

$$ \large J _ f = \frac { 1 } { 2 } ( 1 0 x ^ 2 + 1 0 \dot { x } ^ 2 ) $$

با گسسته‌سازی سیستم، مسئله را به برنامه‌‌ریزی پویا تبدیل می‌کنیم:

$$ \large
\frac { d } { d t } \left [ \begin {array} { c } x _ 1 \\ x _ 2 \end {array} \right ] =\left [ \begin {array} {cc} 1 & d t \\ 0 & 1 \end {array} \right ] \left [ \begin {array} { c } x _ 1 \\ x _ 2 \end {array} \right ] + \left [ \begin {array} { c } 0 \\ d t \end {array} \right ] u $$

اکنون، پارامترهای متناظر با هزینه رو به جلو، $$ S_N = 10I $$، $$ Q = 0 $$ و $$ R = dt $$ هستند. از معادلات زیر برای محاسبه بازگشتی $$S_N$$ استفاده می‌کنیم و از حالت‌ها رو به جلو انتگرال می‌گیریم برای محاسبه کنترل بهینه. در عمل، $$Q = 0 $$ نتایج عددی را ارائه می‌دهد که ناپایدار هستند، بنابراین، از $$ Q = 0.001 dt I $$ استفاده می‌کنیم.

$$ \large K _ { N – 1 } = ( R + B ^ T S _ N B ) ^ { – 1 } B ^ T S _ N A X [ N – 1 ] $$

$$ \large S _ { N – 1 } = Q + K _ { N – 1 } ^ T R K _ { N – 1 } + ( A – B K _ { N – 1 } ) ^ T S _ N ( A – B K _ { N – 1 } ) $$

برنامه ریزی پویا
شکل ۵: نتایج مثال LQR

اگر این مطلب برای شما مفید بوده است، آموزش‌های زیر نیز به شما پیشنهاد می‌شوند:

^^

سید سراج حمیدی (+)

«سید سراج حمیدی» دانش‌آموخته مهندسی برق است. او مدتی در زمینه انرژی‌های تجدیدپذیر فعالیت کرده، و در حال حاضر، آموزش‌های ریاضیات، مهندسی برق و بورس مجله فرادرس را می‌نویسد.

بر اساس رای 5 نفر

آیا این مطلب برای شما مفید بود؟

2 نظر در “برنامه ریزی پویا — از صفر تا صد

  1. با سلام و تشکر از آموزش تون.
    در خط ۲۵ ام از کد متلب تون از دستور dare استفاده شده است، اما توی قسمت help نرم افزار متلب، پیشنهاد داده است که به جای استفاده از دستور dare از دستور idare استفاده بشه. علت اینکه از این دستور استفاده شده چی هست؟
    با تشکر

    1. سلام.
      در راهنمای متلب توصیه شده بعد از نسخه R2019a از دستور “idare” به جای “dare” استفاده شود. در برنامه، دستور “dare” مربوط به نسخی قدیمی‌تر متلب به کار رفته بود که تصحیح شد و به “idare” تغییر یافت. البته استفاده از دستور “dare” تغییری در نتیجه نهایی ایجاد نمی‌کند، اما بهتر است آنچه را که راهنمای متلب پیشنهاد داده به کار ببرید.
      از بازخورد دقیق و سازنده شما بسیار سپاسگزاریم.

نظر شما چیست؟

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *