Chapter 5
Automatic Spatial Planning
Abstract
Automatic spatial planning, i.e. automatic robot planning, is discussed as one of the applications of quotient space theory. We pay attention to how the theory is applied to the problem, and how multi-granular computing can reduce its computational complexity.
General automatic generation of assembly sequences is very complicated. Based on the hierarchical quotient space model, we present a monotonic planning algorithm. For a product, by compressed decomposition along some (disassembly) direction, the product is decomposed into sub-assemblies and parts. By successively compressed decomposition, the product is finally decomposed into a hierarchical tree structure. The assembly of the product simply goes on from bottom to top along the tree. Therefore, the computational complexity is reduced.
In automatic motion planning, i.e. collision-free paths planning in robotics, we present a topology-based model. In the model, the problem is first treated in some coarse topological space by ignoring the geometric details, after that we go deeply into the details of the physical space in some region that contains the potential solutions. Since the less-promising regions have been pruned off in the first step, the computational complexity can be reduced by the strategy. The estimation of the computational complexity and the applications of the method, such as multi-joint arm motion planning, are discussed.
Keywords
assembly sequences; characteristic network; compressed decomposition; configuration space; motion planning; rotation mapping graph (RMG); spatial planning; topological modelChapter Outline
5.1 Automatic Generation of Assembly Sequences
5.1.4 Computational Complexity
5.2 The Geometrical Methods of Motion Planning
5.2.1 Configuration Space Representation
5.2.2 Finding Collision-Free Paths
5.3 The Topological Model of Motion Planning
5.3.1 The Mathematical Model of Topology-Based Problem Solving
5.3.2 The Topologic Model of Collision-Free Paths Planning
5.4 Dimension Reduction Method
5.5.1 The Collision-Free Paths Planning for a Planar Rod
5.5.2 Motion Planning for a Multi-Joint Arm
To illustrate the applications of our theory, some topics of automatic spatial planning, i.e., automatic robot planning will be discussed in this chapter. We will pay attention to how the theory is applied to these problems, and how multi-granular computing can reduce the computational complexity.
The ability to reason about actions and their effects is a prerequisite for intelligent behavior. AI planning is to construct plans by reasoning about how available actions can be applied to achieve given goals. In robotic assembly, there are two kinds of planning. One is the derivation of an ordered sequence of actions that can be used to perform the assembly task. It is usually called task planning. For a robot to execute a sequence of actions, it must be provided with motion commands that will affect these actions. In general, motion planning deals with determining a path in free space, along with an object that can be moved from its initial position to a desired destination. This is the second kind of robot planning known as motion planning.
In this chapter, only the above two specific topics of robot planning rather than the whole field are addressed.
5.1. Automatic Generation of Assembly Sequences
5.1.1. Introduction
As industrial robots come into wider use in assembly applications, interest in automatic robot program generation for assembly tasks is growing. The choice of the sequence in which parts or subassemblies are put together in the mechanical assembly of a product can be stated as follows.
Given a product W consisting of N parts, to find an assembly sequence automatically such that all assembly requirements such as geometrical, technological constraints, etc. are satisfied.
An assembly planning problem begins with each part in separation. The goal is to move them all into a given final configuration. For a product with N parts, the total number of all possible permutations of N parts is N!. Since different kinds of subassemblies can be used in the assembly process so that the total number of all possible combination of N parts will be (2N-3)!! For example, as shown in Fig. 5.1, product W consists of parts 1, 2, 3 and 4. There is no such assembly sequence that only one part is moved at a time in the plane. If subassemblies are used, then we may have assembly sequences. For example, parts 1 and 4 are combined into a subassembly (1,4), and parts 2 and 3 into a subassembly (2,3) first. Putting subassemblies (1,4) and (2,3) together, then we have the final product. Therefore, the derivation of assembly planning is hard.
Assembly plans can be classified into several kinds. In sequential plans the assembly motion can be divided into a finite sequence of steps such that at any moment all moving parts are moving along the same trajectory. However, some plans cannot be built this way, since it requires that at least two parts be moved simultaneously in different directions. A monotonic plan is a sequential plan in which parts are always moved directly to their final positions. A linear plan is a sequential plan in which there is only one part moving at a time.
Since general assembly planning is very complicated, so far much work having been done is limited to some specific kind of plans. Moreover, most planning systems consider only rigid motions, in which the parts are not deformed, and assume that each disassembly task of a product is the inverse of a feasible assembly task of the same product.
Mello and Sanderson (1989a, 1989b) presented a monotonic sequential assembly planning algorithm. The algorithm is complete and its computational complexity is 
, where N is the number of parts composing the product. Wolter (1989) presented a linear monotonic assembly planning algorithm called XAP/1. Its complexity is 
. These algorithms confront with exponential explosion in their computational complexity.
, where N is the number of parts composing the product. Wolter (1989) presented a linear monotonic assembly planning algorithm called XAP/1. Its complexity is . These algorithms confront with exponential explosion in their computational complexity.In this section, based on the principle of the hierarchical quotient space model presented in Chapter 1, we give a monotonic assembly planning algorithm. Under some conditions, the algorithm has a polynomial complexity 
, where s is all possible assembly directions and 
generally. Therefore, the complexity is 
(Zhang and Zhang, 1990c).
, where s is all possible assembly directions and generally. Therefore, the complexity is (Zhang and Zhang, 1990c).5.1.2. Algorithms
In the following discussion, we assume that the disassembly task of a product is the inverse of a feasible assembly task of the same product. So the problem of generating assembly sequences can be transformed into that of generating disassembly sequences for the same product. And rigid motions are also assumed here.
Directed Graph 
Assume that a product W consists of N parts. We call the relative positions and interconnections among the parts of product W its structure. Assume that c is a subset of W. If the structure of any part in c is the same as its structure in W, c is said to be a component. Suppose that each component has two parts at least.
Let a set of possible disassembly trajectories of all parts in W be 
. Given a component p and a possible disassembly trajectory d, a directed graph 
can be constructed as follows.
. Given a component p and a possible disassembly trajectory d, a directed graph can be constructed as follows.Each part of p corresponds to a node. We obtain a set of nodes.
Given a disassembly direction d and a part e, when e moves along direction d from its initial position in W, the sweep volume of e is said to be a trajectory of e along d.
Definition 5.1
Given a direction d and parts a and b, if b intersects with the trajectory of a along direction d, b is said to be in front of a along direction d. It is denoted by a < b(d). If b is moving along the opposite direction to d, it does not collide any part of component p, b is said to be an element immediately in front of a along direction d, or simply the front element of a.
For each element a of p and its front element b, a directed edge 
is constructed. We obtain a directed graph called a disassembly directed graph along the direction d. It is denoted by .
is constructed. We obtain a directed graph called a disassembly directed graph along the direction d. It is denoted by .For example, a component p consists of four parts: a, b, c and e. Its front and plain views are shown in Fig. 5.2, where e is the front element of a, and c is the front element of b. is shown in Fig. 5.3. Since from 
we have 
, sometimes, the directed edge can be omitted, as shown in Fig. 5.3.
is shown in Fig. 5.3. Since from we have , sometimes, the directed edge can be omitted, as shown in Fig. 5.3.Compressed Decomposition
Assume that is a disassembly directed graph of p corresponding to the direction d. If each directed loop in is shrunk to a point, we have a compressed graph denoted as 
or simply 
. Obviously, is a directed tree, or a directed acyclic graph.
is a disassembly directed graph of p corresponding to the direction d. If each directed loop in is shrunk to a point, we have a compressed graph denoted as or simply . Obviously, is a directed tree, or a directed acyclic graph.
There are two kinds of nodes in . 
is a set of nodes which only contain one of ’s nodes. 
is a set of nodes which contain more than one of ’s nodes; namely, a set of components in .
. is a set of nodes which only contain one of ’s nodes. is a set of nodes which contain more than one of ’s nodes; namely, a set of components in .The process of decomposing into and is called a compressed decomposition of . While and compose a compressed decomposition graph of .
into and is called a compressed decomposition of . While and compose a compressed decomposition graph of .
Assume that is a compressed graph of . From our theory, is a quotient space of , where a node in is a subset of nodes in . If a node in contains more than one of ’s nodes, it is said to be a component. Therefore, the compressed decomposition of is a process of constructing its quotient spaces.
is a compressed graph of . From our theory, is a quotient space of , where a node in is a subset of nodes in . If a node in contains more than one of ’s nodes, it is said to be a component. Therefore, the compressed decomposition of is a process of constructing its quotient spaces.Since is a directed tree, there exist linear assembly plans. Due to the compressed decomposition, the problem of planning assembly sequences of is transformed into a set of sub-problems, the planning assembly sequences of components in . By successively using the compressed decomposition, we will finally have an assembly plan of the overall product.
is a directed tree, there exist linear assembly plans. Due to the compressed decomposition, the problem of planning assembly sequences of is transformed into a set of sub-problems, the planning assembly sequences of components in . By successively using the compressed decomposition, we will finally have an assembly plan of the overall product.Assume that is a compressed graph of , or it is simply denoted by E. E is a direct acyclic graph. For all 
, we define the fan-in 
of a as the number of directed edges of E which terminate in a.
is a compressed graph of , or it is simply denoted by E. E is a direct acyclic graph. For all , we define the fan-in of a as the number of directed edges of E which terminate in a.Since E is a directed acyclic graph, there exists 
such that 
. If , a is said to be a l-class node. Generally, for , if the highest class of a's father nodes is k, then a is a (k+1)-class node.
such that . If , a is said to be a l-class node. Generally, for , if the highest class of a's father nodes is k, then a is a (k+1)-class node.Thus, the assembly procedure of E is the following. Taking out all l-class nodes, then all 2-class nodes are merged to their own father nodes along the opposite direction of d, respectively. Generally, If 1- to k-class nodes have been merged, then all (k+1)-class nodes are merged to their own father nodes along the opposite directions of d, respectively. The process is continued, we finally have graph E. The process is called E-assembly.
Cyclic Compressed Decomposition
Assume that a set of possible disassembly trajectories of produce W is 
.
.Component c and disassembly direction 
are given. After the compressed decomposition of 
along d, if we have a set 
of components, then c is said to be undecomposable corresponding to d.
are given. After the compressed decomposition of along d, if we have a set of components, then c is said to be undecomposable corresponding to d.Cyclic Compressed Decomposition Algorithm – Algorithm I
Product W and a set of possible disassembly directions are given. We compose a new infinitely cyclic sequence 
, where 
when 
.
of possible disassembly directions are given. We compose a new infinitely cyclic sequence , where when .Loop
Given an index i and a set 
of components, for 
, define a label 
.
of components, for , define a label .Initially, 
, 
, 
, 
.
, , , .If 
, success.
, success.Otherwise, for , to find the compressed decomposition of c along direction 
.
, to find the compressed decomposition of c along direction .If c is undecomposable
If 
, failure
, failureOtherwise, let 
, c is included in set 
.
, c is included in set .Otherwise, c is decomposed into some new components, and they are included in set .
.By letting 
and 
, go to Loop.
and , go to Loop.Note that when c is decomposed, is decomposed into 
and 
, where the nodes of are said to be new components of c.
is decomposed into and , where the nodes of are said to be new components of c.Assembly Planning Algorithm – Algorithm II
Assume that algorithm I succeeds. We have a set
If nodes in some compressed graph 
are parts, then 
is called a l-class component. Generally, 1-k class components have been defined. Then, when the level of nodes in compressed graph of is less than or equal to k-class, and at less one node is k-class, then is called a (k+1)-class component.
are parts, then is called a l-class component. Generally, 1-k class components have been defined. Then, when the level of nodes in compressed graph of is less than or equal to k-class, and at less one node is k-class, then is called a (k+1)-class component.The assembly procedure is the following.
Each 1-class component in H is assembled, according to its compressed graph. Assume that 1-k class components have been assembled. Then, k+1 class components are assembled, until the overall product W is assembled.
Obviously, if Algorithm I succeeds, it means that the compressed decomposition has been done along all directions . If there is a component which has continuously been decomposed for s times, and is still undecomposable, then its label is (s-1), i.e., algorithm I fails. Since algorithm I succeeds, it shows that the labels of all components are less than (s-1). Therefore, all components in W have been decomposed into the union of parts.
. If there is a component which has continuously been decomposed for s times, and is still undecomposable, then its label is (s-1), i.e., algorithm I fails. Since algorithm I succeeds, it shows that the labels of all components are less than (s-1). Therefore, all components in W have been decomposed into the union of parts.On the other hand, since product W only has N parts, W must be demounted into single parts in N-1 time decompositions at most.
When each component of a directed tree 
has been decomposed, we have a directed graph 
. Obviously, is a quotient space of . Moreover, graph can be reconstructed, by replacing each component of with its corresponding compressed decomposition graph along some direction.
has been decomposed, we have a directed graph . Obviously, is a quotient space of . Moreover, graph can be reconstructed, by replacing each component of with its corresponding compressed decomposition graph along some direction.By repeatedly using the compressed decomposition, a sequence of quotient spaces can be obtained. The upper level graph is a quotient space of its lower level one. And the lower level graph is gained by replacing some nodes of its high level graph with their corresponding directed trees.
5.1.3. Examples
Example 5.1
Product W consisting of six parts is shown in Fig. 5.5, to find its assembly sequences.
and 
and 
From empirical knowledge of product W, we know that there are four possible disassembly trajectories. Namely, 
and 
.
and .First, from the geometric knowledge, we construct a directed graph of W along direction 
. By the compressed decomposition of , is obtained, where 
and 
(see Fig. 5.6).
of W along direction . By the compressed decomposition of , is obtained, where and (see Fig. 5.6).The directed graph of 
along 
is constructed shown in Fig. 5.7. By the compressed decomposition of , we have , where 
and 
.
of along is constructed shown in Fig. 5.7. By the compressed decomposition of , we have , where and .The directed graph 
of 
along 
is constructed, and is shown in Fig. 5.8. By the compressed decomposition of , we have 
, where 
and 
(see Fig. 5.8).
of along is constructed, and is shown in Fig. 5.8. By the compressed decomposition of , we have , where and (see Fig. 5.8).
and 
The directed graph of along is constructed, and is shown in Fig. 5.9. This is a directed tree. The compressed decomposition process terminates.
of along is constructed, and is shown in Fig. 5.9. This is a directed tree. The compressed decomposition process terminates.Now, the assembly process goes on in the opposite directions. First, since is a directed tree, simply by putting part 2 on part 3, fitting part 5 onto parts 2 and 3 along the opposite direction of , we obtain subassembly .
is a directed tree, simply by putting part 2 on part 3, fitting part 5 onto parts 2 and 3 along the opposite direction of , we obtain subassembly .Second, by inserting part 6 into part 5 from left to right, the opposite direction of in , we have subassembly 
, where 
.
in , we have subassembly , where .Finally, based on , by fitting onto part 4, and screwing part 1 on part 4, we have product W.
, by fitting onto part 4, and screwing part 1 on part 4, we have product W.From a technological point of view, it is awkward to fit onto part 4. To prohibit the awkward assembly trajectory, the right one is moving part 4 upward to .
onto part 4. To prohibit the awkward assembly trajectory, the right one is moving part 4 upward to .In order to overcome the above defect, it only needs to revise the construction process of directed graph as follows.
as follows. is a directed edge of . If the disassembly of b along direction d is not allowable, then edge is represented by a double-headed arrow 
. It means that parts a and b can be assembled in two different directions. We can choose one of them depending on the technological requirement. The revised directed graph is denoted by 
. Graph is compressed to tree 
. The rest of the compressed decomposition procedure remains unchanged. The revised algorithm I may satisfy the technological requirement as well.Example 5.2
Product W is as shown in Fig. 5.5. The procedure of inserting part 2 or/and part 3 into part 4 is not allowable.
Some directed graphs and compressed directed graphs 
, 
, 
and 
are shown in Fig. 5.10. The rest is the same as Example 5.1.
, , and are shown in Fig. 5.10. The rest is the same as Example 5.1.The final assembly procedure is the following. Since 
and 
are the same as and 
, respectively, the first two assembly steps are the same as before. Then, we have the subassembly . From we insert part 4 into 
. From screwing part 1 into , we have the overall product W.
and are the same as and , respectively, the first two assembly steps are the same as before. Then, we have the subassembly . From we insert part 4 into . From screwing part 1 into , we have the overall product W.
, , and 5.1.4. Computational Complexity
The Completeness of Algorithms
First we show the completeness of the above algorithms.
If the successively compressed decomposition, i.e., algorithm I succeeds, from algorithm II, it is known that there exists an assembly plan.
If algorithm I fails, there exists a component c such that . We will next show there does not exist a monotonic assembly plan of product W along the given assembly (disassembly) trajectories .
. We will next show there does not exist a monotonic assembly plan of product W along the given assembly (disassembly) trajectories .Proof
Assume there is an assembly plan F. Given a component c such that , where c is a component of product W, letting 
be the disassembly plan corresponding to F, then there must exist some stage of such that c is disassembled along some direction d. Therefore, c is decomposable. This is in contradiction with .
, where c is a component of product W, letting be the disassembly plan corresponding to F, then there must exist some stage of such that c is disassembled along some direction d. Therefore, c is decomposable. This is in contradiction with .Proposition 5.1
Assume that product W has N parts. The computational complexity of algorithm I is 
, where s is the total number of the possible disassembly trajectories of W.
, where s is the total number of the possible disassembly trajectories of W.Proof
Assume that 
is a set of mutually disjoint components of W. Each component has 
parts.
is a set of mutually disjoint components of W. Each component has parts.The computational complexity for constructing each directed graph 
of along some direction , where is a set of possible disassembly trajectories of W, is less than or equal to 
. This can be simply shown as follows.
of along some direction , where is a set of possible disassembly trajectories of W, is less than or equal to . This can be simply shown as follows.Assume that a component b has m parts, i.e., 
. Given a direction d, we construct a 
matrix C as follows.
. Given a direction d, we construct a matrix C as follows.When
Now, a directed graph 
is constructed as follows.
is constructed as follows.If 
then a directed edge 
in is constructed. Since the number of the entities in C, except 
, is 
, the computational complexity for constructing is at most.
then a directed edge in is constructed. Since the number of the entities in C, except , is , the computational complexity for constructing is at most.Therefore, the total computational complexity for constructing directed graph 
along some direction d is
along some direction d is
For s possible disassembly trajectories, the total complexity for constructing directed graph 
is
is
Now, we consider the complexity for obtaining the compressed graph from , where component c has a parts. Given a node 
, starting from b1, we find a directed path 
. If in some step, we have a node 
, which is a leaf of , then 
belongs to . This means that has two nodes at least, namely, c is decomposed into the union of and 
at least. Or in some step, we find a directed loop l, shrinking l into a point, from point l a directed path is explored. The process continues. After a steps, either c is decomposed into two parts at least, or c is undecomposable along d direction.
from , where component c has a parts. Given a node , starting from b1, we find a directed path . If in some step, we have a node , which is a leaf of , then belongs to . This means that has two nodes at least, namely, c is decomposed into the union of and at least. Or in some step, we find a directed loop l, shrinking l into a point, from point l a directed path is explored. The process continues. After a steps, either c is decomposed into two parts at least, or c is undecomposable along d direction.For each 
along directions 
making compressed decomposition, after s time decompositions either c is decomposed or 
, i.e., algorithm I fails. The computational complexity
, where a is the number of parts in c.
along directions making compressed decomposition, after s time decompositions either c is decomposed or , i.e., algorithm I fails. The computational complexity, where a is the number of parts in c.Now, for each of the directed graphs along directions repeatedly making decomposition, respectively, its complexity is 
, where ai is the number of parts in component ci.
along directions repeatedly making decomposition, respectively, its complexity is , where ai is the number of parts in component ci.In other words, after less than or equal to sN decompositions, either at least one of the components in W is decomposed or W is undecomposable, i.e., algorithm I fails.
On the other hand, so long as product W has been decomposed for N-1 times at most, it must be decomposed into single parts.
The total complexity of the successively compressed decomposition is.
.By adding the complexities for constructing the directed graph and making compressed decomposition together, we obtain the total complexity.
.Corollary 5.1
If 
, the complexity of algorithm I is 
.
, the complexity of algorithm I is .Proposition 5.2
If the complexity of assembling two parts (or components) is regarded as 1, then the complexity of algorithm II is
.
.5.1.5. Conclusions
A product W consists of N parts. If all possible permutations of the parts are considered, the number of possible assembly sequences would be N!. This implies that it is not the right way to find the assembly sequences by considering all possible combinations. The essence of multi-granular computing is to break the problem into manageable ones. In our assembly sequences generation, by the cyclic compressed decompositions the product W is decomposed into different kinds of subassemblies hierarchically. Let's consider Example 5.1 again. By the compressed decomposition along the direction , we break the product W into subassembly , parts 1 and 4. And from the compressed decomposition along the direction , it shows that the subassembly V1 is undecomposable, and is denoted by . Then, by the compressed decomposition along the direction , the subassembly is split into sub-subassembly and part 6. Finally, is decomposed into single parts 2, 3 and 5. We finally have a tree structure as shown in Fig. 5.11. The upper level node is a quotient space of its lower level nodes. The assembly of product W simply goes on from bottom to top along the tree. Therefore, the computational complexity is reduced.
, we break the product W into subassembly , parts 1 and 4. And from the compressed decomposition along the direction , it shows that the subassembly V1 is undecomposable, and is denoted by . Then, by the compressed decomposition along the direction , the subassembly is split into sub-subassembly and part 6. Finally, is decomposed into single parts 2, 3 and 5. We finally have a tree structure as shown in Fig. 5.11. The upper level node is a quotient space of its lower level nodes. The assembly of product W simply goes on from bottom to top along the tree. Therefore, the computational complexity is reduced.
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.