مسأله طرح ریزی مسیر[i] یک ربات متحرک عبارت است از یافتن یک مسیر آزاد بدون تصادم بین دو نقطه مشخص از فضای وضعیت ربات [‎0]. ربات باید از بین موانع عبور کند و به موقعیت هدف برسد. برای حل مسأله طرح مسیر ربات‌ها‏ی متحرک در محیط‌های با موانع محدب روش‌های متعددی وجود دارد که این روش‌ها به سه دستـه کلی تقسیـم می­شوند [2][3]: روش‌های تفکیک سلولی[ii]، روش‌های طرح جاده[iii] و روش‌های میدان پتانسیل. در روش‌های تفکیک سلولی فضای وضعیت به صورت شبکه‌ای از سلول‌ها تقسیم بندی می­شود و سپس با اتصال سلول‌های مجاور یک گراف اتصال ایجاد می­شود. با جستجو در این گراف مسیری از وضعیت اولیه به وضعیت نهایی پیدا خواهد شد. روش‌های طرح جاده فضاهای آزاد متصل به هم فضای وضعیت را به صورت شبکه­ یک بُعدی از راه‌های استاندارد مدل می‌کنند که مسیر ربات باید درون این شبکه جستجو شود. در روش‌های میدان پتانسیل ربات به صورت یک جسم متحرک باردار درون یک میدان مغناطیسی مدل می­شود. در این میدان مغناطیسی بار غیر همنام با ربات به نقطه هدف و بار همنام با ربات به موانع تخصیص داده می­شود؛ در نتیجه ربات به سوی هدف کشیده می­شود و از اطراف موانع دفع می­شود. تمامی این رویکردها به یک بازنمایی[iv] کامل از فضای وضعیت ربات نیاز دارند که این امر مستلزم انجام طرح مسیر در زمان غیر واقعی[v] و صرف هزینه محاسباتی زیاد است. به طور کلی، پیچیدگی محاسباتی با افزایش درجات آزادی ربات و ابعاد فضای وضعیت به صورت نمایی افزایش می­یابد [4]. از طرفی، هر کدام از فرضیات زیر نیز موجب افزایش پیچیدگی مسأله طرح مسیر می­شوند:

1- محیط‌های چند رباتی- چند هدفی؛

2- محیط‌های دینامیک (با موانع متحرک)؛

3- محیط‌های با موانع مقعر. 

پیدا کردن یک روش زمان-واقعی[vi] طرح مسیر با کارآیی مناسب در چنین محیط‌هایی همواره یک بحث چالش برانگیز بوده است.

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

2- تحقیقات مرتبط

توسعه روش‌های طرح مسیر کم هزینه (از نظر محاسباتی) مبتنی بر بازنمایی محلی فضای کار همواره مورد توجه بوده است. به دلیل پیچیدگی مسأله، تکنیک‌ها‏ی مختلف هوش محاسباتی برای طرح مسیر ربات‌ها‏ی متحرک به کار رفته­اند. الگوریتم ABC [‎0]، سیستم‌ها‏ی فازی [‎0]، اجتماع مورچگان [‎0]، بهینه سازی اجتماع ذرات [‎0] و الگوریتم ژنتیک [9] از جمله این روش‌ها هستند.

اتوماتاهای سلولی به عنوان سیستم‌ها‏ی توزیع شده[vii] با گسترش فضایی[viii] در ابتدا به وسیله فان نیومن ابداع شدند [10] و به وسیله بورکس گسترش یافتند [‎0][‎0]. اتوماتی سلولی مجموعه­ای از سلول‌ها است که در شبکه­ی d- بُعدی قرار گرفته­اند؛ به طوری که حالت هر سلول به صورت تابعی از حالت­های سلول‌های همسایه و مبتنی بر مجموعه‌ای از قواعد به روز رسانی می­شود. سلول‌ها در اتوماتای سلولی عناصر ساده­ای با اتصالات محلی هستند که مجموعه این سلول‌ها توانایی انجام محاسبات پیچیده را با درجه بالایی از قوام و کارآیی دارند. همچنین اتوماتای سلولی را به عنوان سیستم‌ها‏ی دینامیکی می­توان جایگزینی برای معادلات دیفرانسیل در نظر گرفت [‎0]. به این دلایل اتوماتای سلولی به طور وسیع در فناوری، علوم رایانه، ریاضیات و علوم طبیعی به کار رفته است. پردازش تصویر [‎0]، ربات‌ها‏ی خود شکل پذیر مجدد [‎0]، ترکیب اسیدهای آمینه [‎0] و مدلسازی فرآیندهایی مانند رشد جوامع شهری [‎0]، زمین لرزه [‎0] و تشکیل کهکشان‌ها [‎0] مثال‌هایی از کاربردهای اتوماتای سلولی هستند. اتوماتای سلولی برای شبیه‌سازی سریع مدل‌های علمی و انجام عملیات محاسباتی نیز به کار رفته است [20].

با توجه مزیت در پردازش‌های موازی و ویژگی محاسبات محلی، اتوماتای سلولی می‌تواند به عنوان یک ابزار مناسب برای انجام طرح‌ریزی مسیر ربات‌ها‏ به صورت سریع و مطمئن به کار رود. در [‎0] یک الگوریتم ساده طرح ریزی مسیر ربات‌ها‏ی متحرک در محیط‌هایی که فقط دارای موانع محدب هستند، ارائه شد. ژیوناس و همکارانش یک الگوریتم طرح­ریزی مسیر بدون تصادم را برای یک ربات لوزی شکل معرفی کردند [‎0]. الگوریتم آنها مبتنی بر تصویر فضای آزاد به روی یک گراف وورونی[ix] بود که این گراف از تکامل زمانی یک اتوماتای سلولی ساخته می‌شد. این روش تنها برای ربات‌ها‏ی با شکل خاص لوزی قابل اعمال بود. در [‎0] نشان داده شد که اتوماتای سلولی می­تواند امکان انجام محاسبات کارآمد به منظور طرح­ریزی حرکت یک ربات منفرد در محیطی انباشته از موانع را فراهم آورد. مارچز یک الگوریتم واکنشی مبتنی بر محاسبات چند لایه را برای انجام طرح ریزی مسیر ربات‌ها‏ی متحرک غیرهولونومیک پیشنهاد کرد [‎0]. او پس از آن برای یک سیستم چند­رباتی متشکل از ربات‌ها‏یی با شکل­ها و اندازه‌های متعدد و کینماتیک متفاوت، یک روش طرح­ریزی مسیر سریع را ارائه کرد [‎0]. در روش‌های پیشنهادی مارچز، ربات‌ها‏ باید اطلاعات اولیه‌ای را درباره شکل و اندازه موانع بدانند و در واقع به یک بازنمایی جزئی اولیه از محیط نیاز دارند. به عنوان کارهای پیش زمینه برای این مقاله در [‎0] یک روش غیر زمان-واقعی مبتنی بر اتوماتای سلولی برای طرح­ریزی مسیر یک ربات متحرک پیشنهاد گردید که این روش در [‎0] برای موانع مقعر هم تعمیم یافت.

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

اولین هدف این مقاله، توسعه یک روش مبتنی بر اتوماتی سلولی است. استفاده از اتوماتی سلولی امکان طرح ریزی سریع و زمان-واقعی و بدون نیاز به بازنمایی محیط را فراهم می­آورد. یک چالش مهم در طرح مسیر ربات‌ها‏ی متحرک عبور از موانع مقعر است؛ چرا که به علت وجود کمینه محلی در الگوریتم جستجو، ربات ممکن است درون تقعر موانع به دام افتد. مکانیزم­های اجتماع مورچگان با توجه به مزیت‌شان در حل مسائل پیچیده با فضای جستجوی بزرگ [‎0][‎0] می‌توانند نامزدهای خوبی برای حل مشکل موانع مقعر در طرح مسیر ربات‌ها‏ باشند. بنابراین در این مقاله، به عنوان هدف دوم، یک الگوریتم الهام گرفته از اجتماع مورچگان پیشنهاد می‌‌شود تا روش طرح مسیر مبتنی بر اتوماتای سلولی را برای استفاده در محیط‌های با موانع مقعر تعمیم دهد.

در نهایت، مزیت اصلی روش پیشنهاد شده در این مقاله قابلیت انجام زمان-واقعی طرح‌ریزی مسیر ربات‌ها‏ی متحرک در محیط‌هایی با موانع محدب و مقعر است، بدون آنکه نیازی به بازنمایی محیط باشد.                      

3- روش طرح ریزی مبتنی بر اتوماتای سلولی

3-1- اتوماتای سلولی

اتوماتای سلولی متشکل از شبکه­ای d-بعدی از سلول‌هاست [‎0]. هر سلول یک ماشین حالت-محدود است که با نمایه n نمایش داده می‌شود (n=1,…,N). برای مثال در یک شبکه دوبعدی IÍJ  داریم: N=IÍJ . هر سلول می­تواند در یکی از حالت­های متناهی قرار داشته باشد و می­تواند به طور زمان-واقعی با سلول‌های مجاور تعامل کند تا حالت خود را به روز نماید. تکامل اتوماتای سلولی بر مبنای یک قاعده محلی که برای همه سلول‌ها یکسان است انجام می­شود [‎0][‎0]. حالت­های اتوماتا می‌تواند با تعدادی عدد صحیح یا تعدادی نماد بیان شود. حالت سلول n در لحظه t به صورتنشان داده می‌شود. قاعده به روز رسانی اتوماتا حالت جاری یک سلول و سلول‌های مجاور را به عنوان ورودی می­گیرد و حالت بعدی آن سلول را به عنوان خروجی به دست می­دهد. قواعد اتوماتای سلولی می توانند به صورت جدول یا به صورت تابع بیان شوند. مفهوم همسایگی یک مفهوم کلیدی در اتوماتای سلولی است. برای آرایه یک بُعدی تعریف همسایگی ساده است؛ اما برای آرایه دو بعدی تعریف­های مختلفی برای همسایگی وجود دارد. همسایگی نیومن و همسایگی مور[x] از مشهورترین آنها هستند. همسایگی نیومن هر هشت سلول موجود در مجاورت سلول وسط را به عنوان همسایگی در نظر می­گیرد در حالی که همسایگی مور فقط سلول‌های بالا، پایین، چپ و راست را به عنوان همسایگی تعریف می­کند. ما در این مقاله از مفهوم همسایگی نیومن استفاده می­کنیم.

شکل(1) یک اتوماتای سلولی یک بعدی با حالت­های دودویی و تعریف همسایگی به شعاع یک (r=1) را نشان می­دهد. شبکه و قواعد به روز رسانی آن به همراه دو وضعیت متوالی شبکه در شکل نشان داده شده­اند.

3-2- الگوریتم طرح مسیر

در این بخش یک تکنیک طرح مسیر ربات‌ها‏ی متحرک را مبتنی بر اتوماتای سلولی ارائه می­کنیم. این تکنیک اطلاعات محلی فضای وضعیت را به­ کار می­گیرد و نیاز به بازنمایی کلی محیط ندارد. فرض می­شود که ربات بردار موقعیت هدف  را می­داند و قادر است که در هر گام زمانی بردار موقعیت خود  را به دست آورد (مثلاً از طریق  GPSیا [xi]DR). همچنین فرض می­شود که ربات فقط یک سیستم حسگری با برد کوتاه نیاز دارد تا مشخص  کند که سلول‌های مجاور خالی هستند یا نه. این امر مثلا با نصب هشت حسگر ثابت اولتراسونیک (یا یک حسگر گردان) بر روی ربات ممکن می­شود. برای سادگی مدل­سازی، ربات با در نظر گرفتن تمام جهت گیری­های ممکن آن مطابق شکل (2) درون یک دایره محاط می­شود و به صورت یک ربات همه سویه در نظر گرفته می­شود. فضای وضعیت هم به صورت یک شبکه متشکل از سلول‌های مربعی تقسیم بندی می­شود به گونه‌ای که ربات بتواند به طور کامل درون یک سلول قرار گیرد. در این شبکه تعدادی از سلول‌ها حاوی ربات هستند (یک سلول در سیستم تک رباتی)، درون تعدادی از سلول‌ها مانع قرار دارد و سایر سلول‌ها آزاد هستند. اکنون شبکه‌ای از سلول‌ها داریم که هر یک از سلول‌ها می­تواند سلول ربات (R)، سلول مانع (O) یا سلول آزاد (F) باشد. می‌توان این شبکه را یک اتوماتای سلولی با سه حالت ممکن {F, O, R}  تعبیر کرد. تعریف مناسب قواعد تکامل اتوماتا می‌تواند به یک اتوماتای سلولی طرح کننده مسیر منجر شود. برای ایجاد قواعد مورد نظر مفهوم «بهترین سلول رو به هدف[xii]» را به صورت زیر تعریف می­کنیم:

تعریف: بهترینسلولروبههدف سلولی است که در بین سلول‌های خالی در همسایگی سلول ربات، نزدیکترین سلول به هدف باشد.

اگر بهترین سلول رو به هدف را با B نمایش دهیم، اتوماتای سلولی دارای چهار حالت خواهد بود: {F, O, R, B}. شکل (3) یک نمای شماتیک از محیط شبکه بندی یک ربات و سلول‌های مربوطه را نشان می‌دهد.

شکل (1): یک اتوماتای سلولی یک بُعدی و قاعده به روزرسانی آن

شکل (2): ربات (با در نظر گرفـتن جهت گیری های مختلف) می­تواند درون یک دایره محاط شود و به صورت

 یک ربات دایره­ای دیده شود.‏

شکل (3): فضای کاری ربات را می توان به صورت یک اتوماتای سلولی دو بعدی با چهار حالت ‏‎{F, O, R, B}‎‏ مدل کرد. در شکل سمت راست سلول هدف با ‏F‏ ‏پررنگ نشان داده شده است.

شکل (4): شبه کد برنامه تکامل اتوماتای سلولی

شکل (5): بردارهایجهتدراطرافسلولربات

اکنون قواعد اتوماتا را بر مبنای این اصل ساده بنا می‌کنیم که در هر گام سلول ربات R باید به بهترین سلول رو به هدف B منتقل شود و یک سلول آزاد F  بر جای گذارد. این قاعده با استفاده از شبه­کد شکل (4) قابل پیاده سازی است. برای مثال اگر این قاعده را بر روی شبکه شکل (3) اعمال کنیم، همسایگی نشان داده شده با رنگ خاکستری به صورت زیر به روز می­شود:     

و حالت سایر سلول‌ها بدون تغییر باقی می­ماند. در واقع در یک محیط تک رباتی در هر گام زمانی فقط حالت یکی از سلول‌ها تغییر می­کند.

با استفاده از الگوریتم شکل (4)، سلول ربات در هر گام زمانی جایگزین بهترین سلول رو به هدف می­شود. از آنجا که تعداد سلول‌های شبکه متناهی است و موانع مقعر نیز در محیط وجود ندارند، توقع می‌رود که سلول ربات در گام‌های زمانی متناهی به سلول هدف برسد.

پیدا کردن بهترین سلول رو به هدف یک مرحله اساسی در قاعده شکل (4) است. برای انجام این کار بردارهایجهت را طبق شکل (5) به هر یک از سلول‌های مجاور سلول ربات نسبت می­دهیم. بهترین سلول رو به هدف را می­توان با استفاده

شکل (6): شبه کد پیدا کردن بهترین سلول رو به هدف.  کاردنالیته (تعداد اعضا) مجموعه K را نشان می‌دهد.

شکل (7): ربات‌ها در محیط چند رباتی با هم برخورد نخواهند کرد.

از زاویه بین بردار  و بردارهای جهت مذکور پیدا کرد. (و بردارهای موقعیت هدف و ربات هستند). زاویه بین این بردارها را می­توان به مفهوم ضرب برداری آنها نسبت داد. از بین هشت سلول همسایگی، سلولی که مرتبط با بزرگترین مقدار ضرب برداری باشد، به عنوان بهترین سلول رو به هدف تعیین و با B نشان گذاری خواهد شد. شبه کد شکل (6) برای پیدا کردن بهترین سلول رو به هدف نوشته شده است.

4- محیط‌های چند رباتی

روش ارائه شده در بخش قبل را می­توان به آسانی با افزایش تعداد حالت­ها برای محیط‌های چند رباتی هم تعمیم داد. برای مثال، در یک محیط دو رباتی هر سلول می­تواند دارای یکی از حالت‌های ششگانه {F, O, B1, B1, R1, R2} باشد. به سادگی می­توان نشان داد که با اعمال پی در پی الگوریتم شکل (3) به سلول‌های ربات، طرح مسیر ربات‌ها‏ی سیستم چند رباتی با موفقیت انجام خواهد شد:

• برای نزدیک شدن هر ربات به هدف خود، استدلال قبلی برقرار است.

• برای ارزیابی این که ربات‌ها‏ به یکدیگر برخورد نخواهند کرد، بدون از دست رفتن کلیت دو ربات شکل (7) را در نظر بگیرید. اگر قاعده اتوماتا ابتدا به ربات R1 در شکل (7-الف) اعمال شود، سلول ربات به سلول B1 نقل مکان خواهد شد (مثلا سلول وسط در شکل). اکنون در شکل (7-ب)، سلول B قبلی دیگر یک سلول آزاد نیست و R2 به آن سلول نخواهد رفت.

5- مکانیزم برگرفته از اجتماع مورچگان برای عبور از موانع مقعر

الگوریتم طرح مسیر مبتنی بر اتوماتای سلولی که در بخش­های قبل ارائه شد، موانع محـیط را محدب در نظر می­گیرد. با استفاده از یک روش الهام گرفته از اجتماع مورچگان می­توان الگوریتم را به منظور استفاده در موانع مقعر توسعه داد.

در این اجتماع چندین عامل (ربات) در محیط همکاری می­کنند؛ عامل‌ها‏ی پیشرو نواحی تقعر موانع را شناسایی و برای عامل‌ها‏ی بعدی علامت گذاری می­کنند. برای شناسایی ناحیه تقعر در هر گام زمانی ربات پیشرو حالت سه سلول نزدیکتر  به هدف را در همسایگی خود چک می­کند اگر هر سه سلول مانع باشند، ربات سلول جاری را با ریختن مقدار معینی از فرمون علامت گذاری می­کند. ربات‌ها‏ی بعدی سلول‌های

شکل (8): شبه کد برنامه تکامل اتوماتای سلولی بهبود یافته به وسیله تکنیک برگرفته از اجتماع مورچگان. در این الگوریتم ربات هنگام ترک یک سلول ناحیه تقعر، فرمون برجای می‌گذارد. 

فرمون را به عنوان مانع تلقی می­کنند و از رفتن به آنها اجتناب می­کنند. شکل (8) شبه کد مربوط به الگوریتم بهبود یافته با تکنیک اجتماع ذرات را نشان می­دهد که در آن هنگامی که سلولِ ربات یک سلول داخل ناحیه تقعر را ترک می­کند، حالت آن سلول به P (سلول فرمون) تغییر می یابد.

برای توضیح بیشتر مطالب، شرایط شکل (9) را در نظر بگیرید که در آن سلول هدف پایین­ترین سلول در سمت چپ شبکه است. با اعمال قواعد به روز رسانی اتوماتا، سلول ربات روی مسیر نشان داده شده در شکل (9-الف) حرکت می­کند و بین سلول‌های C₁ و C₂ گیر می­افتد. در صورتی که قاعده بهبود یافته را برای این شرایط اعمال کنیم، هنگامی که اتوماتا در سلول  C₁با بلوک  مواجه شود، سلول ربات (R) هنگام ترک سلول C₁ مقداری فرمون به جای خود قرار می­دهد. در گام‌های بعدی زمانی عامل‌ها‏ (ربات‌ها‏) سلول C₁ را به عنوان B انتخاب نمی­کنند و به آن منتقل نمی­شوند.

 با اعمال این قاعده بهبود یافته مسیـر نشـان داده شده در شکل (9-ب) ایجاد می­شود. در این شکل سلول‌های فرمون با رنگ خاکستری نشان داده شده­اند. مشخص است که با اعمال قاعده بهبود یافته شکل (6) ربات توانسته از ناحیه تقعر خارج شود و به سمت هدف حرکت کند.

عملکرد این روش طرح­ریزی در سیستم‌ها‏ی چند رباتی بهتر هم خواهد بود. اگر اجتماعی از عامل‌ها‏ی رباتی را در نظر بگیریم که حرکت خود را با یک تاخیر زمانی معین نسبت به همدیگر شروع می­کنند، در حالی که هر کدام به طور مستقل الگوریتم بهبود یافته شکل (8) را اجرا می­کند، مسیر ایجاد شده حتی هموارتر هم خواهد بود. برای مثال، شرایط شکل (10) را در نظر بگیرید که در آن ربات R1 قبلاً ناحیه تقعر را پس از علامت گذاری آن ترک کرده است. ربات R2 به سلول‌های فرمون وارد نخواهد شد و بدون ورود به داخل ناحیه تقعر به سمت هدف حرکت خواهد کرد. در طرح ریزی غیر زمان-واقعی سیستم‌ها‏ی تک رباتی هم می­توان با استفاده از تعدادی عامل (ربات) مجازی، اجتماع ربات‌ها‏ را تشکیل داد و مسیر همواری برای ربات ایجاد کرد.

شکل (9): تفاوت عملکرد قواعد بهبود نیافته اتوماتا (شکل (6)) و بهبود یافته اتوماتا (شکل (8)) در مواجهه با موانع مقعر

شکل (10): اعمال قاعده بهبود یافته اتوماتا به یک سیستم دو رباتی. R1 ناحیه تقعر را قبل از رسیدن R2 ترک کرده است.

باید تاکید شود که هرچند روش پیشنهادی از الگوریتم اجتماع مورچگان الهام گرفته شده است، دو تفاوت با الگوریتم کلاسیک اجتماع مورچگان دارد: اول اینکه در الگوریتم کلاسیک اجتماع مورچگان عامل‌ها‏ علاقمند به حرکت در مسیرهای پُر فرمون هستند در حالی که در روش پیشنهادی عامل‌ها‏ از سلول‌های فرمون اجتناب می‌کنند. دوم اینکه در الگوریتم کلاسیک، مورچه‌ها به طور مداوم روی مسیر حرکت خود فرمون می­ریزند، در حالی که در روش پیشنهادی ربات‌ها‏ فرمون را فقط در ناحیه تقعر می­ریزند.

6- نتایج آزمایش

یک ربات متحرک با چرخ­های تفاضلی برای پیاده سازی الگوریتم پیشنهادی ساخته شد. یک حسگر چرخان اولتراسونیک بر روی ربات نصب شد تا با استفاده از آن بتوان حالت سلول‌های قرار گرفته در همسایگی ربات را مشخص کرد.

در ابتدا یک محیط با تعدادی مانع محدب در نظر گرفته شد و الگوریتم پیشنهادی برای دو مجموعه از نقاط اولیه و هدف اعمال گردید. مسیرهای ایجاد شده در شکل (11) نشان داده شده­اند. هرچند که مسیرهای ایجاد شده کوتاهترین مسیرهای ممکن نیستند، ولی با توجه به این که روش پیشنهاد شده یک روش زمان-واقعی است و بازنمایی کامل محیط را به­کار نمی­گیرد، طول مسیرها به اندازه قابل قبولی کوتاه هستند. در واقع، به دلیل عدم استفاده از بازنمایی کامل محیط، توقع نمی‌رود که الگوریتم پیشنهادی بتواند مسیر بهینه را پیدا کند و همین که یک مسیر کوتاه با طول معقول برای رسیدن به هدف پیدا شود، برای یک روش زمان-واقعی عملکرد قابل قبول تلقی خواهد شد. 

در مرحله بعد یک محیط با موانع مقعر درنظر گرفته شد و الگوریتم بهبود یافته برای دو مجموعه نقطه اولیه هدف اعمال گردید. شکل (12) مسیرهای ایجاد شده توسط الگوریتم و نتایج مربوطه را نشان می­دهد. این شکل‌ها بر توانایی روش طرح­ریزی پیشنهادی برای کارایی مناسب در محیط‌های با موانع مقعر دلالت دارد. ربات‌ها‏ توانسته­اند از تقعر موانع بگذرند و درون آنها به دام نیفتند.

در مرحله سوم آزمایش­ها، یک محیط دو رباتی مطابق شکل (13) در نظر گرفته شد که در آن نقاط اولیه-هدف دو ربات به گونه ای انتخاب شد که مسیر ربات‌ها‏ با همدیگر تداخل داشته باشند. با اجرای الگوریتم پیشنهادی، ربات‌ها‏ مسیر خود را به شکلی تغییر دادند که بدون برخورد به یکدیگر به اهداف خود برسند. برای بررسی این که ربات‌ها‏ با هم برخورد نکرده اند در این شکل برخی گام‌های زمانی ربات‌ها با شماره­هایی درون دایره های سفید و سیاه مشخص شده اند که نشان می­دهند دو ربات در یک لحظه در یک سلول یکسان قرار ندارند. از جنبه دیگر اگر ربات دوم برای ربات اول به عنوان مانع متحرک فرض شود، می‌توان نتیجه گرفت که این روش برای محیط‌هایی با موانع متحرک هم کاربرد دارد.

در واقع با این آزمایش­ها عملکرد مورد انتظار روش پیشنهادی ارزیـابی شده است. لازم است توضیح داده شود کـه چون برای ربات امکان حرکت مورب وجود نداشت، در آزمایش­ها هر حرکت مورب به صورت ترکیبی از یک حرکت افقی و یک حرکت عمودی اجرا شده است.

شکل (11): آزمایش‌هایمربوطبهدومسألهطرح‌ریزیدریکمحیطباموانعمحدب. مسیرهایایجادشدهبهوسیلهروشپیشنهادیباخطسفیدومسیرطیشدهتوسطرباتبانقطهچیننمایشدادهشده­اند

شکل (12): آزمایش‌هایمربوطبهدومسألهطرحریزیدریکمحیطبا  موانعمحدبومقعر. مسیرهایایجادشدهبهوسیلهروشپیشنهادیباخطسفیدومسیرطیشدهتوسطرباتبانقطه­چیننشاندادهشده­اند.

شکل (13): آزمایش‌های مربوط به مسأله طرح ریزی در یک محیط دو رباتی. مسیرهای ربات‌ها به با خطوط پر و نقطه چین نشان داده شده­اند. برخی گام‌های زمانی ربات‌ها با شماره‌های درون دایره‌های سقید و سیاه مشخص شده‌اند که نشان می‌دهند دو ربات در یک لحظه در یک سلول یکسان قرار ندارند.

7- جمع بندی و نتیجه­گیری 

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

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

یک تکنیک برگرفته از الگوریتم اجتماع مورچگان به منظور بهبود روش پیشنهادی ارائه شد تا روش طرح ریزی برای محیط‌های با موانع مقعر هم قابل استفاده باشد. در این تکنیک ربات‌ها‏ی پیشرو نواحی تقعر موانع را شناسایی و با ریختن فرمون علامت گذاری می­کنند. ربات‌ها‏ی بعدی از ورود به سلول‌های فرمون و در نتیجه، ورود به نواحی تقعر اجتناب می­کنند. در طرح ریزی مسیر ربات‌ها‏ در زمان غیر واقعی و در سیستم‌ها‏ی تک رباتی می­توان از ربات‌ها‏ی مجازی به عنوان ربات پیشرو استفاده کرد اما در طرح ریزی زمان-واقعی سیستم‌ها‏ی چند رباتی، همه ربات‌ها‏ واقعی خواهند بود.

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

از آنجا که این روش از بازنمایی کلی محیط استفاده نمی­کند و اطلاعات محلی را برای طرح ریزی به کار می‌گیرد، انتظار نمی­رود که بتواند مسیرهای بهینه را ایجاد کند و در واقع چنین نیز هست. البته، می‌توان با استفاده از برخی توابع کشف کنندگی[xiii] جواب‌های نزدیک بهینه را به دست آورد که می­تواند موضوع تحقیقات بعدی باشد.

همچنین، در این روش ربات با محاط شدن درون یک دایره، یک ربات همه سویه فرض می­شود. توسعه این روش برای آنکه بتواند برای ربات‌ها‏ی غیر هولونومیک هم قابل استفاده باشد، می­تواند زمینه دیگری برای تحقیقات آینده باشد.