Applications of ai planning in genome rearrangement and in multi-robot systems

Abstract

Yapay zeka ile planlamada amaç, verilen bir ilk durumu bir hedef duruma ulaştırmakiçin, bir etmenin hareketlerini planlamaktır. Bu tezde, yapay zeka ile planlama iki tanezorlayıcı problemi çözmek için kullanıldı: işlemsel biolojiden genom düzenleme problemive çoklu-robot sistemlerinden ayrışık planlama problemi.Genom düzenleme problemi, motivasyonunu evrimsel ağaçlardan alır. Amacı, ikicanlının genomlarını karşılaştırarak aralarındaki en az sayıdaki genom düzenleme olayını(genomda oluşan büyük çaplı mutasyonlar) bulmaktır. Bu problemin tek kromozomludairesel genomlarla olan ve genomda bazı genlerin birden fazla kopyasının olmasına izinverilenini çözmek için adı GENOMEPLAN olan yeni bir method geliştirdik. Genomdüzenleme problemini bir yapay zeka ile planlama problemi olarak formüle ettik ve yapayzeka planlayıcısı TLPLAN'ı kullanarak planlar bulduk. İşlemsel verimi arttırmakiçin GENOMEPLAN'de hareket tanımları içine bir kaç çeşit buluşsal yöntem yerleştirdik.Gerçek veriler üzerinde daha kesin cevaplar alabilmek için GENOMEPLAN´da düzenlemeolaylarının ağırlıklarının veönceliklerinin tanımlanmasına izin verdik. GENOMEPLAN'inuygulanabilirliğini gerçek veriler üzerinde gösterdik.Çoklu robot sistemlerinde farklı çalışma alanlarında bulunan ve birden fazla robottanoluşan robot takımlarının, birbirleriyle robot alış verişinde bulunarak kendi hedeflerineen kısa zamanda ulaşmaya çalıstıklari bir problemi ele aldık. Bu problemi çözmek içintakimlar arasında uzlaşmayı sağlayıp en kısa planı bulan bir algoritmaöneriyoruz. Bualgoritmada, bir taraftan takımlar sadece kendi çalışma alanlarına ait planlar bulurken,diğer taraftan her takım merkezi bir sistemle iletişim kurup toplamda en kısa planı buluyorlar.Algoritmamızın doğru sonuç verdiğini ve olan bir sonucu kaçırmadığını ispatladıkve işlemsel karmaşıklığını analiz ettik. Metodumuzu akıllı bir fabrikaörneği üzerindegösterdik ve fabrikadaki bir çalışma alanını hareket anlatma dili C+ ile modelleyip nedenselakıl yürütücü CCALC'ın çalışma alanı hakkında akıl yürütmesine dairörneklersunduk.

In AI planning the aim is to plan the actions of an agent to achieve the given goals froma given initial state. We use AI planning to solve two challenging problems: the genomerearrangement problem in computational biology and the decoupled planning problem inmulti-robot systems.Motivated by the reconstruction of phylogenies, the genome rearrangement problemseeks to find the minimum number of rearrangement events (i.e., genome-wide mutations)between two given genomes. We introduce a novel method (called GENOMEPLAN) tosolve this problem for single chromosome circular genomes with unequal gene contentand/or duplicate genes, by formulating the pairwise comparison of entire genomes as anAI planning problem and using the AI planner TLPlan to compute solutions. The idea isto plan genome rearrangement events to transform one genome to the other. To improvecomputational efficiency, GENOMEPLAN embeds several heuristics in the descriptionsof these events. To better understand the evolutionary history of species and to find moreplausible solutions, GENOMEPLAN allows assigning costs and priorities to rearrangementevents. The applicability of GENOMEPLAN is shown by some experiments on realdata sets as well as randomly generated instances.In multi-robot systems, multiple teams of heterogeneous robots work in separateworkspaces towards different goals. The teams are allowed to lend robots to one another.The goal is to find an overall plan of minimum length where each team completesits assigned task. We introduce an intelligent algorithm to solve this problem. The idea is,on the one hand, to allow each team to autonomously find its own plan and, on the otherhand, to allow a central agent to communicate with the representatives of the teams to findan optimal decoupled plan. We prove the soundness and completeness of our decoupledplanning algorithm, and analyze its computational complexity. We show the applicabilityof our approach on an intelligent factory scenario, using the action description languageC+ for representing the domain and the causal reasoner CCALC for reasoning about thedomain.