The US National Science Foundation has awarded a 3-year, $335,000 grant to Computer Science professors Samik Basu,Vasant Honavar, and Robyn Lutz. The Web services are beginning to play an increasingly important role in scientific, engineering, government, health-care, and business applications. Complex applications, e.g., in e-science cyberinfrastructure, call for tools that support users to assemble composite services from independently developed component services to achieve the desired functionality. This research aims to address this need by developing powerful interactive methods for service composition with provable guarantees with respect to user-specified functional and non-functional requirements. It will also provide enhanced opportunities for research-based training of graduate students. This research builds on the results of collaboration involving Jyotishman Pathak, a Ph.D. student in the Artificial Intelligence Research Laboratory, and the team of faculty with complementary expertise in formal methods, artificial intelligence, and software engineering, initiated with seed funds from the Iowa State University Center for Computational Intelligence, Learning, and Discovery.