การเขียนโปรแกรมเชิงพลวัตแบบดิฟเฟอเรนเชียล ( DDP ) เป็น อัลกอริทึม ควบคุมที่เหมาะสมที่สุดใน กลุ่ม การเพิ่มประสิทธิภาพวิถีการเคลื่อนที่ อัลกอริทึมนี้ได้รับการแนะนำในปี 1966 โดยMayne ^{[ 1 ]}และได้รับการวิเคราะห์เพิ่มเติมในหนังสือชื่อเดียวกันของ Jacobson และ Mayne ^{[ 2 ]}อัลกอริทึมนี้ใช้แบบจำลองกำลังสองเฉพาะที่ของพลวัตและฟังก์ชันต้นทุน และแสดงการลู่เข้าแบบกำลังสองมีความเกี่ยวข้องอย่างใกล้ชิดกับวิธีการของนิวตันแบบทีละขั้นตอนของ Pantoja ^{[ 3 ] [ 4 ]}

พลวัต

${\displaystyle \mathbf {x} _{i+1}=\mathbf {f} (\mathbf {x} _{i},\mathbf {u} _{i})}$

1

อธิบายวิวัฒนาการของสถานะโดยพิจารณาจากการควบคุมในแต่ละช่วงเวลาต้นทุนรวมคือผลรวมของต้นทุนการดำเนินงานและต้นทุนสุดท้ายที่เกิดขึ้นเมื่อเริ่มต้นจากสถานะหนึ่งและใช้ลำดับการควบคุมจนกว่าจะถึงช่วงเวลาเป้าหมาย: ${\displaystyle \textstyle \mathbf {x} }$${\displaystyle \mathbf {u} }$${\displaystyle i}$${\displaystyle i+1}$${\displaystyle J_{0}}$${\displaystyle \textstyle \ell }$${\displaystyle \ell _{f}}$${\displaystyle \mathbf {x} }$${\displaystyle \mathbf {U} \equiv \{\mathbf {u} _{0},\mathbf {u} _{1}\dots ,\mathbf {u} _{N-1}\}}$

${\displaystyle J_{0}(\mathbf {x} ,\mathbf {U} )=\sum _{i=0}^{N-1}\ell (\mathbf {x} _{i},\mathbf {u} _{i})+\ell _{f}(\mathbf {x} _{N}),}$

โดยที่และสำหรับกำหนดโดยสมการที่ 1คำตอบของปัญหาการควบคุมที่เหมาะสมที่สุดคือการลดลำดับการควบคุมให้เหลือน้อยที่สุด การเพิ่มประสิทธิภาพวิถีหมายถึงการค้นหาสำหรับค่า ที่เฉพาะเจาะจงแทนที่จะเป็น สำหรับสถานะเริ่มต้นที่เป็นไปได้ทั้งหมด ${\displaystyle \mathbf {x} _{0}\equiv \mathbf {x} }$${\displaystyle \mathbf {x} _{i}}$${\displaystyle i>0}$${\displaystyle \mathbf {U} ^{*}(\mathbf {x} )\equiv \operatorname {argmin} _{\mathbf {U} }J_{0}(\mathbf {x} ,\mathbf {U} ).}$${\displaystyle \mathbf {U} ^{*}(\mathbf {x} )}$${\displaystyle \mathbf {x} _{0}}$

ให้เป็นลำดับควบคุมบางส่วนและกำหนดต้นทุนที่รอการดำเนินการ (cost-to-go)เป็นผลรวมบางส่วนของต้นทุนจากถึง: ${\displaystyle \mathbf {U} _{i}}$${\displaystyle \mathbf {U} _{i}\equiv \{\mathbf {u} _{i},\mathbf {u} _{i+1}\dots ,\mathbf {u} _{N-1}\}}$${\displaystyle J_{i}}$${\displaystyle i}$${\displaystyle N}$

${\displaystyle J_{i}(\mathbf {x} ,\mathbf {U} _{i})=\sum _{j=i}^{N-1}\ell (\mathbf {x} _{j},\mathbf {u} _{j})+\ell _{f}(\mathbf {x} _{N}).}$

ฟังก์ชัน ต้นทุนต่อการดำเนินการหรือฟังก์ชันมูลค่า ที่เหมาะสมที่สุด ณ เวลา t คือต้นทุนต่อการดำเนินการที่กำหนดโดยลำดับการควบคุมที่ทำให้ต้นทุนลดลงต่ำสุด: ${\displaystyle i}$

${\displaystyle V(\mathbf {x} ,i)\equiv \min _{\mathbf {U} _{i}}J_{i}(\mathbf {x} ,\mathbf {U} _{i}).}$

ตามหลักการเขียนโปรแกรมเชิงพลวัต การหาค่าต่ำสุดของลำดับการควบคุมทั้งหมดจะถูกลดทอนให้เหลือเพียงลำดับการหาค่าต่ำสุดของการควบคุมเพียงตัวเดียว โดยดำเนินการย้อนกลับไปตามเวลา: ${\displaystyle V(\mathbf {x} ,N)\equiv \ell _{f}(\mathbf {x} _{N})}$

${\displaystyle V(\mathbf {x} ,i)=\min _{\mathbf {u} }[\ell (\mathbf {x} ,\mathbf {u} )+V(\mathbf {f} (\mathbf {x} ,\mathbf {u} ),i+1)].}$

2

นี่คือสมการของเบลล์แมน

DDP ดำเนินการโดยการทำการส่งผ่านย้อนกลับซ้ำๆ บนวิถีการเคลื่อนที่ที่กำหนดไว้เพื่อสร้างลำดับการควบคุมใหม่ จากนั้นจึงทำการส่งผ่านไปข้างหน้าเพื่อคำนวณและประเมินวิถีการเคลื่อนที่ที่กำหนดไว้ใหม่ เราเริ่มต้นด้วยการส่งผ่านย้อนกลับ หาก

${\displaystyle \ell (\mathbf {x} ,\mathbf {u} )+V(\mathbf {f} (\mathbf {x} ,\mathbf {u} ),i+1)}$

คืออาร์กิวเมนต์ของตัวดำเนินการในสมการที่ 2ให้เป็นการเปลี่ยนแปลงของปริมาณนี้รอบคู่ที่-th : ${\displaystyle \min[\cdot ]}$${\displaystyle Q}$${\displaystyle i}$${\displaystyle (\mathbf {x} ,\mathbf {u} )}$

${\displaystyle {\begin{aligned}Q(\delta \mathbf {x} ,\delta \mathbf {u} )\equiv &\ell (\mathbf {x} +\delta \mathbf {x} ,\mathbf {u} +\delta \mathbf {u} )&&{}+V(\mathbf {f} (\mathbf {x} +\delta \mathbf {x} ,\mathbf {u} +\delta \mathbf {u} ),i+1)\\-&\ell (\mathbf {x} ,\mathbf {u} )&&{}-V(\mathbf {f} (\mathbf {x} ,\mathbf {u} ),i+1)\end{aligned}}}$

และขยายไปสู่ลำดับที่สอง

${\displaystyle \approx {\frac {1}{2}}{\begin{bmatrix}1\\\delta \mathbf {x} \\\delta \mathbf {u} \end{bmatrix}}^{\mathsf {T}}{\begin{bmatrix}0&Q_{\mathbf {x} }^{\mathsf {T}}&Q_{\mathbf {u} }^{\mathsf {T}}\\Q_{\mathbf {x} }&Q_{\mathbf {x} \mathbf {x} }&Q_{\mathbf {x} \mathbf {u} }\\Q_{\mathbf {u} }&Q_{\mathbf {u} \mathbf {x} }&Q_{\mathbf {u} \mathbf {u} }\end{bmatrix}}{\begin{bmatrix}1\\\delta \mathbf {x} \\\delta \mathbf {u} \end{bmatrix}}}$

3

สัญกรณ์ที่ใช้ในที่นี้เป็นรูปแบบหนึ่งของสัญกรณ์ของโมริโมโตะ โดยที่ตัวห้อยแสดงถึงความแตกต่างในโครงสร้างตัวส่วน^{[ 5 ]} การตัดดัชนีออกเพื่อให้อ่านง่ายขึ้น ไพรม์ที่แสดงถึงขั้นตอนเวลาถัดไป สัมประสิทธิ์การขยายคือ ${\displaystyle Q}$${\displaystyle i}$${\displaystyle V'\equiv V(i+1)}$

${\displaystyle {\begin{alignedat}{2}Q_{\mathbf {x} }&=\ell _{\mathbf {x} }+\mathbf {f} _{\mathbf {x} }^{\mathsf {T}}V'_{\mathbf {x} }\\Q_{\mathbf {u} }&=\ell _{\mathbf {u} }+\mathbf {f} _{\mathbf {u} }^{\mathsf {T}}V'_{\mathbf {x} }\\Q_{\mathbf {x} \mathbf {x} }&=\ell _{\mathbf {x} \mathbf {x} }+\mathbf {f} _{\mathbf {x} }^{\mathsf {T}}V'_{\mathbf {x} \mathbf {x} }\mathbf {f} _{\mathbf {x} }+V_{\mathbf {x} }'\cdot \mathbf {f} _{\mathbf {x} \mathbf {x} }\\Q_{\mathbf {u} \mathbf {u} }&=\ell _{\mathbf {u} \mathbf {u} }+\mathbf {f} _{\mathbf {u} }^{\mathsf {T}}V'_{\mathbf {x} \mathbf {x} }\mathbf {f} _{\mathbf {u} }+{V'_{\mathbf {x} }}\cdot \mathbf {f} _{\mathbf {u} \mathbf {u} }\\Q_{\mathbf {u} \mathbf {x} }&=\ell _{\mathbf {u} \mathbf {x} }+\mathbf {f} _{\mathbf {u} }^{\mathsf {T}}V'_{\mathbf {x} \mathbf {x} }\mathbf {f} _{\mathbf {x} }+{V'_{\mathbf {x} }}\cdot \mathbf {f} _{\mathbf {u} \mathbf {x} }.\end{alignedat}}}$

พจน์สุดท้ายในสมการสามสมการสุดท้ายแสดงถึงการหดตัวของเวกเตอร์กับเทนเซอร์ การลดค่าประมาณกำลังสอง(3) ให้เหลือน้อยที่สุด เมื่อเทียบกับเราจะได้ ${\displaystyle \delta \mathbf {u} }$

${\displaystyle {\delta \mathbf {u} }^{*}=\operatorname {argmin} \limits _{\delta \mathbf {u} }Q(\delta \mathbf {x} ,\delta \mathbf {u} )=-Q_{\mathbf {u} \mathbf {u} }^{-1}(Q_{\mathbf {u} }+Q_{\mathbf {u} \mathbf {x} }\delta \mathbf {x} ),}$

4

โดยให้เทอมแบบวงเปิดและเทอมเกนป้อนกลับ เมื่อนำผลลัพธ์กลับไปใส่ใน(3)เราจะได้แบบจำลองกำลังสองของค่า ณ เวลา: ${\displaystyle \mathbf {k} =-Q_{\mathbf {u} \mathbf {u} }^{-1}Q_{\mathbf {u} }}$${\displaystyle \mathbf {K} =-Q_{\mathbf {u} \mathbf {u} }^{-1}Q_{\mathbf {u} \mathbf {x} }}$${\displaystyle i}$

${\displaystyle {\begin{alignedat}{2}\Delta V(i)&=&{}-{\tfrac {1}{2}}Q_{\mathbf {u} }^{T}Q_{\mathbf {u} \mathbf {u} }^{-1}Q_{\mathbf {u} }\\V_{\mathbf {x} }(i)&=Q_{\mathbf {x} }&{}-Q_{\mathbf {xu} }Q_{\mathbf {u} \mathbf {u} }^{-1}Q_{\mathbf {u} }\\V_{\mathbf {x} \mathbf {x} }(i)&=Q_{\mathbf {x} \mathbf {x} }&{}-Q_{\mathbf {x} \mathbf {u} }Q_{\mathbf {u} \mathbf {u} }^{-1}Q_{\mathbf {u} \mathbf {x} }.\end{alignedat}}}$

การคำนวณแบบเรียกซ้ำของแบบจำลองกำลังสองเฉพาะที่และการปรับเปลี่ยนการควบคุมตั้งแต่ลงไปถึงถือเป็นการส่งผ่านย้อนกลับ ดังที่กล่าวมาข้างต้น ค่าจะถูกเริ่มต้นด้วยเมื่อการส่งผ่านย้อนกลับเสร็จสมบูรณ์ การส่งผ่านไปข้างหน้าจะคำนวณวิถีใหม่: ${\displaystyle V(i)}$${\displaystyle \{\mathbf {k} (i),\mathbf {K} (i)\}}$${\displaystyle i=N-1}$${\displaystyle i=1}$${\displaystyle V(\mathbf {x} ,N)\equiv \ell _{f}(\mathbf {x} _{N})}$

${\displaystyle {\begin{aligned}{\hat {\mathbf {x} }}(1)&=\mathbf {x} (1)\\{\hat {\mathbf {u} }}(i)&=\mathbf {u} (i)+\mathbf {k} (i)+\mathbf {K} (i)({\hat {\mathbf {x} }}(i)-\mathbf {x} (i))\\{\hat {\mathbf {x} }}(i+1)&=\mathbf {f} ({\hat {\mathbf {x} }}(i),{\hat {\mathbf {u} }}(i))\end{aligned}}}$

การส่งผ่านย้อนกลับและการส่งผ่านไปข้างหน้าจะถูกทำซ้ำจนกว่าจะบรรจบกัน หากแทนที่เมทริกซ์เฮสเซียนด้วยการประมาณค่าเกาส์-นิวตัน วิธีการนี้จะลดลงเหลือตัวควบคุมเชิงเส้นกำลังสองแบบวนซ้ำ (iLQR) ^{[ 6 ]}${\displaystyle Q_{\mathbf {x} \mathbf {x} },Q_{\mathbf {u} \mathbf {u} },Q_{\mathbf {u} \mathbf {x} },Q_{\mathbf {x} \mathbf {u} }}$

การเขียนโปรแกรมเชิงพลวัตแบบดิฟเฟอเรนเชียลเป็นอัลกอริธึมลำดับที่สองเช่นเดียวกับวิธีของนิวตันดังนั้นจึงใช้ขั้นตอนขนาดใหญ่ในการหาค่าต่ำสุดและมักต้องใช้การปรับค่าและ/หรือการค้นหาเส้นตรงเพื่อให้เกิดการบรรจบกัน^{[ 7 ] [ 8 ]}การปรับค่าในบริบทของ DDP หมายถึงการทำให้แน่ใจว่าเมทริกซ์ในสมการที่ 4เป็นเมทริกซ์บวกแน่นอนการค้นหาเส้นตรงใน DDP เทียบเท่ากับการปรับขนาดการปรับเปลี่ยนการควบคุมแบบวงเปิดด้วยค่าบางค่า ${\displaystyle Q_{\mathbf {u} \mathbf {u} }}$${\displaystyle \mathbf {k} }$${\displaystyle 0<\alpha <1}$

การเขียนโปรแกรมเชิงพลวัตแบบดิฟเฟอเรนเชียลแบบสุ่มตัวอย่าง (SaDDP) เป็นรูปแบบมอนเตคาร์โลของการเขียนโปรแกรมเชิงพลวัตแบบดิฟเฟอเรนเชียล^{[ 9 ] [ 10 ] [ 11 ]}โดยอาศัยการพิจารณาต้นทุนกำลังสองของการเขียนโปรแกรมเชิงพลวัตแบบดิฟเฟอเรนเชียลเป็นพลังงานของการแจกแจงแบบโบลต์ซมันน์ด้วยวิธีนี้ ปริมาณของ DDP สามารถจับคู่กับสถิติของการแจกแจงปกติแบบหลายมิติได้สถิติเหล่านี้สามารถคำนวณใหม่ได้จากวิถีที่สุ่มตัวอย่างโดยไม่ต้องทำการหาอนุพันธ์

การเขียนโปรแกรมเชิงพลวัตแบบดิฟเฟอเรนเชียลที่สุ่มตัวอย่างได้รับการขยายไปสู่การปรับปรุงนโยบายอินทิกรัลเส้นทางด้วยการเขียนโปรแกรมเชิงพลวัตแบบดิฟเฟอเรนเชียล^{[ 12 ]}ซึ่งสร้างการเชื่อมโยงระหว่างการเขียนโปรแกรมเชิงพลวัตแบบดิฟเฟอเรนเชียลและการควบคุมอินทิกรัลเส้นทาง^{[ 13 ]}ซึ่งเป็นกรอบการทำงานของการควบคุมที่เหมาะสมแบบสุ่ม

การเขียนโปรแกรมเชิงพลวัตแบบจุดภายใน (IPDDP) เป็นวิธีการจุดภายในที่เป็นแบบทั่วไปของ DDP ซึ่งสามารถแก้ไขปัญหาการควบคุมที่เหมาะสมที่สุดด้วยสถานะที่ไม่เป็นเชิงเส้นและข้อจำกัดของอินพุต^{[ 14 ]}

• การควบคุมที่เหมาะสมที่สุด

• การใช้งาน DDP ในภาษา Python
• การนำ DDP มาใช้ใน MATLAB

• เฟรมเวิร์กซอฟต์แวร์โอเพนซอร์สacadosนำเสนอการใช้งาน DDP ที่มีประสิทธิภาพและสามารถฝังตัวได้