In Carnegie Mellon University’s CyberScout project, we are developing mobile and stationary sentries capable of autonomous reconnaissance and surveillance. In this paper, we describe recent advances in the areas of efficient perception algorithms (detection, classification, and correspondence) and mission planning. In detection, we have achieved improved rejection of camera jitter and environmental variations (e.g., lighting, moving foliage) through multi-modal filtering, and we have implemented panoramic backgrounding through pseudo-real-time mosaicing. In classification, we present methods for discriminating between individuals, groups of individuals, and vehicles, and between individuals with and without backpacks. In correspondence, we describe an accurate multi-hypothesis approach based on both motion and appearance. Finally, in mission planning, we describe mapbuilding using multiple sensory cues and a computationally efficient decentralized planner for multiple platforms.