Scenario-driven requirement specifications are widely used to capture and represent functional requirements. Use Case Maps (UCM) is being standardized as part of the User Requirements Notation (URN), the most recent addition to ITU-T?s family of languages. UCM models allow the description of functional requirements and high-level designs at early stages of the development process. Recognizing the importance of having a well defined semantic, we propose, in this work, a concise and rigorous formal semantics for Use Case Maps, defined in terms of Multi-Agent Abstract State Machines. The proposed formal semantics addresses UCM?s operational semantics and provides a sound basis for executing UCM specifications using simulation tools and supporting formal verification.