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

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