برنامه ریزی عملیات پویش و مین یابی برای چند روبات در محیط های ناشناخته

نویسندگان

دانشگاه تربیت مدرس

چکیده

به موازات پیشرفت سخت افزاری روبات ها، علم برنامه ریزی حرکت آنها نیز روز به روز پیچیده تر و ضروری تر شده و روبات ها را قادر می سازد قابلیت های خود را در کاربردهایی که حضور انسان ها در آن ناممکن یا خطرناک هستند ارتقا دهند. مثالی از چنین کاربردهایی، عملیات جستجو و جمع آوری مین های دفن شده در محیط های باز می باشد. مقاله حاضر به حل مسئله پویش و مین یابی در محیطی ناشناخته توسط چند روبات متحرک می پردازد که در آن روبات ها با یکدیگر تعاملی همکارانه دارند. برای پویش محیط و یافتن اقلام پراکنده در آن، روش جدید MSRT توسعه داده شده، و برای برنامه ریزی جهت دسترسی و جمع آوری اقلام پراکنده توسط روبات ها مدلی ریاضی شبیه به مسئله فروشنده دوره گرد چندگانه (mTSP) پیشنهاد شده است که با تلفیق آن با تکنیک هایی نظیر خوشه بندی k-means، الگوریتم جستجوی A* و گراف دیدنگار، مسیریابی برای هر روبات انجام می شود. مقایسه روش جدید با نتایج حاصل از بهینه سازی ریاضی مسئله نشان داد که روش پیشنهادی جواب های نزدیک به بهینه مطلق را در زمان های بسیار کوتاهتری تولید می کند.

کلیدواژه‌ها


عنوان مقاله [English]

Planning of Covering and Minesweeping Operations for Multiple Robots in Unknown Environments

نویسندگان [English]

  • Ali Mirdar Harijani
  • Ellips Masehian
چکیده [English]

Abstract – In parallel with advances in robots hardware, the motion planning science has become increasingly indispensable and complicated, and enables robots to enhance their capabilities in applications where the presence of humans is impractical or hazardous. The covering and minesweeping operations of outdoor areas are examples of such applications. This paper deals with the problem of covering and minesweeping of unknown environments by multiple mobile robots which have cooperative interactions. For searching the space, the new method of Multi Sensor-based Random Trees (MSRT) is developed, and for planning the robots’ paths toward the scattered items and their collection, a mathematical model similar to the Multiple Traveling Salesman Problem is proposed, which together with the k-means clustering, the A* search, and the Visibility Graph techniques plans the route of each robot. Comparisons with the counterpart mathematic model solved to optimality showed that the proposed method produces suboptimal solutions in much shorter computational times.

کلیدواژه‌ها [English]

  • Covering
  • Minesweeping
  • Multi robot Motion Planning
  • TSP
  • Clustering