One of the minimum requirements of an autonomous robot is the ability to plan its motions in order to achieve any given goal. This plan usually consists of a collision-free sequence of configurations that take the robot from its configuration to its goal. The problem is to find such a sequence.
Autonomous robots are expected to obey orders given in a way that could be very clear to a human being, but that in fact involves the solution of several problems. One of this problems is planning the activities and movements required to reach the goal given with little or no help of a human operator. Tasks that are easy for people are indeed very difficult for machines. Solving this problem is really important, by doing that it would be possible to have robots able to plan by themselves activities ranging from trivial to very complex, v.g. cleaning or painting arbitrarily complex surfaces or assembling parts of any kind of device without having to be reprogrammed every time the device changes or even walk in complex environments.
The must used approaches to solve this problem are Roadmaps and Potential Fields:
In this project I try a new approach: the use of light properties to help in finding a path for a robot. The idea is based on the behavior that people have when they want to get out from dark places. In this kind of situations people look for light sources and walk in the direction the light is coming from.
A robot can do the same by modeling its goal as a sort of "bulb". Some of the light rays emitted this "bulb" can eventually reach the robot. If it is possible to know where these rays are coming from the robot can reach its goal following the rays.
The original goals for this project were:
As far as I know there has not been any work using light properties to solve the motion planning problem. However, there is a lot of work related with path planning and ray tracing.
Latombe [1] defines the basic problem of planning in this way: given an initial position and orientation and a target position and orientation of a robot in certain workspace, a path specifying a continuous sequence of positions and orientations for the robot avoiding contact with the obstacles in the environment is searched. If there is no such a path the impossibility of solving the problem is reported.
Lozano-Pérez [2] introduced the configuration space as a tool to represent the workspace. The robot is treated as a single point in a space called the robot configuration space. The configuration space is formed by all the possible configurations of the robot and the obstacles in C-space, also called C-obstacles, allow to define collision-free configurations for the robot.
Roadmaps are graphs whose nodes are collision-free configurations and whose edges are collision-free paths between the nodes. The main problem with this approach is that to solve the basic problem of planning the whole configuration space has to be sampled, of course this is not possible in a reasonable time. Kavraki and Svetska [3] came up with a method that has been used successfully in many cases. In this method a probabilistic roadmap is constructed whose nodes are chosen randomly and checked to be collision-free. Once the graph has been built off-line it could be queried by connecting both the initial and goal configurations to it and doing a search with well-known techniques to search graphs.
This approach has its main handicap in regions considered difficult, mainly in narrow corridors where the probability of having enough free-collision nodes decreases. Amato [4] proposed a method to improve the roadmaps with a method that chose configurations on C-obstacle surfaces increasing the probability of having nodes in these difficult region. This method has had very good results in situations that other methods couldn't handle before.
In these methods the robot is considered a particle influenced by an artificial potential field whose local variations reflect the structure of the free space[5]. This is because they are made based on the obstacles and the goal of the robot. The early uses of this method were for navigation purposes when there were no previous model of the workspace more for generating efficient movements rather than trying to reach the goal.
The potential function is defined in such a way that its value doesn't depend on the form or distribution of the obstacles farther than a given distance from them to avoid expensive computations. The most common potential function is defined as the sum of an attractive potential that pushes the robot to the goal configuration and a repulsive potential that makes it go away from the obstacles. Planing is made through iterations in which the sum is computed and the next configuration is found by applying the result to the robot and finding the resultant configuration.
The main problem with this approach is the possibility of falling in local minima. This issue can be minimized by building a function without that tendency (hasn't been done so far for the general case) or by adding techniques to escape from local minima. Another problem is that it is likely that the method doesn't find any path even though the path exists. On the other hand, these methods are very fast.
Ray Tracing is used to render three-dimensional graphics by following the path that light takes as it bounces through a given environment. The goal is finding the color of each point in a view window that is the area in which the scene will be drawn, the points are got by subdividing the view window into small squares, each of them corresponding to a pixel in the image [6], [7].
In a scene with a bulb, it has to be decide how many rays it will shoot out and their direction. Some of these rays will reach the eye directly, others will bounce around and then reach the eye, and many more will never hit the eye at all. It is effortless to trace such rays. To avoid wasted effort only the rays guaranteed to hit the view window are traced, starting at the eye of the viewer and passing through the window into the scene. To calculate the color of a given pixel, each time the ray hits any surface the color is recomputed based on the color of the surface and the color stored previously for that ray.
Ray tracing considers also reflective and refractive properties of materials. If the object is transparent to some extent the ray is divided into two rays, one reflected and the other refracted into the surface, if the index of refraction of the materials on either side of the surface is different the refracted ray is bent.
To know the point of bouncing the intersection of the ray and the surface involved is computed with an intersection routine that returns the distance from the origin of the ray to the intersection point, the normal vector to the surface in that point and a the color produced by the bouncing.
There are many different ways to determine the color at a point. In flat shading every point has the same color, in other fairly complex techniques the physical attributes of the material are considered. One model used very often is known as Lambertian or cosine shading that determines the brightness of a point considering the normal vector at the point and the vector from the point to the light source. When tow vectors coincide the brightness is maximum, as the angle between the two vectors increases the brightness diminishes. this method is implemented with a cosine function. Some other techniques use the textures to compute the color of any given point in the object.
Radiosity or Secondary Illumination is the ability of a material to reflect light and become a second source of illumination. This effect can be seen when two objects of different colors are very close and their color seem to change slightly due to the effect of the influence of the color of the other. This effect is produced when light hits an object with certain color, must of the rays are absorbed by the material and get dissipated as heat vibration whereas the rays that have the same frequency of the color of the surface get into resonance causing the production of new photons that leave the surface making it a sort of light source. Ray tracing can not reproduce secondary illumination because it only traces rays, but it can model its effects by including photons with different frequencies on the ray. Once that a ray has been found it can be traced back to the eye considering the frequencies reflected and the frequencies absorbed by the materials and getting in this way the real color of the pixel.
The idea devised at the beginning of this report could be implemented entirely with a Ray Tracer, it doesn't require the use of Radiosity. However the Radiosity property of materials make me thing in a a way of improving the chance of finding a ray useful to connect to points, because if we see the objects as potential light sources in the point in which they are hit, we can improve the chances of getting useful rays to connect to points in the environment.
One thing I learned is that tracing a ray up to the source is almost impossible if I consider it as a single point. If instead of considering the source and goal as points they can be considered as spheres centered in the source and goal, the radius of this sphere could be the minimum clearance around the point. In this way the rays are traced until they hit the sphere or they have bounced too much. This is much more easier than trying to connect a single point.
I am using an Object Oriented Programming approach and C++ to implement it. I have the following classes:
The program takes two inputs: the environment and a query. These inputs are given in a file each. The environment file contains the characteristics of all the objects and the bounding box in the workspace. The query file has the parameters for the query including: maximum number of bouncings allowed for a single ray, maximum number of rays to try, maximum length for continue tracing each single ray generated and coordinates of the source and target for the point robot. Here I present an example of each file: testEnvironment.env
4 BoundingBox sphere 5.0 5.0 5.0 5.0 Globe1 sphere 2.0 6.0 4.0 4.0 Globe2 sphere 2.0 4.0 6.0 4.0 Globe3 sphere 2.0 4.0 4.0 6.0
In the environment example it is defined that there are 4 objects on it, the Bounding box is the 1st object, it is a sphere (not precisely a box) with center in (5,5,5) and radius 5. The objects are also spheres. testQuery.env
MaxBouncings 100 MaxRays 100 MaxRayLength 1000 Source 6.0 1.0 4.0 Target 6.0 7.0 4.0
In the query example it is defined that there are going to be checked up to 100 rays, each of them up to a total length of 100 (I didn't use units in my program, so it works with any unit system used as long it is consistent in all the data provided), the maximum number of bouncings checked for this ray is 100. The only limits in the program are the maximum number of bouncings it can handle and the maximum number of obstacles, because it stores them in an array of fixed length. The maximum number of bouncings internally allowed is 10000, and for the obstacles is 50. This situation can be fixed by storing them in linked lists.
The output of my program shows a list of the objects in the environment, the source and the target. Each object is followed by its characteristics. It also shows the length and number of bouncings of each ray shot. If no path was found it states it, otherwise it gives the sequence of bouncing points conforming a path. The following example illustrates this.
phere Globe1: position = (6,4,4), radius = 1 Sphere Globe2: position = (4,6,4), radius = 2 Sphere Globe3: position = (4,4,6), radius = 0.5 Sphere Globe4: position = (-4,4,-6), radius = 4 Sphere Globe5: position = (-4,-4,6), radius = 3 Sphere Globe6: position = (4,-4,-6), radius = 1.5 Sphere Globe7: position = (0,0,0), radius = 3.5 Sphere Globe8: position = (5,5,6), radius = 1 Sphere screen: position = (5,5,5), radius = 1 Sphere screen: position = (6,7,4), radius = 1 Ray number 1 tried, length = 1.44949, 1 bouncings. Path found in 0 seconds : Sequence: (5,5,5)[Source], (5.59175,6.1835,4.40825)[screen], (6,7,4)[`ű˙żÓTarget], 1 bouncings
I made a set of test cases to check the performance of my program. I made 3 environments and 5 queries. I applied each query to every environment. The following table is a summary of the results, by clicking in the links the files for environments, queries and results can be seen:
Queries 1, 2, and 3 are from Source (6.0 1.0 4.0) to Target (6.0 7.0 4.0). Queries 4 and 5 are from Source (5.0 5.0 5.0) to Target (6.0 7.0 4.0). When it is allowed to have more bouncings, the path is found faster, but the rays found have more bouncings also. There was just one query in wich no path was found.
More queries and environments to make conclusions and it is also necessary to add more types of objects to this planner, but the results got make me feel confident in that this technique could be used for planning motions for robots.
As it is said at the very beginning of this report, my original goals were:
The main outcome of this work has been the lots of ideas it gave me to address the problem of ray tracing that I state in the Future Work section.
The ray tracing can be done with points got in C-space or workspace, but in this moment I'll limit to do so in workspace because it is the best way to begin. Later it could be interesting trying to introduce C-space. It'll also be interesting to embed this ray tracer with a system using the roadmap approach to improve the graphs and trying to connect separate connected components in regions considered difficult. In addition, this technique could be considered a local-minima-free function for a planner using potential fields, but this is also left to other discussion.
Something that could be tried is shooting out rays from points in the surface of the objects in C-space (the rays are shoot in workspace, but are chosen in C-space) using a sort of radiosity.
Also, some work in enhancing paths has to be done. At first sight I think that the bouncing points could be used as control points for a Bezier continuous curve to have a continuous path instead of a set of straight lines. This could lead to an efficient path for the robot. From my observations I'm optimistic about the possibility of having as a result a free-collision curve that could be manipulated to make it as smooth as desired.
Use better data structures, avoid the use of fixed length arrays. In addition the program has to be tested thoroughly with many kinds of objects.
This project has been very exciting, it has given me lots of ideas I'm going to test undoubtedly. I'm really happy that an idea that at the beginning of the semester was completely vague is now an ongoing work that by this moment has given me many things to think about and hopefuly will lead to interesting results. I think that this approach could be useful both path planning, to what extent? it is still to be known.