التحكم الموزع في تغطية المساحات مع تموضع غير دقيق للروبوتات: دراسات محاكاة وتجارب

الملخص

تدرس هذه المقالة مسألة تغطية المساحات لشبكة من الروبوتات المتحركة ذات تموضع غير دقيق للعوامل. يتمتع كل روبوت بقدرة استشعار شعاعية منتظمة، وتحكمه حركيات من الرتبة الأولى. ويُقسَّم الفضاء المحدب بالاستناد إلى مبدأ فورونوي المضمون (GV)، بحيث تقابل منطقة مسؤولية كل روبوت خلية GV الخاصة به، وهي محدودة بأقواس زائدية. قانون التحكم المقترح موزع، ويتطلب معلومات التموضع الخاصة بجيرانه من نوع GV-Delaunay. وتُعرض دراسات محاكاة وتجارب لإبراز كفاءة قانون التحكم المقترح.

I مقدمة

تغطية منطقة مستوية بواسطة سرب من العوامل الروبوتية مجال بحث نشط يحظى باهتمام كبير وإمكانات واسعة. وتنطوي المهمة على نشر عوامل روبوتية مستقلة ومجهزة بالحساسات داخل منطقة اهتمام لتحقيق تغطية حسية لتلك المنطقة. وتُعد خوارزميات التحكم الموزع خيارا شائعا لهذه المهمة بسبب كفاءتها الحسابية مقارنة بالمتحكمات المركزية، وقدرتها على التكيف آنيا مع التغيرات في سرب الروبوتات، واعتمادها على المعلومات المحلية فقط. ولذلك يمكن تنفيذها على روبوتات ذات قدرة حسابية منخفضة ومرسلات ومستقبلات لاسلكية منخفضة القدرة، إذ لا يُطلب من كل عامل أن يتواصل إلا مع جيرانه. أما الجانب السلبي لمخططات التحكم الموزع فهو أنها تقود إلى أمثليات محلية لدالة الهدف بسبب افتقارها إلى معلومات عن حالة جميع العوامل.

يمكن أن تكون تغطية المساحات ساكنة [1, 2, 3]، وفي هذه الحالة تتقارب العوامل إلى تشكيل نهائي ساكن، أو كاسحة [4, 5, 6]، وفيها تتحرك العوامل باستمرار من أجل تلبية هدف تغطية يتغير باستمرار.

ومن العوامل الأخرى التي يجب أخذها في الحسبان نوع المنطقة المرصودة [7, 8]، ونمط الاستشعار وأداء الحساسات [9, 10, 11, 12]، أو الديناميكيات الخاصة للعوامل [13].

طُرحت مقاربات متنوعة لتغطية المساحات، مثل الاستمثال الموزع [14, 15]، والتحكم التنبئي بالنموذج [16, 17]، ونظرية الألعاب [18]، والتحكم الأمثل [19].

تتضمن جميع أنظمة التموضع لايقينا متأصلا في قياساتها، ولذلك أُنجز عمل مهم لأخذ هذا اللايقين في الحسبان، إما بدمج البيانات [20]، أو بتخطيط مسارات آمنة [21]، أو بالاحتمال المكاني [22]. وتُنشئ مقاربتنا مخطط تقسيم فضائي ملائما بدلا من لايقين تموضع العوامل، إلى جانب قانون تحكم موزع قائم على التدرج.

تدرس هذه المقالة مسألة التغطية المستمرة لمساحة منطقة مستوية محدبة بواسطة شبكة من العوامل المتجانسة المزودة بحساسات متساوية الخواص. ومن أجل أخذ لايقين التموضع في الحسبان، يُفترض أن كل عامل يقع في موضع ما داخل منطقة لايقين تموضع دائرية، ويُنشأ تقسيم فورونوي مضمون [23] لمنطقة الاهتمام انطلاقا من هذه المناطق غير اليقينية. وبعد ذلك يُشتق قانون تحكم موزع بالاستناد إلى التقسيم المذكور بحيث يزداد هدف التغطية على نحو رتيب. ونظرا إلى تعقيد ذلك القانون، يُقترح قانون دون أمثل وتُقارن القاعدتان عن طريق المحاكاة. إضافة إلى ذلك، يُقيّم قانون التحكم دون الأمثل بتجربتين باستخدام روبوتات ذات قيادة تفاضلية. وتمثل هذه المقالة امتدادا للعمل [24] الذي لم يتضمن نتائج محاكاة لقانون التحكم الأمثل وافتقر إلى التقييم التجريبي لقانون التحكم دون الأمثل.

تنظيم المقالة كما يأتي. تُعرض التمهيدات الرياضية المطلوبة في القسم II. وتُفحص تقسيمات الفضاء من نوع فورونوي وفورونوي المضمون في القسم III. ويحتوي القسم IV على تعريف هدف التغطية واشتقاق قانون التحكم القائم على الصعود التدرجي الذي يعظمه. كما يتضمن قانون التحكم دون الأمثل المقترح. وتُعرض دراسات المحاكاة في القسم V لمقارنة قانوني التحكم وتقييمهما. أما القسم VI فيتضمن نتائج تجريبية من تنفيذ قانون التحكم دون الأمثل، وتليه ملاحظات ختامية.

II تمهيدات رياضية

لنفترض وجود منطقة مدمجة محدبة $\mathrm{\Omega }\in {ℝ}^2$ قيد المراقبة، وشبكة مؤلفة من $n$ عوامل متحركة متطابقة عديمة الأبعاد (عقد). وتخضع ديناميكيات كل عامل للعلاقة

$${\dot{q}}_i=u_i,u_i\in {ℝ}^2,q_i\in \mathrm{\Omega },i\in I_n$$ (1)

حيث إن $u_i$ هو مدخل التحكم لكل عامل، و$I_n=\{1,2,\mathrm{\dots },n\}$.

لا تُعرف مواضع العوامل بدقة، ومن ثم فإن لكل عامل في الحالة العامة لايقينا تموضعيا بمقدار مختلف. ونفترض أن حدا أعلى $r_i^u$ للايقين التموضعي لكل عامل معلوم، ومن ثم فإن مركزه يقع داخل قرص

$$C_i^u(q_i,r_i^u)=\{q\in \mathrm{\Omega }:\Vert q-q_i\Vert \le r_i^u\},i\in I_n$$ (2)

حيث إن $\parallel \cdot \parallel$ هو المقياس الإقليدي، و$q_i$ موضع العامل كما تُبلّغ عنه معدات التموضع الخاصة به.

جميع العوامل مزودة بحساسات كلية الاتجاهات متطابقة ذات آثار استشعار دائرية، وبناء على ذلك يمكن تعريف المنطقة المستشعرة لكل عامل على النحو

$$C_i^s(q_i,r^s)=\{q\in \mathrm{\Omega }:\Vert q-q_i\Vert \le r^s\},i\in I_n$$

حيث إن $r^s$ هو المدى المشترك للحساسات.

ونعرّف أيضا، لكل عامل، «منطقة مستشعرة مضمونة» (GSR) بوصفها المنطقة التي يستشعرها العامل لجميع مواضعه الممكنة داخل $C_i^u$. وتُعرّف مناطق GSR كما يأتي

$$C_i^{gs}(C_i^u,C_i^s)=\left\{\bigcap _{q_i}{C}_i^s(q_i,r^s),\forall q_i\in C_i^u\right\},i\in I_n$$

وبما أن $C_i^u$ و$C_i^s$ قرصان، يمكن تبسيط التعبير السابق أكثر إلى

$$C_i^{gs}(q_i,r^s-r_i^u)=\{q\in \mathrm{\Omega }:\Vert q-q_i\Vert \le r^s-r_i^u\},i\in I_n,$$ (3)

شريطة أن $r^s\ge r_i^u$.

عندما يكون موضع عامل ما معلوما بدقة، أي عندما $r_i^u=0$، تكون GSR الخاصة به مكافئة لمنطقته المستشعرة، أما عندما يكون لايقين تموضع العامل كبيرا جدا مقارنة بقدراته الاستشعارية، أي عندما $r_i^u>r^s$، فإن $C_i^{gs}=\mathrm{\varnothing }$.

III تقسيم الفضاء

تسند معظم مخططات تغطية المساحات الموزعة منطقة مسؤولية إلى كل عامل بالاستناد إلى معلومات من عوامله المجاورة. ثم يكون كل عامل مسؤولا عن تعظيم التغطية حصرا في منطقة مسؤوليته. وأكثر مخططات التقسيم شيوعا هو تقسيم فورونوي، الموصوف في القسم III-A. غير أن هذه المقالة، بسبب لايقين تموضع العوامل، تستخدم مخطط فورونوي المضمون الموصوف في القسم III-B لإسناد مناطق المسؤولية.

III-A مخطط فورونوي

يُعرّف مخطط فورونوي لمجموعة من النقاط $Q=\{q_1,q_2\mathrm{\dots }{q}_n\},q_i\in \mathrm{\Omega }$ كما يأتي

$$V_i=\{q\in \mathrm{\Omega }:\Vert q-q_i\Vert \le \Vert q-q_j\Vert ,\forall j\in I_n,j\ne i\},i\in I_n.$$

وتسمى كل $V_i\subset \mathrm{\Omega }$ خلية فورونوي للعقدة $i$. ويُعرض مخطط فورونوي لعدد 6 من النقاط المقيدة ضمن مجموعة جزئية $\mathrm{\Omega }$ من ${ℝ}^2$ في الشكل 1 (يسارا)، حيث تظهر حدود الخلايا باللون الأزرق.

من المهم ملاحظة أن مخطط فورونوي يشكل تبليطا كاملا لـ $\mathrm{\Omega }$، أي إن ${\bigcup }_{i\in I_n}{V}_i=\mathrm{\Omega }$.

ومن الخصائص المفيدة الأخرى لمخططات فورونوي ازدواجيتها مع تثليثات ديلوني. لنعرّف جيران ديلوني لنقطة $q_i$ كما يأتي

$$N_i=\{j\in I_n,j\ne i:V_i\cap V_j\ne \mathrm{\varnothing }\},i\in I_n,$$ (4)

عند إنشاء خلية فورونوي لنقطة $q_i$، لا يلزم إلا أخذ جيران ديلوني لها في الحسبان، مما يبسط تعريف خلية فورونوي الخاصة بها إلى

$$V_i=\{q\in \mathrm{\Omega }:\Vert q-q_i\Vert \le \Vert q-q_j\Vert ,\forall j\in N_i\},i\in I_n.$$

وباستخدام هذه الخاصية، يمكن إنشاء مخطط فورونوي بالعثور أولا على تثليث ديلوني للنقاط الداخلة، ثم لكل خلية $V_i$ بإيجاد تقاطع أنصاف المستويات المعرفة بالنقطة $q_i$ وبجميع النقاط في $N_i$.

Figure 1: مخطط فورونوي (يسارا) لعدد 6 من العقد عديمة الأبعاد، مع مخطط فورونوي المضمون المكافئ له (يمينا) في حالة الأقراص (المتمركزة حول تلك النقاط).

III-B مخطط فورونوي المضمون

يُعرّف مخطط فورونوي المضمون (GV) لمجموعة من المناطق غير اليقينية $D=\{D_1,D_2,\mathrm{\dots },D_n\},D_i\subset \mathrm{\Omega }$. وتحتوي كل منطقة غير يقينية $D_i$ على جميع المواضع الممكنة لنقطة $q_i\in {ℝ}^2$ لا يمكن قياس تموضعها بدقة. ومن ثم يُعرّف مخطط GV كما يأتي

$V_i^g$ $=$ $\{q\in \mathrm{\Omega }:\max \parallel q-q_i\parallel \le \min \parallel q-q_j\parallel$ (5)

$\forall j\in I_n,j\ne i,q_i\in D_i,q_j\in D_j\},i\in I{}_n.$

وهناك تعريف مكافئ لمخطط GV كما يأتي

$$V_i^g=\bigcap _{i\in I_n}{H}_{ij}$$

حيث

$$H_{ij}=\{q\in \mathrm{\Omega }:\max \Vert q-q_i\Vert \le \min \Vert q-q_j\Vert ,\forall q_i\in D_i,\forall q_j\in D_j\}.$$

هذا التعريف مماثل لإنشاء خلية فورونوي الكلاسيكية بطريقة تقاطع أنصاف المستويات الموصوفة سابقا، مع اختلاف أن المناطق التي يُؤخذ تقاطعها لم تعد أنصاف مستويات.

وبناء على ذلك، تحتوي كل خلية $V{i}^g$ على النقاط في المستوى الأقرب إلى النقطة المقابلة $q_i$ من المنطقة $D_i$ لجميع التشكيلات الممكنة للنقاط غير اليقينية. ويُعرض مخطط فورونوي مضمون لعدد 6 من المناطق المقيدة ضمن مجموعة جزئية $\mathrm{\Omega }$ من ${ℝ}^2$ في الشكل 1 (يمينا)، حيث تظهر حدود الخلايا كذلك باللون الأزرق.

ملاحظة 1.

خلافا لمخطط فورونوي الكلاسيكي، لا يشكل مخطط فورونوي المضمون تبليطا لـ $\mathrm{\Omega }$، إذ إن ${\bigcup }_{i\in I_n}{V}_i^g\subset \mathrm{\Omega }$. ونعرّف منطقة محايدة $𝒪$ بحيث إن $𝒪\cup {\bigcup }_{i\in I_n}{V}_i^g=\mathrm{\Omega }$.

على نحو مماثل لمخطط فورونوي، يمكننا تعريف جيران ديلوني المضمونين $N_i^g$ لمنطقة $D_i$ بحيث لا يلزم، من أجل إنشاء $V_i^g$، إلا أخذ المناطق في $N_i^g$ في الحسبان. وبذلك يُعرّف جيران ديلوني المضمونون كما يأتي

$$N_i^g=\{j\in I_n,j\ne i:\partial H_{ij}\cap \partial V_i^g\ne \mathrm{\varnothing }\}.$$ (6)

بعد تعريف جيران ديلوني المضمونين، يمكن تبسيط تعريف مخطط GV إلى

$$V_i^g=\bigcup _{i\in N_i}{H}_{ij}.$$ (7)

من المهم ملاحظة أنه عندما تتداخل منطقتان غير يقينيتين أو أكثر، لا تُسند إلى أي منها خلايا GV. وبالإضافة إلى ذلك، إذا تنكست المناطق غير اليقينية إلى نقاط، فإن مخطط GV يتقارب إلى مخطط فورونوي الكلاسيكي.

III-C مخطط فورونوي المضمون للأقراص

يُفحص مخطط GV في الحالة التي تكون فيها المناطق غير اليقينية $D_i$ أقراصا $C_i^u$ كما عُرّفت في المعادلة (2). وفي هذه الحالة، بُين أن $H_{ij}$ مناطق في المستوى محدودة بفروع زائدية. ولأي عقدتين $i$ و$j$، تكون $\partial H_{ij}$ و$\partial H_{ji}$ الفرعين الاثنين لقطع زائد بؤرتاه عند $q_i$ و$q_j$ ومحوره شبه الأكبر مساو لمجموع نصفي قطري $C_i^u$ و$C_j^u$. ويمكن العثور على المعادلة البارامترية لهذين الفرعين الزائديين في الملحق.

اعتماد خلايا GV لقرصين على مسافة مركزيهما $d_{ij}=d(q_i,q_j)$ يكون كما يأتي. عندما تتداخل القرصان $C_i^u,C_j^u$، تكون الخليتان $V_i^g,V_j^g$ فارغتين كما في الشكل 2 (أ). وإذا كانت الأقراص تمثل المواضع الممكنة للعوامل، فإن هذا تشكيل غير مرغوب فيه لأنه يمكن أن يؤدي إلى تصادمات. وعندما يكون القرصان $C_i^u,C_j^u$ متماسين خارجيا (أي $d(q_i,q_j)=r_i^u+r_j^u$)، تكون الخلايا الناتجة أنصاف مستقيمات تبدأ من مركزي القرصين $q_i,q_j$ وتمتد على امتداد اتجاه $q_i{q}_j$ كما يظهر في الشكل 2 (ب). وعندما يكون القرصان منفصلين، تكون خلايا GV محدودة بفرعي قطع زائد. ومع ازدياد $d_{ij}$ أكثر، تزداد لا مركزية القطع الزائد وتزداد مسافة مركزي القرصين عن رأسي القطع الزائد (وهما نقطتا القطع الزائد الأقرب إلى مركزه)، كما يظهر في الشكل 2 (ج)، (د). وتبقى المسافة بين رأسي القطع الزائد ثابتة عند $r_i+r_j$ مع ازدياد $d_{ij}$.

تعتمد خلايا GV لقرصين أيضا على مجموع نصفي قطريهما $r_i+r_j$ كما يظهر في الشكل 3. فمع تناقص $r_i+r_j$، تزداد لا مركزية القطع الزائد، ويكون الأثر على الخلايا مماثلا لما يحدث إذا ازدادت المسافة بين مركزي القرصين، كما شُرح سابقا. وعندما $r_i+r_j=0$، تكون خلايا GV هي خلايا فورونوي الكلاسيكية.

(a)

(b)

(c)

(d)

Figure 2: اعتماد خلايا GV على $\Vert q_i-q_j\Vert$.

Figure 3: اعتماد خلايا GV على $r_i+r_j$.

بُين أيضا أن جيران ديلوني المضمونين $N_i^g$ هم مجموعة جزئية من جيران ديلوني الكلاسيكيين لمراكز الأقراص غير اليقينية. وتكون المجموعتان $N_i$ و$N_i^g$ متساويتين عندما يُنشأ مخطط GV للمستوى كله، غير أنه عندما يكون مخطط GV مقيدا ضمن مجموعة جزئية $\mathrm{\Omega }$ من المستوى، يمكن أن تكون $N_i^g$ مجموعة جزئية من $N_i$. وتظهر مثل هذه الحالة في الشكل 1، حيث تكون العقدتان 1 و5 جارتين وفق ديلوني وليستا جارتين وفق ديلوني المضمون. وبهذه الطريقة يمكن إنشاء مخطط GV للأقراص بطريقة مشابهة لمخطط فورونوي الكلاسيكي. أولا، يُنشأ تثليث ديلوني لمراكز الأقراص، ثم تُنشأ كل خلية $V_i^g$ بأخذ تقاطع المناطق المحدودة بالأقواس الزائدية $H_{ij}\forall j\in N_i^g$. وتُعرض هذه العملية في الشكل 4.

Figure 4: إنشاء خلية GV بطريقة تقاطع المناطق الزائدية.

من المفيد تعريف خلايا فورونوي ذات الاستشعار المضمون (GSV) كما يأتي

$$V_i^{gs}=V_i^g\cap C_i^{gs},i\in I_n,$$ (8)

وهي أجزاء خلايا GV المضمون استشعارها بواسطة عقدها المقابلة. ويمكن إثبات أنه بما أن خلايا GV متمايزة، فإن خلايا GSV مناطق متمايزة أيضا.

IV صياغة المسألة - قانون التحكم الموزع

بأخذ تقسيم GV للفضاء في الحسبان، يُبنى معيار تغطية المساحات الآتي

$$\mathscr{H}={\int }_{{\bigcup }_{i\in I_n}{V}_i^{gs}}\varphi \left(q\right)dq=\sum _{i\in I_n}{\int }_{V_i^{gs}}\varphi \left(q\right)dq=\sum _{i\in I_n}{\mathscr{H}}_i,$$ (9)

حيث ترتبط الدالة $\varphi :{ℝ}^2\to {ℝ}_{+}$ بالمعرفة القبلية بأهمية نقطة $q\in \mathrm{\Omega }$، مبينة احتمال وقوع حدث عند $q$ في سيناريو تغطية. ويعبر هذا المعيار عن المساحة المضمونة الأقرب إلى العقد والمغطاة بها.

يُصمم قانون تحكم موزع لتعظيم معيار التغطية (9) مع أخذ نمط الاستشعار المضمون للعقد (3) وتقسيم GV (7) في الحسبان. ويُبين أن قانون التحكم هذا يؤدي إلى زيادة رتيبة في معيار التغطية.

مبرهنة 1.

لشبكة من العقد المتحركة ذات تموضع غير يقيني كما في (2)، وأداء استشعار شعاعي منتظم محدود المدى كما في (3)، ومحكومة بالحركيات الفردية للعامل الموصوفة في (1)، ومع تقسيم GV لـ $\mathrm{\Omega }$ المعرّف في (7)، فإن مخطط التنسيق

$u_i$ $=$ ${\alpha }_i{\displaystyle {\int }_{\partial V_i^{gs}\cap \partial C_i^{gs}}}{n}_i\varphi dq+$ (10)

${\alpha }_i{\displaystyle \sum _{j\in N_i^g}}\left[{\displaystyle {\int }_{\partial V_i^{gs}\cap \partial H_{ij}}}{\upsilon }_i^i{n}_i\varphi dq+{\displaystyle {\int }_{\partial V_j^{gs}\cap \partial H_{ji}}}{\upsilon }_j^i{n}_j\varphi dq\right]$

حيث إن $n_i$ هو الناظم الواحدي الخارجي على $\partial V_i^{gs}$، و${\alpha }_i$ ثابت موجب، يعظم معيار الأداء (9) على امتداد مسارات العقد بطريقة رتيبة، مؤديا إلى تشكيل أمثل محليا من حيث المساحة للشبكة.

Proof.

لضمان الزيادة الرتيبة لمعيار التغطية (9)، نقيم مشتقته الزمنية

$$\frac{\partial \mathscr{H}}{\partial t}=\sum _{i\in I_n}\frac{\partial {\mathscr{H}}_i}{\partial q_i}{\dot{q}}_i=\sum _{i\in I_n}\frac{\partial {\mathscr{H}}_i}{\partial q_i}{u}_i$$ (11)

وباستخدام قانون التحكم القائم على التدرج

$$u_i=\frac{\partial {\mathscr{H}}_i}{\partial q_i},i\in I_n,$$ (12)

تتحقق زيادة رتيبة في $\mathscr{H}$.

نقيّم الآن المشتقة الجزئية لـ $\mathscr{H}$ بالنسبة إلى $q_i$ كما يأتي

$$\frac{\partial \mathscr{H}}{\partial q_i}=\frac{\partial }{\partial q_i}{\int }_{V_i^{gs}}\varphi 𝑑q+\sum _{j\in N_i^g}\frac{\partial }{\partial q_i}{\int }_{V_j^{gs}}\varphi 𝑑q.$$

وبالنظر إلى حد الجمع الثاني، فإن حركة متناهية الصغر لـ $q_i$ لا يمكن أن تؤثر في $\partial V_j^{gs}$ إلا عند $\partial V_j^{gs}\cap \partial 𝒪$، حيث إن $𝒪$ هي المنطقة المحايدة المعرفة في الملاحظة 1، لأن كلا فرعي القطع الزائد يتأثران بتغير إحدى البؤرتين. إضافة إلى ذلك، لا يؤخذ في الجمع إلا جيران ديلوني المضمونون (6) لـ $i$، وهي خاصية رئيسية لتقسيم GV. لذلك يمكن كتابة التعبير السابق بواسطة قاعدة لايبنتز التكاملية المعممة [25] (بتحويل التكاملات السطحية إلى تكاملات خطية) على الصورة

$$\frac{\partial \mathscr{H}}{\partial q_i}={\int }_{\partial V_i^{gs}}{\upsilon }_i^i{n}_i\varphi 𝑑q+\sum _{j\in N_i^g}{\int }_{\partial V_j^{gs}\cap \partial 𝒪}{\upsilon }_j^i{n}_j\varphi 𝑑q,$$

حيث تمثل ${\upsilon }_i^i,{\upsilon }_j^i$ مصفوفتي جاكوبي المنقولتين بالنسبة إلى $q_i$ للنقطتين $q\in \partial V_i^{gs}$ و$q\in \partial V_j^{gs}$، على الترتيب، أي

$${\upsilon }_j^i\left(q\right)\stackrel{\mathrm{△}}{=}{\frac{\partial q}{\partial q_i}}^T,q\in \partial V_j^{gs},i,j\in I_n.$$ (13)

ويمكن تفكيك الحد $\partial {\tilde{V}}_i^{gs}$ إلى مجموعات متمايزة كما يأتي

$$\partial V_i^{gs}=\left\{\partial V_i^{gs}\cap \partial \mathrm{\Omega }\right\}\cup \left\{\partial V_i^{gs}\cap \partial C_i^{gs}\right\}\cup \left\{\partial V_i^{gs}\cap \partial 𝒪\right\}.$$ (14)

تمثل هذه المجموعات أجزاء $\partial V_i^{gs}$ الواقعة على حد $\mathrm{\Omega }$، وحد منطقة الاستشعار المضمونة للعقدة، وحد المنطقة المحايدة غير المسندة من $\mathrm{\Omega }$، على الترتيب. ويظهر هذا التفكيك في الشكل 5، حيث يظهر $\partial V_i^{gs}\cap \partial \mathrm{\Omega }$ بالأخضر، و$\partial V_i^{gs}\cap \partial C_i^{gs}$ بالأحمر المتصل، و$\partial V_i^{gs}\cap \partial 𝒪$ بالأزرق المتصل.

Figure 5: تفكيك $\partial V_i^{gs}$ إلى مجموعات متمايزة (أحمر متصل، وأخضر، وأزرق).

ومن ثم يمكن كتابة $\frac{\partial \mathscr{H}}{\partial q_i}$ على الصورة

${\displaystyle \frac{\partial \mathscr{H}}{\partial q_i}}$ $=$ ${\displaystyle {\int }_{\partial V_i^{gs}\cap \partial \mathrm{\Omega }}}{\upsilon }_i^i{n}_i\varphi dq+{\displaystyle {\int }_{\partial V_i^{gs}\cap \partial C_i^{gs}}}{\upsilon }_i^i{n}_i\varphi dq+$ (15)

${\displaystyle {\int }_{\partial V_i^{gs}\cap \partial 𝒪}}{\upsilon }_i^i{n}_i\varphi dq+{\displaystyle \sum _{j\in N_i^g}}{\displaystyle {\int }_{\partial V_j^{gs}\cap \partial 𝒪}}{\upsilon }_j^i{n}_j\varphi dq.$

ومن الواضح أن ${\upsilon }_i^i=0$ عند $q\in \partial V_i^{gs}\cap \mathrm{\Omega }$، لأن جميع $q\in \partial \mathrm{\Omega }$ تبقى غير متغيرة بفعل الحركات المتناهية الصغر لـ $q_i$، مع افتراض عدم تغير البيئة. وبالنظر إلى التكامل الثاني، فإنه لأي نقطة $q\in \partial {\tilde{V}}_i^{gs}\cap \partial C_i^{gs}$ تتحقق العلاقة ${\upsilon }_i^i\left(q\right)={𝕀}_2$، حيث تمثل $𝕀$ مصفوفة الهوية، لأنها تنتقل في اتجاه حركة $q_i$ نفسه وبالمعدل نفسه. أما فيما يتعلق بالمجموعتين $\partial V_i^{gs}\cap \partial 𝒪$ و$\partial V_j^{gs}\cap \partial 𝒪,j\in N_i^g$، فيمكن دمجهما في أزواج باستخدام الفرعين الزائديين الأيسر والأيمن، كما قُدما في تقسيم GV (7)، على النحو الآتي

${\displaystyle {\int }_{\partial V_i^{gs}\cap \partial 𝒪}}{\upsilon }_i^i{n}_i\varphi dq+{\displaystyle \sum _{j\in N_i^g}}{\displaystyle {\int }_{\partial V_j^{gs}\cap \partial 𝒪}}{\upsilon }_j^i{n}_j\varphi dq=$

${\displaystyle \sum _{j\in N_i^g}}\left[{\displaystyle {\int }_{\partial V_i^{gs}\cap \partial H_{ij}}}{\upsilon }_i^i{n}_i\varphi dq+{\displaystyle {\int }_{\partial V_j^{gs}\cap \partial H_{ji}}}{\upsilon }_j^i{n}_j\varphi dq\right].$ (16)

غير أنه لأي جارين وفق ديلوني $i,j$ يمكن ملاحظة أن

• الفرعان الزائديان $\partial H_{ij}$ و$\partial H_{ji}$ متناظران بالنسبة إلى المنصف العمودي لـ $q_i,q_j$، وتحكمهما مجموعة المعادلات البارامترية نفسها (الفرع الأيسر والفرع الأيمن).

• المتجهات $n_j$ هي صور مرآتية للمتجهات المقابلة $n_i$ بالنسبة إلى المنصف العمودي لـ $q_i,q_j$.

بأخذ ما سبق في الحسبان، يمكن كتابة $\frac{\partial \mathscr{H}}{\partial q_i}$ كما يأتي

${\displaystyle \frac{\partial \mathscr{H}}{\partial q_i}}$ $=$ ${\displaystyle {\int }_{\partial V_i^{gs}\cap \partial C_i^{gs}}}{n}_i\varphi dq+$ (17)

${\displaystyle \sum _{j\in N_i^g}}\left[{\displaystyle {\int }_{\partial V_i^{gs}\cap \partial H_{ij}}}{\upsilon }_i^i{n}_i\varphi dq+{\displaystyle {\int }_{\partial V_j^{gs}\cap \partial H_{ji}}}{\upsilon }_j^i{n}_j\varphi dq\right].$

يمكن تقييم متجهات الناظم الواحدية $n_i,n_j$ ومصفوفات جاكوبي ${\upsilon }_i^i,{\upsilon }_j^i$ في الجزء الثاني من (17) باستخدام التمثيلات البارامترية للمجموعات التي يجري التكامل عليها. وهذه المجموعات أجزاء من الفرع الأيسر ($\partial H_{ij}$) والفرع الأيمن ($\partial H_{ji}$) للقطع الزائد الذي يسند الفضاء بين عقدتين اعتباطيتين $i,j$. ويتطلب الحد الثاني من المجموع في (17) معرفة جميع العقد في ${\bigcup }_{j\in N_i^g}{N}_j^g\subseteq I_n$، ولذلك يكون قانون التحكم موزعا.

تفكيك المجموعة $\partial V_i^{gs}\cap \partial 𝒪$ للعقدة $i$ إلى أقواس زائدية متمايزة فيما بينها $\partial V_i^{gs}\cap \partial H_{ij}$ و$\partial V_i^{gs}\cap \partial H_{ik}$ يظهر في الشكل 6. كما يعرض الشكل 6 مجالات التكامل الأخرى المستخدمة في (17)، وهي $\partial V_i^{gs}\cap \partial C_i^{gs}$ و$\partial V_j^{gs}\cap \partial H_{ji}$ و$\partial V_k^{gs}\cap \partial H_{ki}$.

Figure 6: مجالات التكامل في قانون التحكم (10).

يقود القانون المقترح (10) إلى جريان تدرجي لـ $\mathscr{H}$ على امتداد مسارات العقد، في حين تزداد $\mathscr{H}$ رتيبا، لأن

$$\frac{d\mathscr{H}}{dt}=\sum _{i\in I_n}\frac{\partial \mathscr{H}}{\partial q_i}\cdot {\dot{q}}_i=\sum _{i\in I_n}{\Vert u_i\Vert }^2\ge 0.$$

∎

ملاحظة 2.

لا يتضح مباشرة من قانون التحكم (10) ما المعلومات التي تحتاجها العقدة $i$ لتنفيذه. فالتكاملان على $\partial V_i^{gs}\cap \partial C_i^{gs}$ و$\partial V_i^{gs}\cap \partial H_{ij}$ يتطلبان معرفة جيران ديلوني المضمونين $N_i^g$ من أجل حساب $V_i^{gs}$ و$H_{ij}$. غير أن التكامل على $\partial V_j^{gs}\cap \partial H_{ji}$ يتطلب معرفة الخلية كاملة $V_j^{gs}$ للعقدة $i$، ومن ثم يتطلب معلومات من جيران ديلوني المضمونين $N_j^g$ للعقدة $j$. لذلك تحتاج العقدة $i$ إلى معلومات من جميع العقد في

$${\tilde{N}}_i^g=\bigcup _{j\in N_i^g}{N}_j^g,$$

وهي جيران ديلوني المضمونون لجميع جيران ديلوني المضمونين للعقدة $i$.

IV-A تقييد العقد داخل $\mathrm{\Omega }$

عند استخدام قانون التحكم هذا، قد يقع جزء من منطقة لايقين التموضع لبعض العقد خارج المنطقة $\mathrm{\Omega }$، أي إن $C_i^u\cap \mathrm{\Omega }\ne C_i^u$ لعقدة ما $i$. ونتيجة لذلك، قد يكون من الممكن أن تكون تلك العقدة خارج المنطقة $\mathrm{\Omega }$ نظرا إلى أنها قد تكون في أي مكان ضمن $C_i^u$.

ولمنع هذه الحالة، سيُستخدم، بدلا من $\mathrm{\Omega }$، مجموعة جزئية ${\mathrm{\Omega }}_i^s\subseteq \mathrm{\Omega }$، تكون في الحالة العامة مختلفة لكل عقدة، إذ يُسمح لاختلاف أنصاف أقطار اللايقين بينها. وتُحسب هذه المجموعة الجزئية بوصفها فرق مينكوفسكي بين $\mathrm{\Omega }$ والقرص $C\left(r_i^u\right)=\{q\in \mathrm{\Omega }:\Vert q\Vert \le r_i^u\}$.

$${\mathrm{\Omega }}_i^s=\left\{q\in \mathrm{\Omega }\right|q+C(r_i^u)\subseteq \mathrm{\Omega }\},i\in I_n.$$

وبذلك، من خلال تقييد مركز كل قرص لايقين $q_i$ داخل ${\mathrm{\Omega }}_i^s$، يُضمن ألا يقع أي جزء من قرص اللايقين خارج $\mathrm{\Omega }$ على الإطلاق. ويتحقق ذلك بإسقاط مدخل التحكم بالسرعة $u_i$ على $\partial {\mathrm{\Omega }}_i^s$. ولا يلزم هذا إلا إذا $q_i\in \partial {\mathrm{\Omega }}_i^s$ وكان مدخل التحكم $u_i$ يشير نحو خارج ${\mathrm{\Omega }}_i^s$. ونتيجة لذلك يصبح قانون التحكم

(18)

حيث إن $ϵ$ ثابت موجب متناه في الصغر.

IV-B قانون التحكم دون الأمثل

بسبب التعقيد العالي للتكاملات على $H_{ij}$ و$H_{ji}$ في قانون التحكم (10)، وكمية المعلومات الكبيرة المطلوبة لتنفيذه كما هو موصوف في الملاحظة 2، فضلا عن المشكلات الموصوفة في القسم IV-A، تُقترح نسخة مبسطة من قانون التحكم.

حدس 1.

قانون التحكم دون الأمثل ذو الكفاءة الحسابية

$$u_i={\alpha }_i{\int }_{\partial V_i^{gs}\cap \partial C_i^{gs}}{n}_i\varphi dq$$ (19)

يقود العقد إلى مسارات دون مثلى.

يُستخدم تعزيز قانون التحكم الموصوف في القسم IV-A مع قانون التحكم المبسط هذا.

V دراسات المحاكاة

أُجريت محاكاة لتقييم كفاءة قانون التحكم، وكذلك لمقارنة القانون الكامل (10) بالقانون المبسط (19). ولجميع العقد مناطق لايقين تموضع مشتركة $C_i,\forall q_i\in \mathrm{\Omega }$، وكذلك أداء استشعار مشترك $C_i^{gs}$. وكانت الأهمية القبلية للنقاط داخل المنطقة $\varphi (q)=1,\forall q\in \mathrm{\Omega }$. في هذه الحالة تكون القيمة القصوى الممكنة لـ $\mathscr{H}$ هي

$${\mathscr{H}}^{\max }=\sum _{i\in I_n}𝒜\left(C_i^{gs}\right),$$

حيث إن $𝒜(\cdot )$ هي دالة المساحة، وذلك بالنظر إلى أنه يمكن رص $n$ أقراص استشعار مضمونة داخل $\mathrm{\Omega }$. وفي جميع المحاكاة، يُستخدم امتداد قانون التحكم كما هو موصوف في القسم IV-A.

V-A دراسة الحالة I

في دراسة الحالة هذه تُفحص سرعة التقارب بين القانونين الأمثل ودون الأمثل. وتُحاكى شبكة من ثلاث عقد في منطقة كبيرة. يبين الشكل 7 الحالتين الابتدائية والنهائية للشبكة، حيث تظهر أقراص اللايقين بالأسود، وأقراص الاستشعار المضمونة بالأحمر، وخلايا GV بالأزرق. وفي الشكل 8 تظهر مسارات العقد عند استخدام قانون التحكم الأمثل باللون الأحمر، وعند استخدام قانون التحكم دون الأمثل باللون الأزرق، بينما تمثل الدوائر المواضع الابتدائية وتمثل المربعات المواضع النهائية. ويُلاحظ أن التشكيلات النهائية في الحالتين متشابهة جدا، إذ إن متوسط المسافة بين الحالات النهائية للعقد يبلغ $0.57\%$ من قطر المنطقة. ويرجع ذلك إلى العدد المنخفض للعقد في الشبكة، وهو نتيجة لا يمكن تعميمها، كما يظهر في دراسة الحالة التالية. ويبين الشكل 9 تطور هدف التغطية $\mathscr{H}$ مع الزمن، مع تمثيله مرة أخرى بالأحمر لقانون التحكم الأمثل وبالأزرق للقانون دون الأمثل. وكما هو متوقع، يتقارب القانون الأمثل أسرع من القانون دون الأمثل. أما القيمة النهائية لدالة الهدف فهي نفسها لكلا قانوني التحكم في هذه الحالة، لأن الشبكة تبلغ حالة مثلى عالميا في الحالتين.

(a)

(b)

(c)

Figure 7: دراسة الحالة I: (أ) الحالة الابتدائية، (ب) الحالة النهائية باستخدام قانون التحكم الأمثل، (ج) الحالة النهائية باستخدام قانون التحكم دون الأمثل.

Figure 8: مسارات العقد باستخدام قانوني التحكم الأمثل (الأحمر) ودون الأمثل (الأزرق).

Figure 9: هدف التغطية $\mathscr{H}$ باستخدام قانوني التحكم الأمثل (الأحمر) ودون الأمثل (الأزرق).

V-B دراسة الحالة II

في دراسة الحالة هذه تُفحص شبكة من عشر عقد. يبين الشكل 10 الحالتين الابتدائية والنهائية للشبكة، حيث تظهر أقراص اللايقين بالأسود، وأقراص الاستشعار المضمونة بالأحمر، وخلايا GV بالأزرق. وفي الشكل 11 تظهر مسارات العقد عند استخدام قانون التحكم الأمثل باللون الأحمر، وعند استخدام قانون التحكم دون الأمثل باللون الأزرق، بينما تمثل الدوائر المواضع الابتدائية وتمثل المربعات المواضع النهائية. ويُلاحظ أن التشكيلات النهائية في الحالتين تبدو متشابهة جدا للوهلة الأولى، إلا أن متوسط المسافة بين الحالات النهائية للعقد يبلغ $10.12\%$ من قطر المنطقة. ويبين الفحص الدقيق للمسارات أن العقد التي تبدأ من الموضع الابتدائي نفسه لا تتقارب كلها إلى الموضع النهائي نفسه، مما يفسر المسافة المتوسطة الكبيرة. ويبين الشكل 12 تطور هدف التغطية $\mathscr{H}$ مع الزمن، مع تمثيله مرة أخرى بالأحمر لقانون التحكم الأمثل وبالأزرق للقانون دون الأمثل. وكما هو متوقع، يتقارب القانون الأمثل أسرع من القانون دون الأمثل. والقيمة النهائية لدالة الهدف هي نفسها لكلا قانوني التحكم في هذه الحالة بسبب تشابه تشكيلاتهما النهائية. غير أنه، بما أن كلا قانوني التحكم يتقاربان إلى عظمى محلية، فلا توجد ضمانات بأن يحقق أحدهما دائما أداء أفضل من الآخر.

تبرز دراسة الحالة هذه الحاجة إلى تعزيز التحكم في القسم IV-A، ولا سيما في حالة قانون التحكم الأمثل. ويمكن أن نرى في الشكل 11 أن عقدة تتحرك وفق القانون الأمثل (المسار الأحمر) مُنعت من الخروج خارج المنطقة عند الزاوية السفلية اليسرى.

(a)

(b)

(c)

Figure 10: دراسة الحالة I: (أ) الحالة الابتدائية، (ب) الحالة النهائية باستخدام قانون التحكم الأمثل، (ج) الحالة النهائية باستخدام قانون التحكم دون الأمثل.

Figure 11: مسارات العقد باستخدام قانوني التحكم الأمثل (الأحمر) ودون الأمثل (الأزرق).

Figure 12: هدف التغطية $\mathscr{H}$ باستخدام قانوني التحكم الأمثل (الأحمر) ودون الأمثل (الأزرق).

VI الدراسات التجريبية

لتقييم قانون التحكم المبسط (19)، خُططت تجربتان وأُجريتا. وتتكون التجارب من $3$ روبوتات، ونظام خارجي لتتبع الوضعية، وحاسوب يتواصل مع الروبوتات ومع نظام تتبع الوضعية عبر موجه WiFi.

الروبوتات المستخدمة هي روبوتات AmigoBot ذات القيادة التفاضلية من شركة ActiveMedia Robotics، وتوفر مجموعة أوامر عالية المستوى، مثل ضبط سرعاتها الانتقالية والدورانية مباشرة. وهذه الروبوتات مزودة أيضا بمشفرات تُستخدم للتقدير الذاتي لوضعيتها، غير أنه بسبب خطأ الانجراف نُفذ نظام تتبع خارجي. ومع أن نظام تقدير الوضعية الخارجي يُستخدم لتنفيذ قانون التحكم، فإن أداءه يُقارن بأداء المشفرات. ونظرا إلى أن الروبوتات غير مزودة بحساسات فعلية، فقد افتُرضت أنماط استشعار دائرية بنصف قطر $r^s=0.3m$ في تنفيذ قانون التحكم.

يتكون نظام تقدير الوضعية من كاميرا وحاسوب ODROID-XU4 ثماني النوى، يشغل خادما لتقدير الوضعية قائما على ArUco. وArUco [26] مكتبة صغيرة لتطبيقات الواقع المعزز، وتوفر تقدير الوضعية لبعض المجموعات المعرفة مسبقا من العلامات المرجعية. ومن ثم، بإرفاق علامة مرجعية أعلى كل روبوت، توفر مكتبة ArUco تقديرا لوضعية كل روبوت.

ولتقدير لايقين التموضع في المنظومة التجريبية، وُضعت علامة مرجعية على مركز الثقل وعلى كل رأس من رؤوس المنطقة $\mathrm{\Omega }$. وأُنشئت شبكة مثلثية ثلاثية الأبعاد 3 من هذه القياسات كما هو مبين في الشكل 13. واستُخدمت في التجارب قيمة اللايقين العظمى من تلك الشبكة، وهي $r^{u_{\max }}=0.032$ m.

Figure 13: شبكة مثلثية من قياسات لايقين التموضع.

نُفذ قانون التحكم خوارزميا على هيئة حلقة بفترة $T_s=0.1$ sec. وبعد نهاية كل تكرار يرسل الحاسوب أوامر سرعة إلى الروبوتات. في البداية تُستخدم المواضع الحالية للروبوتات لإنشاء مخطط فورونوي المضمون للأقراص غير اليقينية وحساب مداخل التحكم وفقا لقانون التحكم المبسط (19). وبعد ذلك تُنشأ نقطة هدف $q_i^t\in {ℝ}^2$ لكل روبوت بالاستناد إلى موضعه الحالي $q_i$ ومدخل التحكم الخاص به $\widetilde{u_i}$. وبعد إيجاد نقطة الهدف لكل روبوت، وبالنظر إلى موضع كل روبوت $q_i$ واتجاهه ${\theta }_i$، تُرسل مداخل التحكم في السرعة الانتقالية $v_i$ والدورانية ${\omega }_i$ إلى كل روبوت.

$v_i$ $=\min ({\displaystyle \frac{\Vert q_i^t-q_i\Vert }{T_s}},v_{\max })\cos (d{\theta }_i)$

$\omega$ $=\min ({\displaystyle \frac{|d{\theta }_i|}{T_s}},{\omega }_{\max })\sin (d{\theta }_i)$

حيث إن $d{\theta }_i=\mathrm{\angle }(q_i^t-q_i)-{\theta }_i$ و$v_{\max }$، و${\omega }_{\max }$ قيود على السرعة الانتقالية والدورانية العظميين، على الترتيب، لروبوتات Amigobot. وما إن تصبح جميع الروبوتات ضمن مسافة معرفة مسبقا $d_t=0.02m$ من نقاط الهدف الخاصة بها حتى يُحسب مخطط فورونوي المضمون وقانون التحكم مرة أخرى وتُنتج نقاط هدف جديدة.

المنطقة المبينة في جميع الأشكال المتعلقة بالتجارب هي ${\mathrm{\Omega }}^s\subseteq \mathrm{\Omega }$، أي المنطقة التي تُقيد داخلها مراكز الأقراص غير اليقينية، كما شُرح في القسم IV-A.

تُقيّم التجربتان كلتاهما بالمقارنة مع محاكاة لها مواضع روبوتات ابتدائية ولايقين تموضع وأداء استشعار مماثلة.

VI-A التجربة I

تُعرض المواضع الابتدائية والنهائية للروبوتات، لكل من التجربة والمحاكاة، في الشكلين 14 و15 على الترتيب، حيث تظهر أقراص اللايقين بالأسود، وأقراص الاستشعار المضمونة بالأحمر، وخلايا GV بالأزرق. إضافة إلى ذلك، يمكن رؤية صور للتشكيلات الابتدائية والنهائية للتجربة في الشكل 16. ويمكن ملاحظة أن جميع أقراص الاستشعار المضمونة في التشكيل النهائي محتواة داخل خلايا GV المقابلة لها في كل من التجربة والمحاكاة، مما يقود الشبكة إلى تشكيل أمثل عالميا. وبمقارنة التشكيلات النهائية، وكذلك مسارات الروبوتات للتجربة والمحاكاة المبينة في الشكل 17، يتضح أنها تختلف اختلافا ملحوظا. ويبلغ متوسط المسافة بين المواضع النهائية للعقد في التجربة والمحاكاة $8.68\%$ من قطر ${\mathrm{\Omega }}^s$. ولأن في هذه الحالة الراهنة تشكيلات مثلى عالمية متعددة يمكن للشبكة أن تبلغها، وبما أن قانون التحكم المنفذ يختلف عن القانون النظري، فمن الطبيعي أن تختلف التشكيلات النهائية بين التجربة والمحاكاة. ومع ذلك فقد تحقق تشكيل أمثل عالميا في الحالتين. لم يزد هدف التغطية $\mathscr{H}$ رتيبا بسبب قانون التحكم المنفذ. غير أنه ازداد من $83.7\%$ إلى $99.9\%$ من قيمته القصوى الممكنة. وتُقارن بيانات التموضع من مكتبة ArUco ومشفرات الروبوت في الشكل 19 [يسار]. وكما هو متوقع، كلما تحرك الروبوت مسافة أبعد وزاد دورانه، ازداد خطأ تموضع المشفرات. ويبلغ متوسط الخطأ بين المواضع النهائية للروبوتات وفق ArUco والمشفرات $4.04\%$ من قطر ${\mathrm{\Omega }}^s$. ويعرض الشكل 19 [يمين] مسارات نقاط الهدف المستخدمة في تنفيذ قانون التحكم.

Figure 14: التجربة I: التشكيل الابتدائي.

Figure 15: التجربة I: التشكيل النهائي في التجربة [يسار] والمحاكاة [يمين].

Figure 16: التجربة I: صور من مواضع الروبوتات الابتدائية [يسار] والنهائية [يمين] في التجربة.

Figure 17: التجربة I: مقارنة مسارات الروبوتات في التجربة (الأحمر) والمحاكاة (الأخضر). وُسمت المواضع الابتدائية بدوائر والمواضع النهائية بمربعات.

Figure 18: التجربة I: هدف التغطية $\mathscr{H}$ بدلالة الزمن.

Figure 19: التجربة I: [يسار] المسارات المبلغ عنها بواسطة ArUco (الأخضر) والمشفرات (الأحمر). [يمين] مسارات نقاط الهدف. وُسمت المواضع الابتدائية بدوائر والمواضع النهائية بمربعات.

VI-B التجربة II

في هذه التجربة، أضيف نصف قطر الروبوتات إلى لايقين تموضعها، بحيث يكون كل روبوت محتوى بالكامل داخل قرص لايقين التموضع الخاص به $C_i^u$. غير أن أقراص الاستشعار المضمونة حُسبت باستخدام اللايقين الفعلي فقط، لا اللايقين المزاد بنصف قطر الروبوت. وقد جرى ذلك لضمان بقاء الروبوتات داخل المنطقة $\mathrm{\Omega }$. وتُعرض المواضع الابتدائية والنهائية للروبوتات، لكل من التجربة والمحاكاة، في الشكلين 20 و21 على الترتيب، حيث تظهر أقراص اللايقين بالأسود، وأقراص الاستشعار المضمونة بالأحمر، وخلايا GV بالأزرق. إضافة إلى ذلك، يمكن رؤية صور للتشكيلات الابتدائية والنهائية للتجربة في الشكل 22. ويمكن ملاحظة أن جميع أقراص الاستشعار المضمونة في التشكيل النهائي محتواة بالكامل تقريبا داخل خلايا GV المقابلة لها في كل من التجربة والمحاكاة. وبمقارنة التشكيلات النهائية، وكذلك مسارات الروبوتات للتجربة والمحاكاة المبينة في الشكل 23، يتضح أنها لا تختلف اختلافا كبيرا. ويبلغ متوسط المسافة بين المواضع النهائية للعقد في التجربة والمحاكاة $1.54\%$ من قطر ${\mathrm{\Omega }}^s$. وبسبب زيادة لايقين التموضع في هذه الحالة، مما يؤدي إلى خلايا GV أصغر، يكون عدد القيم العظمى المحلية لدالة الهدف أقل بكثير مما في التجربة السابقة. ولذلك فمن الممكن جدا، على الرغم من اختلافاتهما، أن يتقارب قانونا التحكم النظري والمنفذ إلى التشكيل النهائي نفسه. لم يزد هدف التغطية $\mathscr{H}$ رتيبا بسبب قانون التحكم المنفذ. غير أنه ازداد من $38.8\%$ إلى $98.3\%$ من قيمته القصوى الممكنة. وتُقارن بيانات التموضع من مكتبة ArUco ومشفرات الروبوت في الشكل 25 [يسار]. وكما هو متوقع، كلما تحرك الروبوت مسافة أبعد وزاد دورانه، ازداد خطأ تموضع المشفرات. ويبلغ متوسط الخطأ بين المواضع النهائية للروبوتات وفق ArUco والمشفرات $1.54\%$ من قطر ${\mathrm{\Omega }}^s$. ويعرض الشكل 25 [يمين] مسارات نقاط الهدف المستخدمة في تنفيذ قانون التحكم.

يمكن العثور على فيديو للمحاكاة والتجارب على http://anemos.ece.upatras.gr/images/stories/videos/PTGS_IEEETAC.mp4

Figure 20: التجربة II: التشكيل الابتدائي.

Figure 21: التجربة II: التشكيل النهائي في التجربة [يسار] والمحاكاة [يمين].

Figure 22: التجربة II: صور من مواضع الروبوتات الابتدائية [يسار] والنهائية [يمين] في التجربة.

Figure 23: التجربة II: مقارنة مسارات الروبوتات في التجربة (الأحمر) والمحاكاة (الأخضر). وُسمت المواضع الابتدائية بدوائر والمواضع النهائية بمربعات.

Figure 24: التجربة II: هدف التغطية $\mathscr{H}$ بدلالة الزمن.

Figure 25: التجربة II: [يسار] المسارات المبلغ عنها بواسطة ArUco (الأخضر) والمشفرات (الأحمر). [يمين] مسارات نقاط الهدف. وُسمت المواضع الابتدائية بدوائر والمواضع النهائية بمربعات.

VII الخلاصة

تدرس هذه المقالة مسألة تغطية المساحات بواسطة فريق متجانس من العوامل المتحركة ذات التموضع غير الدقيق. وقد صُمم قانون تحكم قائم على الصعود التدرجي بالاستناد إلى تقسيم فورونوي مضمون للمنطقة. ونظرا إلى تعقيد قانون التحكم الناتج، اقتُرح قانون تحكم دون أمثل أبسط، وقورن أداء كلا القانونين في دراسات محاكاة. إضافة إلى ذلك، أُجريت تجربتان لإبراز كفاءة قانون التحكم دون الأمثل.

[] نفترض وجود $n$ أقراص $D_i,i\in I_n$ ذات مراكز $q_i={[x_i,y_i]}^T\in {ℝ}^2$ وأنصاف أقطار $r_i^u,i\in I_n$.

-A تعريف القطع الزائد وخصائصه

سنستخدم تعريف مخطط GV المعطى في (5) لقرصين $D_i$ و$D_j$ ونبين أن حدود خلايا GV الخاصة بهما هي فروع قطع زائد.

لنجد حد خلية العقدة $i$، $V_i^g=H_{ij}$، لأننا نفحص عقدتين فقط. لدينا أن

$$\partial H_{ij}=\{q\in \mathrm{\Omega }:\max \Vert q-b_i\Vert =\min \Vert q-b_j\Vert ,\forall b_i\in D_i,\forall b_j\in D_j\},$$

غير أنه بما أن $D_i$ و$D_j$ قرصان، يمكن حساب المسافتين العظمى والصغرى، ومن ثم

$$\partial H_{ij}=\{q\in \mathrm{\Omega }:\Vert q-q_i\Vert +r_i^u=\Vert q-q_j\Vert -r_i^u\},$$

حيث إن $q_i$ و$q_j$ هما مركزا $D_i$ و$D_j$ على الترتيب. وتعرّف المعادلة

$$\partial H_{ij}=\{q\in \mathrm{\Omega }:\Vert q-q_j\Vert -\Vert q-q_i\Vert =r_i+r_j\},$$

فرعا واحدا من قطع زائد، لأنها موضع النقاط التي يكون فرق مسافاتها عن بؤرتين $q_i$ و$q_j$ مساويا لثابت موجب $r_i+r_j$. أما الفرع الآخر من القطع الزائد فهو

$$\partial H_{ji}=\{q\in \mathrm{\Omega }:\Vert q-q_i\Vert -\Vert q-q_j\Vert =r_i+r_j\},$$

ويقابل حد $V_j^g$.

في القطع الزائد، يسمى الثابت الموجب المحور الأكبر ويرمز إليه عادة بـ $2a$، في حين يرمز إلى المسافة بين بؤرتيه بـ $2c$. ثم يُعرّف معامل ثالث، هو المحور الأصغر ويرمز إليه بـ $2b$، بالمعادلة $a^2+b^2=c^2$. وبناء على ذلك، لدينا في هذه الحالة أن $2a=r_i+r_j$ و$2c=\Vert q_i-q_j\Vert$. إضافة إلى ذلك، تسمى أقرب نقطتين على الفرعين رأسي القطع الزائد، وتكون المسافة بينهما $2a$.

Figure 26: قطع زائد مع إظهار معامليه $2a$ و$2c$.

-B المعادلة البارامترية للقطع الزائد

بافتراض أن بؤرتي القطع الزائد هما $q_i={[-c0]}^T$ و$q_j={[c0]}^T$، فإن معادلته البارامترية هي

$$\gamma (t)=\left[\begin{array}{c}\pm a\cosh (t)\\ b\sinh (t)\end{array}\right],t\in ℝ$$

حيث إن $a$ و$b$ و$c$ هي تلك المعرفة في الملحق -A، وتشير علامة $+(-)$ إلى الفرع الغربي (الشرقي) من القطع الزائد، وهو $H_{ji}(H_{ij})$.

وبتدوير بؤرتي القطع الزائد حول الأصل بزاوية $\theta$، تصبح المعادلة البارامترية

وأخيرا، إذا أُعطيت بؤرتان $q_i={[x_i{y}_i]}^T$ و$q_j={[x_j{y}_j]}^T$ في أي موضع على المستوى، فإن المعادلة البارامترية العامة للقطع الزائد هي

(20)

حيث إن $\theta =\arctan (\frac{y_j-y_i}{x_j-x_i})$.

-C متجهات الناظم الواحدية الخارجية

لأي منحنى $\gamma (t)$ يُعرّف متجه الناظم كما يأتي

$$\widehat{n}(t)=\ddot{\gamma }-\left(\ddot{\gamma }\cdot \frac{\dot{\gamma }}{\Vert \dot{\gamma }\Vert }\right)\frac{\dot{\gamma }}{\Vert \dot{\gamma }\Vert }.$$

ومقدار هذا المتجه هو الانحناء عند تلك النقطة المعينة على المنحنى، ويتجه نحو مركز الانحناء. وبما أن الفروع الزائدية تعرّف مناطق محدبة في المستوى، فإن متجه الناظم الواحدي الخارجي يُعطى بـ

$$n(t)=-\frac{\widehat{n}}{\Vert \widehat{n}\Vert }.$$ (21)

غير أنه، بما أن التعابير الناتجة كبيرة جدا بحيث لا تُعرض هنا، يعرض الشكل 27 رسما دالا لمتجهات الناظم الواحدية الخارجية لأحد فرعي قطع زائد.

Figure 27: تظهر متجهات الناظم الواحدية الخارجية لأحد فرعي القطع الزائد باللون الأسود.

-D مصفوفة جاكوبي

تُظهر مصفوفة جاكوبي $\upsilon _j^i{}_{}{}^T$ التغير في المنحنى ${\gamma }_j(t)=\left[\begin{array}{c}{\gamma }_{jx}(t)\\ {\gamma }_{jy}(t)\end{array}\right]$ الناتج عن حركة العقدة $i$، ومن ثم فإن منقولها هو

(22)

وتكون التعابير الخاصة بعناصر مصفوفة جاكوبي كبيرة جدا بحيث لا تُعرض هنا؛ ولذلك تُعرض بعض الرسوم الدالة لها بالنسبة إلى المعامل $t$ في الشكل 28.

(a)

(b)

(c)

(d)

Figure 28: عناصر مصفوفة جاكوبي ${\upsilon }_i^i$ (الأزرق) و${\upsilon }_j^i$ (الأحمر) بدلالة $t$. (أ) $\frac{\partial {\gamma }_{jx}}{\partial x_i}$، (ب) $\frac{\partial {\gamma }_{jx}}{\partial y_i}$، (ج) $\frac{\partial {\gamma }_{jy}}{\partial x_i}$، (د) $\frac{\partial {\gamma }_{jy}}{\partial y_i}$.