En Yakın Komşu Sezgiseli Yaklaşımı İle Market Tabanlı Görev Dağıtımı

Abstract

Çok-robotlu uygulamalarda çalışılan ana konulardan biri görevleri robotlara dağıtmak ve bu dağıtılmış görevleri kullanan robotlar için etkin rotalar inşa etmektir. Bu makalenin esas amacı piyasa temelli görev dağıtım mimarisi aracılığıyla görevleri dağıtmak ve bilinen bir iç mekânda çok-robotlu sistemler için çarpışmanın olmadığı rotalar inşa etmektir. Görev dağıtımı için piyasa temelli mimari inşa edilmiş ve dört adet çoktürel gezgin robottan oluşan bir örnek takıma uygulanmıştır. Çalışmada, görevler iki kısıt uyarınca dağıtılmıştır: robotların toplam iş yapma sürelerini en aza düşürmek ve gruptaki her robotun görev robot uyum değerini en yükseğe çıkarmak. Bu kısıtlar bir karar parametresinin değeri değiştirilerek sağlanmıştır. Önerilen yöntemin etkinliğini gösterme için bu kısıtlar içinde karşılaştırmalar yapılmıştır. Rotaları inşa etmek için En Yakın Komşu sezgiseli ve Dijkstra’nın en kısa yol algoritmasının birleşimi kullanılmıştır. Çakışmayan rotaları inşa edebilmek için çarpışmaları saptayan ve çözen bir yöntem geliştirilmiştir. Çalışmada erkinler arasındaki iletişim için Açık Erkin Mimarisi (Open Agent Architecture) kullanılmıştır. Ek olarak önerilen yöntemin uygulanabilirliğini kanıtlamak için MobileSim platformunda benzetimler yapılmıştır.

One of the main subjects that is studied in multi-robot applications is allocating tasks to robots and constructing objective-efficient tours for the robots using these allocated tasks. The main purpose of this paper is to allocate tasks via market-based task allocation architecture and to construct collision-free routes for multi-robot systems in a known indoor environment. For task allocation, a market-based architecture is constructed and applied to an example of a team of four heterogeneous mobile robots. In the study, tasks are allocated according to one of two constraints: minimizing the makespan of the robots and maximizing the robot task matching value of each robot in the group. These constraints are achieved by changing the value of a decision parameter. To show the effectiveness of the proposed method, comparisons are made within these constraints. To construct path, a combination of the Nearest Neighbor heuristic and Dijkstra's shortest path algorithms is used. To construct non-conflicting paths, a method that detects and solves collisions is developed. In the study, for agent communication Open Agent Architecture is used. Additionally, simulations on the MobileSim platform are conducted to verify the feasibility of the proposed method.