In service-based systems, services from various providers can be integrated following specific workflows to achieve users? goals. These workflows are often executed and coordinated by software agents, which invoke appropriate services based on situation changes. These agents need to be deployed on underlying platforms with respect to various requirements, such as access permission of agents, real-time requirements of workflows, and reliability of the overall system. Deploying these agents manually is often error-prone and time-consuming. Furthermore, agents need to migrate from hosts to hosts at runtime to satisfy deployment requirements. Hence, an automated agent deployment mechanism is needed. In this paper, an approach to automated agent deployment in service-base systems is presented. In this approach, the deployment requirements are represented as deployment policies, and techniques are developed for generating agent deployment plans by solving the constraints specified in deployment policies, and for generating executable code for runtime agent deployment and migration.