In the stream of research that aims to speed u p p r ac-tical planners, we propose a new approach to task planning based o n P r obabilistic Roadmap Methods (PRM). Our contribution is twofold. The rst issue concerns the development of ShaPer, a task planner that is able to deal eeciently with large problems. Shaper cap-turess the structure of the task space. The second contribution involves promising results on robot task planning. This is obtained t h r ough an analysis of the task space structure that exhibits the relation between task and geometric reasoning for a given robot task. To illustrate such an approach, we solve a complex problem where motion and task planning are closely interleaved. 1 Motivations Task planning has often used examples borrowed from robotics like, for instance, Pick&Place scenarii. However, the eeective use of practical task planners in robotics has always been limited to domains where it was possible to establish a clear and impermeable hierarchy b e t ween a high-level task planner and a lower level where geometric problems are dealt with. This is clearly insuucient if one wants to tackle realistic robotics problems. For instance, a plan for building a stack of objects may be substantially modiied if one adds an obstacle or changes the shape of the robott10, 8]. We h a ve proposed in the early nineties a geometrical formulation of the manipulation problemm2]. We formulated the problem as a series of motion planning problems in presence of movable obstacles. We s h o wed that it was possible to compute regions in the global connguration of the system where a grasp or a release action may cause a qualitative c hange in the topology of the free space allowing to access new states in the task space of a given manipulation problem. Such regions correspond to links between various "slices" of the global connguration spacee1]. While the formulation was satisfactory and gave a deep understanding of the manipulation problem, its eeective application has been limited to environments with a small number of degrees of freedomm1]. Indeed, we faced three problems. The rst one was due to the limitations of the motion planners of that (old) times. It was unrealistic to try to solve m o-tion problems with more than 3 degrees of freedom. The second problem was the absence of an operational link between task planning and motion planning. The third problem which w as also discouraging was the slowness of task planners. We are convinced that the recent and independent advances in motion and task planning have r e a c hed a level where it becomes realistic and fruitful to investigate the links between them and to devise paradigms that eeectively involve the two aspects in close relation and not simply through a gross and somewhat artiicial hierarchical decomposition. This paper is a rst step toward this goal. Even though task planners have made very substantial progress 3] o ver the last years, they are still limited in their use. There are also domains, like i n robotics which heavily innuence the structure of the task spacee learning such a structure will certainly help in building an eecient planner in a given domain. However, the structure of the environment (at least the usefull one) heavily depends not only on the environment but also on the actions that can be performed. Our aim is to develop a generic planner that will exhibit and learn the structuree of a given domain. This is the reason why w e propose to investigate approaches based on Probabilistic Roadmap (PRM). PRM basically capturess the space topol-ogyy through random connguration generation and connectivity t e s t s b e t ween states using a local planner. PRM obtains good results in robot path planning because it is relatively easy to test the validity o f a