Realistic motion of virtual characters is a crucial factor for the reality and immersiveness of an AR application. Motion graph-based approach allows for generating infinitely many types of motions and may create remarkably realistic human motion from a limited set of motion data. In this paper, we present a method to efficiently search the motion graph using A* search algorithm in an AR environment. Specifically, we introduce three types of heuristic functions: the distance, previewed distance, and directional heuristic functions. The proposed heuristic functions reduce compute time significantly while not sacrificing the quality of motion. We demonstrate the effectiveness of our method by implementing an interactive AR application.