Web services are agents on the web that provide services to other agents. Interacting with a web service is essentially a planning problem, provided the service exposes an interface containing action definitions, which in fact is an elegant representation of how web services actually behave. The question is what sort of planner is best suited for solving the resulting problems, given that dealing with web services involves gathering information and then acting on it. Estimated-regression planners use a backward analysis of the difficulty of a goal to guide a forward search through situation space. They are well suited to the web-services domain because it is easy to relax the assumption of complete knowledge, and to formalize what it is they don’t know and could find out by sending the relevant messages. Applying them to this domain requires extending classical notations (e.g., PDDL) in various ways. A preliminary implementation of these ideas has been constructed, and further tests are underway.