We propose a novel method for generating test scenarios for a black box autonomous system that demonstrate critical transitions in its performance modes. In complex environments it is possible for an autonomous system to fail at its assigned mission even if it complies with requirements for all subsystems and throws no faults. This is particularly true when the autonomous system may have to choose between multiple exclusive objectives. The standard approach of testing robustness through fault detection is directly stimulating the system and detecting violations of the system requirements. Our approach differs by instead running the autonomous system through full missions in a simulated environment and measuring performance based on high-level mission criteria. The result is a method of searching for challenging scenarios for an autonomous system under test that exercise a variety of performance modes. We utilize adaptive sampling to intelligently search the state space for test scenarios which exist on the boundary between distinct performance modes. Additionally, using unsupervised clustering techniques we can group scenarios by their performance modes and sort them by those which are most effective at diagnosing changes in the autonomous system's behavior.