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 paper, a concise and rigorous formal semantics for Use Case Maps (UCM). The proposed formal semantics addresses UCM's operational semantics and covers the key language functional constructs. These semantics are defined in terms of Multi-Agent Abstract State Machines that describes how UCM specifications are executed and eliminates ambiguities hidden in the informal language definition. The resulting operational semantics are embedded in an ASM-UCM simulation engine and are expressed in AsmL, an advanced ASM-based executable specification language. The proposed ASM-UCM engine provides an environment for executing and simulating UCM specifications. We illustrate our approach using an example of a simplified call connection.