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.
Tanveer Abbas Bruce A. MacDonald
The University of Auckland, New Zealand
国际会议
2011 IEEE International Conference on Robotics and Automation(2011年IEEE世界机器人与自动化大会 ICRA 2011)
上海
英文
3816-3821
2011-05-09（万方平台首次上网日期，不代表论文的发表时间）