Automatic assembly task assignment for a multirobot environment

AUTOMATIC ASSEMBLY TASK ASSIGNMENT FOR A MULTIROBOT ENVIRONMENT C. Del Valle* and E.F. Camacho** *Departamento de Lenguajes y Sistemas Informáticos, Universidad de Sevilla, 41012 Sevilla, Spain ([email protected]) **Departamento de Ingeniería de Sistemas y Automática, Universidad de Sevilla, 4/012 Sevilla, Spain Abstract: This paper presents an algorithm A• for obtaining the "best" assembly plan for a product in a multirobot system. Toe algorithm takes into account, in addition to the assembly times, the times needed to change tools in the robots. Toe objective of the plan is the minimization of the makespan. To meet this objective, the algorithm starts from the And/Or graph (compressed representation of all feasible assembly plans) and the information on each assembly task (robot and tool needed, and assembly time). Keywords: Flexible manufacturing systems; assembly robots; industrial robots; artificial intelligence; optimization problems; scheduling algorithms 1. INTRODUCTION Automatic assembly is one of the areas of manufac turing that has not been fully developed in industry. This is mainly because robot control and off-line programming have not evolved as expected (Martensson, 1990), as result of the fact that the assembly process is much more complex than processes in other robotic applications and parts manufacturing. Therefore, until recently, industrial robots were used primarily in simple assembly applications. This situation is changing, however, and Flexible Assembly Systems have become a very important issue because of the need to produce small lots of products, but the degree of flexibility is still low (Boneschanscher, 1993). There are different stages in the whole process of assembly, such as design of products and parts, design of fixtures, grasp selection, path planning, fine-motion planning, sensor integration, etc. One of the most important issues in the whole process is planning assembly tasks, whose optimality will have a significant effect on the final cost of the assembled product (Kusiak, 1990). Toe assembly planning problem involves the identification, selection and sequencing of assembly operations, stated as their effects on the parts. Toe identification of assembly operations usually leads to the set of all feasible assembly plans. The number of them grows expo nentially with the number of parts, and depends on other factors, such as how the single parts are inter connected in the whole assembly, i.e. the structure of the graph of connections. In fact, this problem has been proved to be NP-complete in both the two dimensional (Kavraki and Kolountzakis, 1995) añ.d three-dimensional (Kavraki, et al., 1995; Wilson, et al., 1995) cases. Two different approaches have been used in obtaining assembly plans. At first, interactive planners queried the user for geometric-reasoning information (Bour jault, 1984; De Fazio and Whitney, 1987). More recently, planners work automatically from a geomet ric and relational model of the assembly (Homero de Mello and Sanderson, 1991 b) and from a CAD model and other non-geometric information (Ames, et al., 1995; Romney, et al. , 1995). Within this scope, the representation of assembly plans is an important issue. Toe use of And/Or graphs for this purpose (Homero de Mello and Sanderson, 1990, 1991a, b) is becoming one of the most standard ways of representing all possible assembly plans. It can be obtained by studying the opposite problem, that of disassembly, but main taining the constraints of assembly. Most automat ic planners work with this strategy. The result is a representation which is adequate for a goal-directed approach. Moreover, Homero de Mello and Sanderson (1990) and Wolter (1992) showed that this structure is more efficient in most cases than other enumerative ones. An optimum assembly plan is now sought, selected from the set of all feasible assembly plans. A variety of criteria has been used for choosing an optima! one. For example, Wolter (1988) combines the ratings related to manipulability of subassemblies, fixture complexity, and the number of different . directions from which operations are performed, to complete a plan. Criteria including the minimization of reorienta tion and fixture requirements were introduced by De Fazio et al. (1990). Henrioud (1989) proposed the aid of an expert about the operational and logistic complexity, and strategic advantages to select the best assembly tree (plan). Homem de Mello and Sanderson ( 1990) proposed assigning to the hyperarcs of the And/Or graph weights that depend on the complexity of the assembly tasks and on the stability of the intermediate sub-assemblies, and using generic search algorithms such as the AO* to obtain the best plan. Their proposal (1991c) of sorne optimization criteria based on maximizing the number of different assembly sequences encompassed by the assembly plan, and on maximizing the amount of parallelism (simultaneity) possible in the execution of the assem bly tasks, is used in a heuristic search algorithm. In another way, an algorithm is proposed in (Holland, et al., 1992) for a specific assembly cell, and for batches of products. This paper presents an algorithm A* (Nilsson, 1980; Pearl, 1984) for obtaining the "best" assembly plan for a product in a multirobot system. The approach used here is that of Homero de Mello and Sanderson (1990; 1991c), but more detailed information for the assembly tasks is considered. The algorithm takes into account, in addition to the assembly times, the times needed to change tools in the robots. Toe ob jective of the plan is the minimization of the total assembly time (makespan). To meet this objective, the algorithm starts from the And/Or graph (com pressed representation of all feasible assembly plans) and the information about each assembly task (robot and tool needed and assembly time). The paper is organized as follows: Section 2 describes the problem of assembly-task assignment. Toe proposed algorithm is described in Section 3, and sorne of the results obtained are presented in Section 4. Sorne final remarks are made in the concluding section. 2. PROBLEM STATEMENT Toe process of joining parts together to form a unit is known as assembly. The joining process results in the connection of one part with parts already assem bled. A sub-assembly is a group of parts having the property of being able to be assembled independently of other parts of the product. An assembly plan is a set of assembly tasks with ordering amongst its ele ments. Each task consists of joining a set of sub assemblies to give rise to an ever larger sub-assem bly. An assembly sequence is an ordered sequence of the assembly tasks satisfying all the ordering con straints. Each assembly plan corresponds to one or more assembly sequences. An And/Or graph is a representation of the set of all assembly plans possible for a product. Toe Or nades correspond to sub-assemblies, the top node corre sponds to the whole assembly, and the leaf nodes correspond to the individual parts. Each And nade corresponds to the assembly task joining the sub assemblies of its two final nodes producing the sub assembly of its initial node. In the And/Or graph representation of assembly plans, an And/Or path whose top node is the And/Or graph top node and whose leaf nades are the And/Or graph leaf nodes is associated to an assembly plan, and is referred to as an assembly tree. An important advantage of this representation, used in this work, is that the And/Or graph shows the independence of assembly tasks that can be executed in parallel. Figure 1 shows an exam ple of this representation. And nades are omitted. This work is centered on the problem of choosing the best assembly plan, that is one of the And/Or trees of the And/Or graph. The majority of approaches used Fig. l. The And/Or graph for the product ABCDE. up to now make this selection in a planning phase in which neither the assembly system, nor how the assembly tasks within it will be materialized, is taken into account. This work takes into account the physical realization of the assembly. It is assumed that the assembly tasks correspondíng to the And/Or graph have been evalu ated separately, in the sense of estimating the re sources necessary for their realization (robots, tools, fixtures ... ) as well as their approximate duration times. These times should include an estimation for the times needed for other operations, such as trans portation of parts and subassemblies. Por an And/Or graph with a large number of nodes this is not an easy task, and the help of a computer-aided system is necessary. Toe nodes corresponding to tasks which are not realizable as the adequate tools are not avail able are eliminated from the And/Or graph. Another fact taken into account here, is the time necessary for changing the tools in the robots, which is of the same order as the execution time of the assembly tasks and therefore cannot be disregarded as in Parts manufacturing. Furthermore, the choice is not limíted to the assembly plan, but also specifies when each task is to be carried out in order to míni mize the makespan (sorne tasks which could poten tially be carried out in parallel have to be delayed because they need common resources). Toe algorithm can be used in an off-line manner for obtaining an optimum initial solution for the assembly process. However, due on one hand to the flexibility for modifying the convergence criteria of the algo rithm towards a not strictly optimum solution, and on the other to the fact that as the assembly process advances the resulting problem becomes smaller, the algorithm could be applicable on-line to modify either the plan or the initial sequence, in order to correct the variations with respect to the initial solution. 3. ALGORITHM DESCRIPTION As has been stated previously, the algorithm is cen tered on the choice of an assembly plan for a com plete product in a multiple-robot system, whe::e the resources necessary for carrying out each task repre sented in the And/Or graph (robots, tools ... ) appear as data, as well as the times necessary for their exe cution. As well as the choice of assembly plan, the execution orders for the tasks in each robot are speci fied by an analysis of their execution in parallel in the assembly system given. Because of the set-up of the And/Or graph, the as sembly problem can be studied, starting from the final situation and going towards the initial one. Toe algorithm has two well-differentiated parts: one of them studies the sequential execution of assembly tasks, and the other solves the parallel execution of assembly tasks (the representation through the And/Or graph allows a natural study of this stage). This is actually the most complex section, because the execution of tasks on one side of the global as sembly is not independent of the rest, and can influ ence the execution of tasks in the other part of the assembly. Heuristic functions based on the execution of tasks taken only from the part of the tree below the node, and the time remaining for the use of tools and robots (supposing the mínimum number of tool changes, in order to maintain the algorithm as A*) have been used in order to expand the mínimum number of nodes and avoid redundant nodes. Because there is un upper limít to the makespan, the parallel algorithm does not need to finish when the best expected cost is higher than that limit. Toe algorithm is used off-line to obtain an optimum first assembly plan. However, as the assembly pro cess evolves, it can be used on-line to correct the changes which could have occurred during the assem bly process, by pruning the And/Or graph of the subassemblies already performed. Toe optimízation criteria can easily be changed, according to the par ticular needs of the application. 3 .1. Sequential Execution of Tasks An algorithm A· to search for the global assembly plan can be implemented in the following way. Be ginning with an initial node whose state represents the complete assembly realization, and therefore corresponds to the root node of the And/Or graph (complete assembly), all its possible successors are generated, whose states will represent the execution at the end of the assembly process of the tasks corre sponding to the And nodes coming from the root node of the And/Or graph. Two types of nodes may be generated, depending on the destination Or nodes of each chosen And node. If at least one of these Or nodes corresponds to an individual part, the assembly process will continue to be sequential, and the node resulting from the expan sion may be treated as the initial node, where the node corresponding to the non-trivial sub-assembly will take the place of the root node. If, on the other hand, the application of the task starts from two sub-assemblies, each with various parts, in the resulting plan (or plans in general) the task arrangement is not totally specified (various possible sequences exist for each assembly plan}, or tasks may be carried out in parallel. There is also an interdependence amongst the sub-assemblies, because they potentially use the same set of resources. Toe treatment of this type of node has therefore to be undertaken in a different way from those correspond ing to sequential task execution, and this will connect with the second part of this algorithm. Toe evaluation function used for the nodes generated in this part is f(n) = g(n) + h(n), (1) g(n) being the time accumulated in the execution of tasks corresponding to the state of node n, including the delays in the necessary tool changes, and h(n) being an optimistic estimation of the remaining time in which to complete the global process. (h(n) should be a lower bound of the remaining time for the algo rithm to be A·.) Due to the fact that various different plans (and therefore different task sets which would complete the assembly process) may be reached from node n, a detailed study would be computationally costly, and therefore h(n) = a(n) · min(pJ (2) has been chosen, a(n) being the number of tasks necessary to complete the assembly plan, and p¡ the processing time of task i. As can be seen, it is also impossible to determine the minimum number of tool changes without a detailed study, and therefore when estimating h(n) it is assumed to be zero. All the assembly trees (task precedence trees) are obtained for the "parallel" nodes, and are studied separately. Toe function h (n) corresponding to each tree is defined in the following subsection. 3.2. Parallel Execution of Tasks Toe objective of this part of the algorithm is to deter mine the total minimum time for the execution of the precedence trees obtained in the previous section. In order to do this, an algorithm A* is again used. Toe nodes of the expansion tree now present partial infor mation about the execution of the assembly process. Concretely, at each expansion step only one assembly task is introduced, and its processing time will affect only one of the workstations, the same state being retained by the other workstations. Toe state corresponding to one node of the expansion tree is represented by using the tasks available for introduction in the state of the next step, termed "candidates", and their earliest starting times, denot ed est(tJ. At the same time, the last tool used is included for each robot, as well as the final time of use. Toe evaluation function for the nodes obtained by this algorithm is similar to (1), being now g(n) = the largest of the earliest starting times of candidates(n) and the final times of the already finished in n without successors. h(n) = max(h¡(n),hi(n)) (3) h1 (n) =estimation of the time remaining if the inter dependencies between different branches in the tree are not taken into account. It is looked at only in depth. hi(n) =estimation of time needed if only the re maining usage times of the tools in each robot are taken into account, further sup posing the number of tool changes to be at a minimum. Figure 2 shows a task precedence tree, different expansion nodes and information about their corre sponding states. lt is also accompanied by the Gantt charts. Toe heuristic function h¡(n) can be defined as fol lows: h¡(n) =max ( hl(n,JJ -ft(n,JJ ) candidates(n) where ft(n,J) = g(n) -est(n,J) hJ(n,J) = h;'(J) + max ( r(l,R;,last tool(RJ - robots (est(n,J)-last _time(RJ), O) h;'(J) = p(J) + max ( h;'(JJ + r(l;,R(J),T(J)) ). successors of J (4) (5) (6) (7) In the above expressions, n is an expansion node, J is an assembly task, last _tool(RJ and last _time(RJ are the last tool used in robot R; and the time of last use respectively, and (est(n,J)-last _time(RJ) is the exist ing time slack. R(J) and T(J) are the robot and tool necessary for the execution of task J, and p(J) is its processing time. r(J,R, T) is the added delay, due to the fact that the tool T is being used by robot R in task J and successors, because of the necessary tool changes. Notice that h¡(J) does not depend on the expansion nodes, and thus allows one to calculate a lower bound prior to using the A· algorithm. ......... R1 T1 p•1 . . . . . . . . . . . p-4 . . . . R1 T2 ............ ' ........................ ' . . . . . . . . . . . . . . . . . . ' . . . . . . . . . . ' .... . . . . . . . . . . . . . . ' . . :R2T4 :p-2 J2 R1 T1 J5 p-5 ......... .... p-3 J6 ........... J1 • o J2 • O o R1 • -· 2 4 8 8 10 TIME R2- -· g . o J1 J1 J2 • O J3 • 1 J4 • 1 R1 • T1 • 1 R1 T1 R2. ····-· R2 g . 1 J4 J2 • 8 J3. 3 J6. 4 R1 • T1 -1 R2·T3-3 R1 g . R2 J2 J3. 11 J5 • 8 J6 • 4 R1 • T1 -1 R2 • T4 • 8 R1 T1 g . 11 R2 ... T4 T3 Fig. 2. A task precedence tree, sorne expansion nodes, and their corresponding Gantt charts. h2 can be defined as follows: hi(n) =max ( h;(n,RJ -ft(n,RJ ) robots (8) where ft(n,RJ = g(n) -last_time(RJ (9) and hln,RJ is the minimum time of use of robot R; without considering the task precedence constraints. First simplification: Each tool is associated with only one robot. The calculation of hin,R) is equivalent to the travelling salesman problem, when considering the tools not yet used and an initial node correspond ing to the last-used tool in the robot R. h;(n,R) = L 1r(J'J + tool-change times (10) T¡E T(R) with 1r(J'J the remaining time of usage of tool T. Second simplification: Tool-changing times do not depend on the type of tool. hi(n) could be improved by using the earliest usable time of R instead of using ft(n,RJ. Notice that tasks not included in n should be considered in this case. Definition: A task t; is compatible with [including] task tj if, on including this task at the following leve!, the start of t; and that of its successors in the task precedence tree are not delayed. This definition allows the number of expanded nodes to be minimized. The candidates tasks compatible with another task included in the next leve! will be included in successive levels. The expansion of a node is carried out by the algo rithm shown in Fig. 3. Notice that the algorithm can be extended to the case where there is more than one candidate tool for each assembly task. A list of candidate tools has to Procedure Expand(n) Let J = {11, ... ,JJ be the s t of candidates(n) and EST = {est,, ... ,estJ its earliest starting times. est_min = min(estJ lf there is just one task l¡ with est¡ = est _min lnclude in open a nade whose state is that of n plus J, /f there are tasks not compatible with l¡ Expand(n), restrided to l'= {Jm, with lm not compatible with JJ endif else Let NTI, be the number of tasks not compatible with J,, and Nl1_min = min(Nl7¡), for est¡=est_min lnclude in open a nade whose state is that of n plus J,, with J, such that Nl1=Nl1_min /fNI1_min�O Expand(n), restricted to l'= {Jm , with Jm not compatible with J J endif endif Fig. 3. Algorithm for the expansion of nodes. be considered when expanding the nodes. A very simple heuristic function consisting of only consider ing the assembly times of the remaining tasks could be used. A more informed heuristic function would require a more complex algorithm. 4. RESULTS Toe algorithm has been tested in a variety of situa tions, considering different product structures (num ber of parts, number of connections between parts), different types of And/Or graphs (number of sub assemblies, number of assembly tasks for each sub assembly), and different assembly resources (number of robots, number of tools). Toe solution obtained for the assembly task assign ment of the flashlight shown in Fig. 4 (Homem de Mello and Sanderson, 1990c) is shown in Fig. 5. Toe assembly environment was composed of two robots and two assembly tools per robot. Toe original com plete And/Or graph contains 35 And nodes, 24 Or nodes and 37 possible assembly plans, and is not shown for the lack of space. Toe Gantt charts corre sponding to the solution are shown in Fig. 6. 5. CONCLUSIONS An A· algorithm for obtaining the optimum assembly plan for a multirobot environment has been present ed. The algorithm minimizes the makespan of the assembly. To apply the algorithm, possible assembly tasks should be specified by an And/Or graph. Toe algo rithm needs the definition of the necessary tools and an estimation of the time required for each assembly operation. The algorithm has been tested with problems of di verse complexity. 6. ACKNOWLEDGMENT The authors would like to acknowledge CICYT for funding the work. Toe authors would also like to extend their thanks to the anonymous referees for their helpful suggestions. 7. REFERENCES Ames, A.L., T.L. Calton, R.E. Jones, S.G. Kaufman, C.A. Laguna and R.H. Wilson (1995). Lessons Learned from a Second Gener ation Assembly Planning System. Proc. 1995 IIINQ U!NS IUIJI IIEA.SCTOR BATTBIY END Fig. 4. Product example: a flashlight. 111 IIM. ao L E Fig. 5. Tree solution for the product example ob tained from the And/Or graph. TASK CHANGE TASK TASK TASI< R1 31 TOOL 11 4 TASI< CIWIQE � R2 30 TOOL TIME Fig. 6. Gantt charts for the tree solution in a two robot environment. IEEE Intl. Symp. on Assembly and Task Plan ning, pp. 41-47. Boneschanscher, N. (1993). Plan Generation for Flexible Assembly Systems. PhD thesis Delft University of Technology, Delft, Toe Nether lands. Bourjault, A. (1984). Contribution a une Approche Méthodologique de l'Assemblage Automatisé: Elaboration Automatique des Séquences Opératoires. These d'état, Université de Franche-Comté, Besaneon, France. De Fazio, T.L., T.E. Abell, G.P. Amblard, O.E. Whitney (1990). Computer-aided assembly sequence editing and choice: Editing criteria, bases, rules, and technique. Proc. IEEE Int. Conf. Syst. Eng., pp. 416-422. De Fazio, T.L. and O.E. Whitney (1987). Simplified Generation of All Mechanical Assembly Se- quences. IEEE J. Robotics and Automat., Vol. 3, No. 6, pp. 640-658. Also, Corrections, Vol. 4, No. 6, pp. 705-708. Henrioud, J.M. (1989). Contribution a la conceptualisation de l'assemblage automatisé: nouvelle approche en vue de détermination des processus d'assemblage. These d'état, Université de Franche-Comté, Besancon, France. Holland, W. van, N. Boneschanscher and W.F. Bronsvoort (1992). Task Assignment in a Flexi ble Assembly Cell Using And/Or Graphs. Proc. 23rd /nt. Symp. lnd. Robots. Barcelona, Spain, October 6-8, pp. 653-658, 642. Homem de Mello, L.S. and A.C. Sanderson (1990). And/Or Graph Representation of Assembly Plans. IEEE Trans. Robotics Automat. Vol. 6, No. 2, pp. 188-199. Homem de Mello, L.S. and A.C. Sanderson (1991a). Representations of Mechanical Assembly Se quences. IEEE Trans. Robotics Automat. Vol. 7, No. 2, pp. 211-227. Homero de Mello, L.S. and A.C. Sanderson (1991b). A Correct and Complete Algorithm for the Generation of Mechanical Assembly Sequences. IEEE Trans. Robotics Automat. Vol. 7, No. 2, pp. 228-240. Homero de Mello, L.S. and A.C. Sanderson (1991c). Two Criteria for the Selection of Assembly Plans: Maximizing the Flexibility of Sequencing the Assembly Tasks and Minimizing the Assem bly Time Through Parallel Execution of Assem bly Tasks. /EEE Trans. Robotics Automat. Vol. 7, No. 5, pp. 626-633. Kavraki, L., J.C. Latombe and R.H. Wilson (1993). On the Complexity of Assembly Partitioning. lnformation Processing Letters. Vol. 48, pp. 229-235. Kavraky, L. and M. Kolountzakis (1995). Partition ing a planar assembly into two connected parts is NP-complete. lnformationProcessing Letters. Vol. 55, pp. 156-165. Kusiak, A. (1990). lntelligent Manufacturing Sys tems. Prentice-Hall International Series in Indus trial and Systems Engineering. Martensson, N. (1990). Robot Ability for the 90's. Proc. 21st lnt. Symp. lnd. Robots. Copenhagen, Denmark, October 23-25, 1990, pp. 193-198. Nilsson, N.J. (1980). Principies o/ Artificial lntelli gence. Chenanso Forks, NY: Tioga. Pearl, J. (1984). Heuristics: Intelligent Search Strate gies for Computer Problem Solving. Reading, MA, Addison-Wesley. Romney, B., C. Godard, M. Goldwasser, G. Ramkumar (1995). An Efficient System for Geometric Assembly Sequence Generation and Evaluation. Proc. 1995 ASME Intemational Computers in Engineering Conference, pp. 699- 712. Wilson, R.H., L. Kavraki, T. Lozano-Pérez and J.C. Latombe (1995). Two-Handed Assembly Se quencing. lntemational Joumal o/ Robotic Research. Vol. 14, pp. 335-350. Wolter, J. (1988). On the automatic generation o/ plans for mechanical assembly. Ph.D. thesis. Univ. of Michigan. Department of Computer, Information and Control Engineering, Septem ber 1988. Wolter, J. (1992). A Combinatorial Analysis of Enumerative Data Structures for Assembly Planning. Joumal o/Design and Manufacturing. Vol. 2, No. 2, June 1992, pp. 93-104.