Добавил:
Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
(EOD).Mechatronics.pdf
Скачиваний:
81
Добавлен:
23.08.2013
Размер:
5.07 Mб
Скачать

page 738

Figure C.4 Grid Representation of Space

1

2

3

Floor Layout

 

 

1

1

 

 

Maps to

 

 

 

 

1

1,2

2

 

 

 

 

 

 

 

 

 

 

 

 

 

 

3

3

 

 

 

 

 

 

 

 

 

 

3

3

 

 

 

 

 

 

 

 

Floor Layout Map

 

 

(by objects in cell)

This map only indicates an objects presence, the remainder of the information is kept in a concurrent list. By finding and using a series of holes and walls within the grid an A* search is applied to find the best path. The cost function of the search is based on the path length and the number of turns made. The performance of this method is not stated, and thus no basis for comparison is available. This method provides straight line path segments. The mapping to configuration space could be convenient for the first pass of a path planner for general path finding.

40.12 APPENDIX D - FIELD METHODS

In an attempt to model ’natural flow’, there have been attempts to use gradients and potentials to choose natural path choices. These methods use the equivalent of field representations to provide a direction of travel that is ’down hill’. These methods have long setup times, and they can get caught. These techniques will benefit the most as more powerful computer hardware becomes available.

40.12.1 SPATIAL PLANNING : STEEPEST DESCENT

In an attempt to find a fast path planning method, the steepest descent method was proposed by P.W.Verbeek, L.Dorst, B.J.H. Verwer, and F.C.A. Groen [1987]. Their method is an array based method which will take the workspace represented polygons. This array is a two dimension representation of space in which the goal position is represented with a zero value, and the objects are represented with a value of infinity. Each element of the array is considered in a series of iterations over the array. The result of these iterations is a map of a ’height’ with respect to the goal state. The method then just follows the steepest gradient, down to the goal state.

page 739

Figure D.1 Steepest Descent Representation and Path

start

A Distance Map

This method has been implemented for a 2D multilink manipulator, but it uses 4 Mbytes of memory for a workspace resolution of 32 by 32 by 32. On a 12 MHz, 68000 VME computer system the whole process takes about 12 seconds. This is broken up into a 6 seconds for detection and labelling of forbidden states, a 6 second generation of distance landscape, and less than a second for finding the shortest path by steepest descent.

40.12.2 SPATIAL PLANNING : POTENTIAL FIELD METHOD

When considering that the basic thrust of the path planning methods is to avoid obstacles, it is easy to compare this avoidance to repulsion. The basic concept of repulsion is based on potential fields, as thus the potential field method of W.T.Park [1984]. In particular, the method was directed towards a workcell with multiple manipulators. In this setting there is a problem with potential manipulator collisions, which must be considered when path planning. To do this a planar view of the work cell is created, and the arms are given a potential. The potential repulsion of the manipulators is mapped for a number of various joint and slider positions. In the work of Park, a manipulator with two revolute joints, and a Stanford manipulator is used. Both of the manipulators have two degrees of freedom, thus a number of two dimensional arrays are necessary to fully describe the work space. This memory requirement is very large, and thus is one of the drawbacks of this technique. The Even with the use of compression techniques, the arrays still consume over 100 KBytes each. In the experimental implementation, the computer used was a VAX 750. The problem was constrained to 4 d.o.f., which used 2 MBytes of memory, and took 8 hours of computation time, to calculate about a million combinations. This method may also get caught in cul-de-sacs. The bottom line on this method is it highly oriented to batch and workcell operations, but too staggering to consider for use in a practical system.

In a more complex vein, Y.K.Hwang and N.Ahuja [1988] have developed a method using polygons and polyhedra to represent objects, from which a potential field is generated. First

Соседние файлы в предмете Электротехника