Generalizing topological task graphs from multiple symbolic demonstrations in programming by demonstration (PbD) processes

Many programming by demonstration methods encode demonstrations into sequences of predefined symbols and then build a generalized task structure such as a topological graph. The longest common subsequence (LCS) algorithm is one of the potential techniques to help build generalized task structures from multiple sequences. However the LCS problem is NP hard, so a couple of suboptimal LCS approaches have been adopted in the past, involving a pair-wise comparison of sequences or a search for the common symbols within a small window. This paper argues that an LCS of multiple sequences results in a better generalization than pairwise comparison, and in many practical situations it is feasible to find an LCS of multiple sequences. So a novel LCS finding algorithm is presented for applications in the programming by demonstration domain. The algorithm has been extensively tested for sequences of random symbols and its application in a path planning example is presented.