How to interface a human operator and a Motion Planning Algorithm

Abstract

In this work1, we present an application of motion planning to interaction with a virtual character or robot. The work is made in the context of moving an object from an initial place to a goal.

-

A lot of work in motion planning has been done to compute free paths in digital models for virtual or mechanical systems. This eld started with the piano mover's problem which was \how to move a piano from its initial place to another place, avoiding obstacles". Most of Motion planning algorithms compute a collision free roadmap in a con guration space (CS) where the object is reduced to a point. This point represents the robot's model in the environment and the dimension of CS is equal to the number of degrees of freedom of the mechanical system. The algorithm searches a free path for a point in the roadmap.

One example of applying motion planning techniques in real studies is in the maintenance and operation of nuclear power stations [ 9, 8 ].

One of the principal way for solving motion planning problems are deterministic algorithms. The main idea is to construct an explicit and accurate representation of the workspace in the con guration space. Algorithms such as cell decomposition methods or visibility graphs works ne for simple problems (usually with less than six dimensions for the CS). If CS has more than six dimensions, the complexity and the computation time increase signi cantly. For problems with more dimensions (like humanoid robots), newer and more e cient methods are used.

These methods are called sampling-based. They avoid the explicit construction of CS by building an approximate representation of it under the shape of a graph. With the recent results in sampling-based planning algorithms [ 6 ] it is possible to solve automatically problems for systems with a large number of degrees of freedom.

There are mainly two families of methods for building a graph, the roadmap methods such as the Probabilistic Roadmap planner (PRM) [ 3 ] and the Tree methods like RRT [ 7 ]. The PRM is a typical multiple query method. The main idea is to sample randomly con guration in CS, keep only free con gurations (a 1 This work was partially supported by the AMSI project nanced by the ANR. collision detector will say if a con guration is colliding) and try to connect the sampled con gurations by a free local path. The result is a global roadmap graph that captures the connectivity of the free CS. Many extensions were proposed to resolve various problems of motion planning (closed chains, non-holonomic robots, human motion, digital actor).

The RRT approach was originally proposed by Lavalle in [ 5 ]. Its main di erence with PRM is that it doesn't try to map the CS entirely, but tries to reach the goal con guration as soon as possible. To do so, a new free con guration is added to the graph only if a free local path can be built from the nearest node in the graph in the direction of the sampled con guration. An interesting variant is the bidirectionnal RRT algorithm [ 7 ] which uses bidirectional expansion strategy between two trees (one rooted at the start and the other at the goal). Again, multiple extensions were developed to resolve various motion planning problems (closed chains, kinodynamic and non-holonomic robot, PLM [ 2 ]). 2

Interactive Devices

Recently, new kinds of peripheral devices that allow users to interact in a more natural way with machines were developed. These various devices such as space mouse or haptic arm ( gure 1.b) can be used to improve motion planning algorithm with a natural user input, thus speeding-up path computation. A space mouse is a kind of mouse that can move in three dimensions, and even with orientation, the drawback is that the user has no feedback from the machine. This is done by haptic arms, which can send back forces and torques to the user. 3

Interactive Motion Planning Algorithms

In [ 1 ] the authors use user-input to work with automatic motion planner. They show that randomized techniques are really useful to transform an approximate user-input path with collisions into a collision free path. The idea is to push an approximate user path that can collide with obstacles into free space in CS. The user rst draws a path that he thinks is good (without any collision detection, meaning that this manual path can collide with obstacle), and then, in a second step, an algorithm modi es this path to avoid collisions.

In [ 10 ] was introduced the use of a path planning technique based on harmonic functions to generate guiding forces that aid a user in a virtual environment. The idea is to compute a solution channel by cell decomposition that connects the initial and the nal con guration. Then, two harmonic functions are computed over the CS to nd a guiding path.

An RRT Algorithm including heuristics based on a study of the workspace is presented in [ 4 ]. The idea is to discretize the workspace using an unbalanced octree decomposition and generate a free continuous volume between initial and nal con guration using A . In a second time a free path for the object is computed by using RRT approach. 4

Interactive RRT

The idea of the I-RRT is to take advantage of both human and computer capabilities for planning a motion into a virtual scene. While previously described interactive algorithms use a two-step decomposition, the I-RRT integrate the user input directly into the planning loop. For this purpose, human and computer must cooperate in an e cient way along the process. We choose to integrate the human into the planning loop via an I-Device (see Figure 1.a). The user can thus act on the search, showing areas to explore or to go through. On the other side, the algorithm can gather information while exploring the scene (independently from the user's input) and display them visually or/and haptically. We use our algorithm to resolve industrial cases such as removing a silencer from a car (Figures 1.b and 2.b). 5

Interactive Character Animation

Here, the goal is to make a virtual character or a robot do a speci c task in a virtual world. The user leads the task execution through an interaction device and then, the motion planner takes care of everything else. That means, the user can only give an input up to six degrees of freedom, and the motion planner modify other degrees of freedom to move the character or the robot accordingly to the user's input.

For example, a typical use can be to make a character move a fridge or a cumbersome object from one place to another. The user guides the bounding box of the system while the motion planner is computing every degrees of freedom of the character to make him walk and move the object.

This is a part of our work in progress, rst results will be presented at the workshop.

References

1. O. B. Bayazit , G. Song, and N. M. Amato . Enhancing randomized motion planners: Exploring with haptic hints . In Int. Conference on Robotics and Automation (ICRA'2000) , pages 529 {536, april 2000 .

2. E. Ferre and J. Laumond . An iterative di usion algorithm for part disassembly . In Int. Conference on Robotics and Automation (ICRA'2004) , pages 3149 {3154, april 2004 .

3. L. E. Kavraki , P. Svestka , J.-C. Latombe , and M. H. Overmars . Probabilistic roadmaps for path planning in high-dimensional con guration spaces . IEEE Transactions on Robotics & Automation , 12 ( 4 ): 566 { 580 , June 1996 .

4. N. Ladezeve , J. Y. Fourquet , and M. Taix . Interactive motion planning in virtual reality environments . In Virtual Reality International Conference (VRIC'08) , april 2008 .

5. S. M. LaValle . Rapidly-exploring random trees: A new tool for path planning . Technical Report 98-11 , Computer Science Dept., Iowa State University, oct 1998 .

6. S. M. LaValle. Planning Algorithms . Cambridge University Press, Cambridge, U.K., 2006 . Available at http://planning.cs.uiuc.edu/.

7. S. M. LaValle and J. J. Ku ner. Rapidly-exploring random trees: Progress and prospects . In Proceedings Workshop on the Algorithmic Foundations of Robotics (WAFR'00) , 2000 .

8. T. Simeon , R. Chatila , and J. Laumond . Computer aided motion for logistics in nuclear plants . In Int. Symposium on Arti cial Intelligence , Robotics and Human Centered Technology for Nuclear Applications (AIR'02) , pages 46 {53, january 2002 .

9. T. Simeon , J.-P. Laumond , C. V. Geem , and J. Cortes . Computer aided motion: Move3d within molog . In Int. Conference on Robotics and Automation (ICRA'2001) , pages 1494 {1499, may 2001 .

10. C. Vazquez and J. Rosell . Haptic guidance based on harmonic functions for the execution of teleoperated assembly tasks . In IFAC Workshop on Intelligent Assembly and Disassembly , May 2007 .