This area is a mature field in robotics research: during the last three decades motion planning has established itself as an important area of robotics. In addition, it has traditionally only dealt with simulations, ignoring the problems of working with real robot implementations. These facts should make it particularly amenable for benchmark developing, since the only hardware involved is a computer. In spite of its progresses and maturity, motion planning has achieved limited success, so far, in terms of widespread penetration into industrial applications. One of the reasons might have been the difficulty in comparing the performance of the existing motion planning techniques and in assessing their suitability for the problem at hand. Consequently, the need for benchmarks is acknowledged in the community because usually it is difficult to compare the different techniques since they are tested by solving a limited set of specific examples on different types of scenes, using different underlying libraries, incompatible problem representations, and implemented by different people on different machines. This area has also been suggested by the EURON research roadmap, since motion planning is crucial both for advanced production systems and household robots.
There is a general agreement that efforts should therefore be devoted in the development and dissemination of open, standardized benchmarks and performance assessment methodologies. Even so, it is felt in the MP community that this is a very difficult issue because whether a method is good depends on a large number of factors, often defined by the application in which the method is being used.
This is, indeed, a long standing problem. Hwang and Ahuja [92], in their famous survey, already urged motion planning researchers to develop a set of realistic and non-pathological benchmark problems. This need was later highlighted by Gupta and del Pobil [98]. After a decade of significant advances in motion planning, no common set of benchmarks is available yet. Rather, the effectiveness of each tool is measured by means of a specific set of problems, which however cannot be shared by any other tool due to incompatible or proprietary formats and characteristics. A limited exception to this situation has been the alpha puzzle, a benchmark for narrow passage problems proposed by the Parasol motion planning group, though in the opinion of others, this would rather exemplify a disease called puzzlitis: according to which, the most obscure case within the domain is picked as a criteria for successful research, in order to show generality, even though the puzzle problem itself is very unlikely to ever be encountered in practice [Brooks 90], whereas other more practical issues are abstracted.
As an example of this state of affairs in the context of the probabilistic roadmap approach, which is a commonly used motion planning technique, Geraersts and Overmars [04], in a recent study, compared 12 sampling techniques which is a critical component of this approach. For the comparison they used a single environment on the same scenes. Their results were surprising in the sense that techniques often performed differently than claimed by the designers. The study also showed how difficult it is to evaluate the quality of the techniques. It is expected that these results and other to come should help users in deciding which technique is suitable for their situation.
Another interesting work in this regard is that of Reggiani et al. [02]. It is a well know fact that randomized motion planners are greatly affected by the efficiency and robustness of algorithms for collision checking of robot configurations, even though the examples typically used tend to simplify this point. A number of powerful collision detection algorithms are currently available, but their relative capabilities and performance cannot be easily compared due to the many factors involved. In this work, collision detection packages were experimentally evaluated within the context of motion planning for rigid and articulated robots in 3D workspaces. Artificial and realistic problems were chosen as benchmarks to assess package behaviour with different object models.
An initiative toward the development of an interchange format for motion planning problems has been in progress. The participants in the discussions felt that the development of sharable benchmarks could not be achieved in just a few months but rather it was expected to be a long process. A primary goal in this process should be to identify input format requirements of existing tools and, based on this assessment, define common concepts and terminology.
Some considered that defining open, standardized benchmarks offers several benefits since they can give immediate insight when developing new planners, improve the understanding of strengths and weaknesses of existing planners, and they can be usefully exploited for educational purposes. Furthermore, benchmarks designed from industrial cases could inspire new research directions and contribute to increase the impact of planning tools.
It was agreed that given the usefulness and desirability of a set of benchmarks for the research community, the key issue of designing appropriate and sound benchmarks should be addressed. However, among the identified difficulties it can be mentioned that defining an adequate taxonomy for motion planning problems is quite complex because problems can be varied along several dimensions: problems could be classified either by workspace complexity (presence of narrow or wide corridors, geometric representation of obstacles), or C-space dimension, robot type (kinematic chains, closed kinematic chains, non-holonomic robots), etc
Assuming the availability of a set of benchmarks, still, there are other problems to be faced. Defining what should be compared is more tough than expected. Computation time for a given problem complexity has been the typical metrics for motion planning and collision detection algorithms, but the time required to find a solution is often less important than the solution quality. Moreover, quality is difficult to measure: the best solution could be the shortest, or the smoothest, or the most human-like depending on the problem requirements. Currently, other metrics are being considered such as those based on coverage and connectivity, rather than on the time it takes to solve some particular queries.
Another problem is that obtained results are vitiated by the large dependency of the tools on implementation details and exploited libraries, such as collision detection packages. A final issue regards the benchmark representation using the proprietary file format of the tools: when converting a format into another some parameters might get changed causing the problem itself to change.
There are a number of initiatives aiming at defining a format for motion planning since the definition of sharable benchmarks cannot be achieved without a broadly accepted interchange format for the description of the robots, the workspace and the problem. Some of the requirements of a suitable interchange format were identified. The format should be human-readable (self-explaining and simple to use), flexible (able to describe several kind of robots and obstacles), validable (easy to check data consistency and coherence) and extendible (easy to scale to future needs).
Two remarkable experiences in defining an input format for motion planning applications have been developed: First, Utrecht University has proposed the input format to be used with their application Callisto, which is a library to visualize 3D virtual environments that is specifically suited to support research on Probabilistic Road Maps (PRM's). It consists of a visualization environment based on Maverik and it uses Solid for collision checking. The input format used to describe scenes in Callisto is based on XML. A DTD defines the structure and the tags of the XML files that describe the workspace, the robots and the problem.
An XML-based input format has also been proposed by the University of Parma. As the research group of Parma uses motion planning techniques for different applications, such as the control of mobile manipulators and programming by demonstration, the need of an easy to use, self-describing and flexible format to share problems among them raised. The structure, content and semantics of valid XML files describing the robots and the workspace are defined by a set of XML-Schema documents. A Java3D tool to visualize motion planning scenario that uses the XML format is also part of the system.
There has been an on-going discussion in the MP community as a first step toward format structure and requirements elicitation. The most challenging issue was recognized to be problem description. Currently, most of the formats specify the final goal through the definition of d.o.f. values for the robots. This has proven to lack in flexibility, indeed, it does not allow a higher level approach focusing on task goals instead of position goals.
The suitability of XML as the technology to define an interchange format was highlighted. The choice of a markup language is motivated by their common use in storage, transmission and exchange of information, as they allow the description in a standardized format of data or information contained in text. XML has already proven to conveniently describe various types of structured data, as demonstrated by a growing number of XML-based languages in a wide range of domains. XML documents are human-readable, self-described, easy to maintain while guaranteeing interoperability. Moreover, they can be easily extended and several tools to parse them are freely available. In particular, the structure of an XML document allows the reader to efficiently skip unsupported information. A comprehensive interchange format can be designed still guaranteeing interoperability with several applications as unsupported information (for example texture and color of geometric objects) can be easily ignored.
Another issue that has also been discussed is that of establishing a common geometric format to be used in the exchange format. As most of the currently available collision detection packages employ triangulated objects, a triangulated format could seem a sound choice; but the problem of dealing with different geometric representations such as CSG or nurbs (the latter frequently used in industrial applications) would still remain open.
Assuming a unique format should be chosen, VRML was proposed as a suitable candidate format for geometry representation since a triangulated representation can be easily obtained from a VRML model. Moreover, VRML is widely supported by several tools, it is general and versatile to allow description of a wide variety of objects, it supports non-strictly-geometrical information such as texture and color, and a number of models are already freely available on the Web.
An initiative for a repository for motion planning benchmark problems is maintained by the University of Parma It aims at including benchmarks designed by different research groups and documentation describing the file formats currently used by the available planning tools to define their problems. Also, links and useful information regarding motion planning research projects are available. The repository is intended to serve as the basis for further discussion on the requirements and the design of benchmarks in motion planning.
The data sets follow the so-called Motion Planning Markup Language (MPML), an XML-based input format that has been proposed by the University of Parma, in such a way that the structure, content and semantics of valid XML files describing the robots and the workspace are defined by a set of XML-Schema documents. A Java3D tool to visualize motion planning scenarios that uses the XML format is also part of the system.
The repository (which can be found here) includes data sets about: robots, workspaces and benchmark problems
Similarly, the so-called Movie Models for Motion Planning is intended as a repository of motion planning benchmarks maintained by Utrecht University. It originated from work in the context of the Movie project in which motion planning techniques were developed and tested by using tools and 3D models of robots and scenes. Then they were opened to the community at large in model collections providing easy interface and search functionality, as well as useful information about the models, in such a way that new models could be easily added by researchers around the world. Specification formats for the robots and scenes are a critical issue for the widespread acceptance and use of the models. Current file formats are:
This repository can be found here.
Also additional technical information can be found in the followings documents: " Models for motion planning.pdf " and " Motion planning benchmarks.pdf "; .
On Experimental Research in Sampling-based Motion Planning, by Roland Geraerts, included in the document Lecture Notes of the IROS'06 Workshop on Benchmarks in Robotics Research.
Motion Planning vs. Automated Planning in Benchmarking, by M. Reggiani and E Pagello, in the Lecture Notes of the IROS'07 Workshop on Benchmarks in Robotics Research.