back icon
close icon

Capture phrases in quotes for more specific queries (e.g. "rocket ship" or "Fred Lynn")

Conference Paper  January 1, 2017

Approximate Graph Matching for Mistake-tolerant Skill Assessment

SRI Authors Melinda Gervasio, Karen Myers



Melinda Gervasio and Christian Jones and Karen Myers. Approximate Graph Matching for Mistake-tolerant Skill Assessment, in Advances in Cognitive Systems, vol. 5, 2017.


This paper presents an approach to automated assessment for online training based on approximate graph matching. The algorithm lies at the core of two prototype training systems that we have built in accord with U.S. Army training materials: one for the use of a collaborative visualization and planning tool, the other for rifle maintenance. The algorithm uses approximate graph-matching techniques to align a representation of a student response for a training exercise with a predefined solution model for the exercise. The approximate matching enables tolerance to learner mistakes, with deviations in the alignment providing the basis for feedback that is presented to the student. Given that graph matching is NP-complete, the algorithm uses a heuristic approach to balance computational performance with alignment quality. A comprehensive experimental evaluation shows that our technique scales well while retaining the ability to identify correct alignments for responses containing realistic types and numbers of learner mistakes. Keywords: Artificial Intelligence, Artificial Intelligence Center, AIC

How can we help?

    Once you hit send…

    We’ll match your inquiry to the person who can best help you. Expect a response within 48 hours.

    Our Privacy Policy