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

Official URL: http://192.168.1.20/record=b1378270 (Table of Contents)

In AI planning the aim is to plan the actions of an agent to achieve the given goals from a given initial state. We use AI planning to solve two challenging problems: the genome rearrangement problem in computational biology and the decoupled planning problem in multi-robot systems. Motivated by the reconstruction of phylogenies, the genome rearrangement problem seeks to find the minimum number of rearrangement events (i.e., genome-wide mutations) between two given genomes. We introduce a novel method (called GENOMEPLAN) to solve this problem for single chromosome circular genomes with unequal gene content and/or duplicate genes, by formulating the pairwise comparison of entire genomes as an AI planning problem and using the AI planner TLPlan to compute solutions. The idea is to plan genome rearrangement events to transform one genome to the other. To improve computational efficiency, GENOMEPLAN embeds several heuristics in the descriptions of these events. To better understand the evolutionary history of species and to find more plausible solutions, GENOMEPLAN allows assigning costs and priorities to rearrangement events. The applicability of GENOMEPLAN is shown by some experiments on real data sets as well as randomly generated instances. In multi-robot systems, multiple teams of heterogeneous robots work in separate workspaces 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 completes its 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 other hand, to allow a central agent to communicate with the representatives of the teams to find an optimal decoupled plan. We prove the soundness and completeness of our decoupled planning algorithm, and analyze its computational complexity. We show the applicability of our approach on an intelligent factory scenario, using the action description language C+ for representing the domain and the causal reasoner CCALC for reasoning about the domain.