One of the most important developments in the software industry in recent years has been the merger of the entertainment and educational software markets. An intriguing possibility for edutainment software is the introduction of intelligent life-like characters. By coupling inferential capabilities with well-crafted animated creatures, it becomes possible to create animated pedagogical agents that provide communicative functionalities with strong visual impact. We have developed the coherence-structured behavior space approach to creating animated pedagogical agents. This is a two-step approach. Firsti we design a behavior space of animation and audio segments that are structured by prerequisite relationships and a continuity metric. Second, we navigate coherent paths through the space to dynamically sequence behaviors. This creates seamless global behaviors that communicate fundamental knowledge and provide contextualized problem-solving advice. The coherence-structured behavior space approach has been implemented in "Herman the Bug," an animated pedagogical agent for DESIGN-A-PLANT, which is an edutalnment system for teaching students about botanical anatomy and physiology. Formative evaluations of Herman with middle school students are encouraging.