Abstract: AI planning is a promising method for Web service composition (WSC). But it encounters knowledge engineering bottleneck for there is no predefined action models for Web services (WS) in planning language under most circumstances. For example, using planning to find WSC solutions needs action models for WS, which is difficult for engineers to write. Considering that most existing WSC solutions are manually written in business process language for Web services (WSBPEL), it is preferred to learn action models from existing WSC solutions. In the mean time, WS may have multiple outcomes. For this non-deterministic nature of WS and the hidden semantic requirements for WS in existing WSC solutions, the corresponding action model for WS should be a non-deterministic action with condition effects and it should embody semantic requirements too. So firstly WSBPEL programs are translated into a labeled transition system (LTS). Then the scope of learning action models is extended into non-deterministic planning (NDP) with condition effects, and non-deterministic action models are learned from LTS. A system called ARMS-WS is implemented, and experimental results show that non-deterministic action models can be learned from WSBPEL programs. This work helps avoid writing planning description for existing Web services, and makes planning tools more applicable for real-world WSC problems.