TL;DR
This paper introduces a data-driven "chunking parser" to automatically interpret spoken route directions into a structured route graph for robot navigation. The approach demonstrates robustness to speech recognition errors and can generalize to unseen concepts, making it a promising step towards more natural human-robot interaction.
What Problem Does This Paper Address?
As robots move into dynamic, real-world environments, they need to acquire knowledge that isn't pre-programmed. Human dialogue is a rich source of this information, particularly for tasks like navigation. However, understanding spoken instructions, especially when delivered in natural, unscripted ways and subject to speech recognition errors, is a significant challenge. Existing methods often struggle with the structured nature of route directions (e.g., understanding relationships between landmarks, directions, and actions) and generalizing to new concepts. This paper tackles the problem of converting spoken route directions into a usable, structured representation (a route graph) for robots, even when the speech recognition output is imperfect.
Methods
The core of the proposed solution is a "chunking parser" inspired by syntactic analysis. This parser has three main stages:
- Chunker: Identifies base concepts within the spoken instruction (e.g., "turn," "right," "at," "the post office"). This is framed as a classification problem where each word is assigned a chunk tag (e.g., B-ACTION, I-ACTION).
- Attacher: Takes the identified chunks and assigns more specific concepts (using a domain ontology) and links them as arguments. For instance, it can recognize "post office" as a specific type of LANDMARK and associate it with the "at" preposition. Crucially, it can also back off to more general concepts (e.g., LANDMARK for an unknown place) to handle unseen information.
- Segmenter: A newer addition, this component groups chunks into meaningful route segments, making the entire interpretation process more automatic.
The system uses machine learning algorithms like Naive Bayes and Linear Threshold Units (specifically Sparse Perceptron and Sparse Averaged Perceptron) trained on features derived from word instances, word windows, POS tags, and chunk labels.
Datasets
- IURO Project Data: Used in previous work, this dataset consisted of manually transcribed route instructions from a Wizard-of-Oz experiment.
- Instruction-Based Learning (IBL) Corpora: This is the primary dataset used for the extensions in this paper. It includes manual transcriptions and audio recordings of 144 spoken English route instructions given by 24 subjects in a miniature urban environment. This corpus contains filler pauses, self-corrections, and repetitions, making it realistic. A subset of 30 instructions was manually annotated for evaluation.
Key Insights and Ideas
- Robustness to ASR Errors: The data-driven approach, particularly the Attacher, shows remarkable resilience to errors in the Automatic Speech Recognition (ASR) output. Even with significant word errors, the system can still extract the core conceptual information.
- Generalization via Ontology: The use of a domain ontology allows the system to generalize. When encountering an unknown landmark (like "trees" in the example), it can fall back to a more general concept (LANDMARK) while preserving its role in the instruction.
- Structured Representation is Key: Unlike simple keyword spotting, the parser preserves the structural relationships between concepts (e.g., "turn right at the post office"), which is essential for accurate navigation.
- English vs. Swedish Morphology: Features that were informative for Swedish (a language with richer morphology) were less so for English, suggesting that language-specific feature engineering might be necessary for optimal performance.
Key Results
- Improved Performance: The Sparse Averaged Perceptron learner achieved a Concept Error Rate (CER) of 19.99% for the Attacher on transcribed English route instructions, a significant improvement over a baseline keyword spotting method (77.70%).
- Robustness Demonstrated: The relative CER (R-CER) remained relatively steady even with ASR errors (e.g., a WER of 25.02% resulted in an R-CER of 15.53%, comparable to the CER on perfect transcriptions).
- Segmenter Performance: While the Chunker and Attacher performed well, the automatic Segmenter's performance was not as strong, indicating that heuristic rules might still be needed for this task.
Limitations and Future Work
- Segmenter Improvement: The authors acknowledge that the automatic Segmenter needs further development, possibly requiring heuristic rules or better algorithms.
- Usability Evaluation: A crucial next step is to evaluate the practical usability of the generated route graphs by having subjects follow them in a simulated environment. This will help assess how well the robot can navigate based on the interpreted instructions.
- User Modeling and Dialogue Strategies: Understanding which concepts users find most useful in navigation can inform user modeling and the design of dialogue strategies for the robot, especially when it needs to ask for directions.
- Incremental Processing: Exploring the parser's performance with left-context only processing (for incremental dialogue) is also a future direction.
Summary updated