Adaptive planning in unknown environments using grammatical inference

This paper presents a framework that integrates grammatical inference with symbolic control on finite-state transition systems interacting with partially unknown, adversarial, rule-governed environments. We model the interaction between a system and its environment as a two-player zero-sum game on graphs. We show that with some prior knowledge of the environment, the system can autonomously infer a game equivalent to the one actually being played and thus successively adapt its control strategy in polynomial time, and evolve its controller into one that ensures the completion of the desired task, whenever such a completion is possible.