Çoklu robot s?stemler?nde d?nam?k zamansal planlama
Dynamic temporal planning for multirobot systems
Yazar: CELAL UĞUR USUĞ
Danışman: YRD. DOÇ. DR. SANEM SARIEL TALAY
İstanbul Teknik Üniversitesi / Fen Bilimleri Enstitüsü / Bilgisayar Mühendisliği Ana Bilim Dalı
Derece: Yüksek Lisans, 2011
Konu: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol = Computer Engineering and Computer Science and Control
Dizin: Plan değişikliği = Plan alteration ; Planlama = Planning ; Robot sistemleri = Robot systems ; Robotik = Robotics ; Robotlar = Robots ; Çizelgeleme = Scheduling

Özet:
Gezgin robotların birbirlerine bağımlı ve karmaşık görevleri etkin şekilde yürütebilmesi için otonom eylem planlama yöntemlerinin kullanılması gerekir. Fakat gerçek dünya kısıtlarını karşılayabilmek için planlama problem tanım kümesini (domain) gerçekçi olarak temsil etmek muazzam bir çaba gerektirir. Bu yüzden gezgin robot sistemleri için eylem temsillerini (örneğin etki ve önkoşullarını) tüm durumlarda en mükemmel şekilde temsil edememek bir başka belirsizlik kaynağı teşkil etmektedir. Tanım kümesi temsili tam ve eksiksiz olmadığında, bir planlayıcı dinamik gerçekleşebilecek olaylar karşısında aslında mümkün olmasına rağmen geçerli bir plan üretemeyebilir.Bu çalışmada gerçek-zaman yürütme hatalarına karşı alternatif planlar üretmek için tanım kümesi güncelleme metodları üzerine odaklanılmıştır. Sınırlı bir arkaplan bilgisinde dahi güncellenmiş tanım kümesi temsiline dayalı yeni bir yürütülebilir plan oluşturulması hedeflenmiştir. Bu amaçla önerilen yöntemlerle, plan onarma için gerekli operatörler, ortamda yönlendirici uzmanlar olmadığı durumlar için de, var olan tanım kümesi temsili ile geçerli plan bulmak mümkün olmamasına rağmen alternatif planlar üretilebilir. Hatalar yürütme anında veya yürütme öncesi simülasyon sürecinde tespit edilir. Problemin çoklu robot düzeyine çekilmesi durumundaki çözümün kalitesinin artırımını sağlamak, problemi zamansal açıdan ele almayı gerektirmiştir. Bu da problemi zamansal açıdan çözmeyi sağlayabilen zamansal planlayıcıyı ve buna uygun bir sistemin oluşturulmasını gerektirmiştir.Önerilen yöntemler biribirleri arasında ve ara hedef planlama ile bir dizi deney kümesi için karşılaştırılmıştır. Temel planlayıcı olarak TLPlan zamansal planlayıcısı kullanıldığından robotların varolan bilgileri ile toplam plan süresi eniyilemesi başarılmıştır. Gerçekçi çoklu robot simülatörü Webots ve TLPlan planlayıcısı ile haberleşen merkezi bir dinamik zamansal planama sistemi yapısı inşa edilmiştir. Gezgin robotları içeren bir hata çözme senaryosu Webots simülatöründe verilmiştir.

Abstract:
The use of automated action planning techniques is essential for efficient mission execution of mobile robots. However, a tremendous effort is needed to represent planning problem domains realistically to meet the constraints of real-world action execution. Therefore, there is another source of uncertainty for mobile robot systems due to the impossibility of perfectly representing action representations (e.g., preconditions and effects) in all circumstances. When the domain representations are not complete, a planner may not be capable of constructing a valid plan for dynamic events even when it is possible.Robots may take on missions under time constraints. To overcome time constraints temporal planners must be used. Temporal planners, capable of generating efficient sequences of durative actions, are convenient to be used with real robot missions. There have been significant advances in devising efficient temporal planners for continually enhanced benchmark planning domains. However, these algorithms operate at a high level and are not completely capable of dealing with hardware or physical environment limitations. In particular, real world is partially observable and involves different sources of uncertainty due to noisy sensor information, unexpected outcomes of actions and failures.This research presents a dynamic temporal planning framework for mobile robots to handle action failures due to environmental issues. Different from earlier studies, the presented solution constructs alternative plans even when guidance by experts, relevant new information or repairing operators for replanning is not available. Real outcomes of existing operators may not be completely known in advance (e.g., due to abstraction) or valid plans are not possible with the existing representation of the domain.The proposed framework includes three domain update procedures that provide flexible reasoning tools to replan accordingly for the resolution of a failure by using the intuitive principle of locality of failure. Failures are detected either during runtime or earlier by a plan simulation process. Background knowledge needed for updating the existing domain operators is almost negligible and a generic approach is applied by searching for effects in existing operators that may resolve the failure. After the required domain updates are performed, a replanning approach is employed as opposed to repairing since makespan (near-) optimal solutions are targeted (Cushing, Benton and Kambhampati 2008). TLPlan (Bacchus and Ady 2001) is used as the forward chaining temporal planner in the system to construct makespan-optimized plans. Low and high-level planning procedures of the robot system are made compatible by using efficient domain (e.g., map) representations.A centeral dynamic temporal planning system communicating with both the realistic Webots simulator and TLPlan temporal planner is constructed. Experiments are conducted to compare the three presented domain update approaches and the subgaol planning method on specific problem sets with two failure scenorios. A failure resolution scenario is given in the Webots simulator with mobile robots.