This paper describes our methodology for building conformant planners, which is based on recent advances in the theory of action and change and answer set programming. The development of a planner for a given dynamic domain starts with encoding the knowledge about fluents and actions of the domain as an action theory D of some action language. Our choice in this paper is AL – an action language with dynamic and static causal laws and executability conditions. An action theory D of AL defines a transition diagram T(D) containing all the possible trajectories of the domain. A transition 〈s,a,s′〉 belongs to T(D) iff the execution of the action a in the state s may move the domain to the state s′. The second step in the planner development consists in finding a deterministic transition diagram Tlp(D) such that nodes of Tlp(D) are partial states of D, its arcs are labeled by actions, and a path in Tlp(D) from an initial partial state δ0 to a partial state satisfying the goal δf corresponds to a conformant plan for δ0 and δf in T(D). The transition diagram Tlp(D) is called an ‘approximation’ of T(D). We claim that a concise description of an approximation of T(D) can often be given by a logic program π(D) under the answer sets semantics. Moreover, complex initial situations and constraints on plans can be also expressed by logic programming rules and included in π(D). If this is possible then the problem of finding a parallel or sequential conformant plan can be reduced to computing answer sets of π(D). This can be done by general purpose answer set solvers. If plans are sequential and long then this method can be too time consuming. In this case, π(D) is used as a specification for a procedural graph searching conformant planning algorithm. The paper illustrates this methodology by building several conformant planners which work for domains with complex relationship between the fluents. The efficiency of the planners is experimentally evaluated on a number of new and old benchmarks. In addition we show that for a subclass of action theories of AL our planners are complete, i.e., if in Tlp(D) we cannot get from δ0 to a state satisfying the goal δf then there is no conformant plan for δ0 and δf in T(D).