Survey on assembly sequencing: a combinatorial and geometrical perspective

• Abegg, F., Engel, D., & Wörn, H. (1999). Manipulating deformable linear objects—vision-based recognition of contact state transitions. In: The Ninth international conference on advanced robotics (pp. 135–140).

• Acker, J., & Henrich, D. (2005). Manipulation of deformable linear objects: From geometric model towards program generation. In: Proceedings of the IEEE international conference on robotics and automation (pp. 1541–1547).

• Almgren, R. (1994). Comparative topological modeling and analysis of assemblies and assembly systems—an aid in computerized assembly planning. In: Proceedings of the IEEE international conference on robotics and automation (ICRA) (pp. 1468–1475).

• Bagchi A., Mahanti A. (1983) Admissible heuristic search in and/or graphs. Theoretical Computer Science 24: 207–219

  Article  Google Scholar 

• Ben-Arieh D., Kumar R. R., Tiwari M. K. (2004) Analysis of assembly operations difficulty using enhanced expert high-level colored fuzzy petri net model. Robotics and Computer-Integrated Manufacturing 20(5): 385–403. doi:10.1016/j.rcim.2004.03.002

  Article  Google Scholar 

• Bonneville, F., Henrioud, J., & Bourjault, A. (1995). Generation of assembly sequences with ternary operations. IEEE international symposium on assembly and aask planning (pp. 245–249). doi:10.1109/ISATP.1995.518778.

• Bourjault, A. (1984). Contribution a une approche methodologique de l’assemblage automatise: Elaboration automatique des sequences operatoires. PhD thesis, Universite de Franche-Compte.

• Bruyninckx, H., Lefebvre, T., Mihaylova, L., Staffetti, E., Schutter, J. D., & Xiao J. (2001) A roadmap on autonomous robotic assembly. In: IEEE proceedings of the international symposium on assembly and task planning (pp. 49–54). doi:10.1109/ISATP.2001.928965.

• Cao P. B., Xiao R. B. (2007) Assembly planning using a novel immune approach. The International Journal of Advanced Manufacturing Technology 31(7–8): 770–782. doi:10.1007/s00170-005-0235-2

  Google Scholar 

• Cao T., Sanderson A. C. (1998) And/or net representation for robotic task sequence planning. IEEE Transaction on Systems, Man and Cybernetics, Part C Appliccations and Reviews 28(8): 104–218

  Google Scholar 

• Caselli, S., & Zanichelli, F. (1995). On assembly sequence planning using Petri Nets. In: IEEE proceedings of the international symposium on assembly and task planning (pp. 239–244).

• Cem Sinanoglu H. R. B. (2005) An assembly sequence-planning system for mechanical parts using neural network. Assembly Automation 25(1): 38–52. doi:10.1108/01445150510578996

  Article  Google Scholar 

• Chakrabarty S., Wolter J. (1997) A structure-oriented approach to assembly sequence planning. IEEE Transactions on Robotics and Automation 13(1): 14–29. doi:10.1109/70.554344

  Article  Google Scholar 

• Chen C. L. P. (1992) Design of a real-time and/or assembly scheduler on an optimization neural network. Journal of Intelligent Manufacturing 3(4): 251–261. doi:10.1007/BF01473902

  Article  Google Scholar 

• Chen S. F., Liu Y. J. (2001) The application of multi-level genetic algorithms in assembly planning. Journal of Industrial Technology 17(4): 1–9

  Google Scholar 

• Chen W. C., Tai P. H., Deng W. J., Hsieh L. F. (2008) A three-stage integrated approach for assembly sequence planning using neural networks. Expert Systems with Applications 34(3): 1777–1786. doi:10.1016/j.eswa.2007.01.034

  Article  Google Scholar 

• Choset H., Lynch K. M., Hutchinson S., Kantor G. A., Burgard W., Kavraki L. E., Thrun S. (2005) Principles of robot motion: Theory, algorithms, and implementations. MIT Press, Cambridge, MA

  Google Scholar 

• Cui, J. G. P. W. N. (2007). Adaptive ant colony algorithm for on-orbit assembly planning. In: Proceedings of the 2nd IEEE conference on industrial electronics and applications (pp. 1590–1593). doi:10.1109/ICIEA.2007.43186.76.

• Dakin, G. A. (1994). Fine-motion planning for robotic assembly in local contact space. PhD thesis, University of Massachussets Amherst.

• De-Lit P., Latinne P., Rekiek B., Delchambre A. (2001) Assembly planning with an ordering genetic algorithm. International Journal of Production Research 39(16): 3623–3640. doi:10.1080/00207540110056135-005-0235-2

  Article  Google Scholar 

• de Mello, L. S. H., & Sanderson, A. C. (1989) A correct and complete algorithm for the generation of mechanical assembly sequences. In: Proceedings IEEE international conference on robotics and automation (ICRA), (vol. 1, pp. 56–61). doi:10.1109/ROBOT.1989.99967.

• de Mello L. S. H., Sanderson A. C. (1991) Representations of mechanical assembly sequences. IEEE Transactions on Robotic and Automation 7(2): 211–227. doi:10.1109/70.75904

  Article  Google Scholar 

• Desai, R., Xiao, J., & Volz, R. (1988). Contact formations and design constraints: A new basis for the automatic generation of robot programs. In: NATO ARW: CAD based programming for sensory based robots, (pp. 361–395).

• Deshmukh A., Yung J. P., Wang H. P. (1993) Automated generation of assembly sequence based on geometric and functional reasoning. Journal of Intelligent Manufacturing 4(4): 269–284. doi:10.1007/BF00124140

  Article  Google Scholar 

• Dini G., Failli F., Lazzerini B., Marcelloni F. (1999) Generation of optimized assembly sequences using genetic algorithms. Annals of the CIRP 48: 17–20

  Article  Google Scholar 

• Donald, B. R. (1985). On motion planning with six degrees of freedom: Solving the intersection problems in configuration space. In: Proceedings of the IEEE international conference on robotics and automation (pp. 536–541).

• Dong, T., Tong, R., Dong, J., & Zhang, L. (2003). Knowledge-based assembly sequence planning system. In: Proceedings of the 8th international conference on computer supported cooperative work in design (pp. 516–521).

• Fazio T. L. D., Whitney D. E. (1987) Simplified generation of all mechanical assembly sequences. IEEE Journal of Robotics and Automation RA-3(6): 640–658

  Article  Google Scholar 

• Giraud, A., & Sidobre, D. (1992). A heuristic motion planner using contact for assembly. In: Proceedings of the IEEE international conference on robotics and automation (ICRA) (pp. 2165–2170).

• Goldwasser M. H., Motwani R. (1999) Complexity measures for assembly sequences. International Journal of Computational Geometry and Application 9(4/5): 371–417

  Article  Google Scholar 

• Guan Q., Liu J. H., Zhong Y. H. (2002) A concurrent hierarchical evolution approach to assembly process planning. International Journal of Production Research 40(14): 3357–3374. doi:10.1080/00207540210146152

  Article  Google Scholar 

• Guibas, L. J., Halperin, D., Hirukawa, H., Latombe, J. C., & Wilson, R. H. (1995). A simple and efficient procedure for polyhedral assembly partitioning under infinitesimal motions. In: Proceedings of the IEEE international conference on robotics and automation) (pp. 2553–2560).

• Halperin D., Latombe J. C., Wilson R. (2000) A general framework for assembly planning: The motion space approach. Algorithmica 26: 577–601. doi:10.1007/s004539910025

  Article  Google Scholar 

• Heger, F. W. (2008). Generating robust assembly plans in constrained environments. In: Proceedings of the IEEE international conference on robotics and automation (ICRA) (pp. 4068–4073).

• Hong D., Cho H. (1995) A neural-network-based computational scheme for generating optimized robotic assembly sequences. Engineering Applications of Artificial Intelligence 8(2): 129– 145

  Article  Google Scholar 

• Hong, D., & Cho, H. (1999). Generation of robotic assembly sequences using a simulated annealing. In: Proceedings of the 1999 IEEE/RSJ international conference on intelligent robots and systems (pp. 1247–1252).

• Huang, Y., & Lee, C. (1991) A framework of knowledge-based assembly planning. In: IEEE international conference on robotics and automation, (vol. 1, pp. 599–604). doi:10.1109/ROBOT.1991.131647.

• Ji P., Choi A. C., Tu L. (2002) Vdas: A virtual design and assembly system in a virtual reality environment. Assembly Automation 22(4): 337–342

  Article  Google Scholar 

• Ji X., Xiao J. (2001a) Planning motions compliant to complex contact states. International Journal of Robotic Research 20(6): 446–465

  Article  Google Scholar 

• Ji X., Xiao J. (2001b) Random sampling of contact configurations in two-pc contact formations. In: Lynch K., Donald B. R., Rus D. (eds) New directions in algorithmic and computational robotics. Kluwer, Boston

  Google Scholar 

• Jiménez P., Torras C. (2000) An efficient algorithm for searching implicit and/or graphs with cycles. Artificial Intelligence 124(1): 1–30

  Article  Google Scholar 

• Jones, R. E., & Wilson, R. H. (1996) A survey of constraints in automated assembly planning. In: Proceedings of the IEEE international conference on robotics and automation (pp. 1525–1532) Minneaopolis (MN), USA.

• Kim J. Y., Cho H. S. (2000) A neural net-based assembly algorithm for flexible parts assembly. Journal of Intelligent and Robotic Systems 29(2): 133–160. doi:10.1023/A:1008115522778

  Article  Google Scholar 

• Kuniyoshi, Y., Inaba, M., & Inoue, H. (1994) Learning by watching: Extracting reusable task knowledge from visual observation of human performance. IEEE transactions on robotics and automation, 10(6), 799–822. citeseer.ist.psu.edu/kuniyoshi94learning.html.

• Lai H. Y., Huang C. T. (2004) A systematic approach for automatic assembly sequence plan generation. The International Journal of Advanced Manufacturing Technology 24(9–10): 752–763. doi:10.1007/s00170-003-1760-5

  Article  Google Scholar 

• Latombe J. C. (1991) Robot motion planning, vol. SECS 0124. Kluwer, Dordrecht, The Netherlands

  Book  Google Scholar 

• LaValle, S. M. (2006). Planning algorithms. Cambridge University Press, Cambridge, UK. Available at http://planning.cs.uiuc.edu/.

• Le, D. T., Cortés, J., Siméon, T. (2009). A path planning approach to (dis)assembly sequencing. In: Proceedings of the fifth IEEE international conference on automation science and engineering (pp. 286–291).

• Lee B., Saitou K. (2003) Decomposition-based assembly synthesis for in-process dimensional adjustability. Journal of Mechanical Design 125(3): 464–473. doi:10.1115/1.1587746

  Article  Google Scholar 

• Lee, S., & Moradi, H. (1999) Disassembly sequencing and assembly sequence verification using force flow networks. In: Proceedings of the IEEE international conference on robotics and automation (ICRA) (pp. 2762–2767).

• Lee S., Shin Y. G. (1990) Assembly planning based on geometric reasoning. Computation and Graphics 14(2): 237–250

  Article  Google Scholar 

• Lefebvre, T., Bruyninckx, H., & Schutter, J. D. (2003). Active sensing for the identification of geometrical parameters during autonomous compliant motion. In: Proceedings IEEE international conference on robotics and automation (ICRA) (pp. 2599– 2604).

• Lefebvre T., Bruyninckx H., Schutter J. D. (2005) Task planning with active sensing for autonomous compliant motion. International Journal of Robotic Research 24(1): 61–81

  Article  Google Scholar 

• Lefebvre T., Xiao J., Bruyninckx H., de Gersem G. (2005) Active compliant motion: A survey. Advanced Robotics 19(5): 479–499

  Article  Google Scholar 

• Lu, T., Zhang, B., & Jia, P. (1993). Assembly sequence planning based on graph reduction. In: Proceedings of the IEEE TENCON (pp. 119–122)

• Mahanti A, Bagchi A (1985) And/or graph heuristic search methods. Journal of Association for Computing Machinery 32(1): 28–51

  Article  Google Scholar 

• Mantripragada R., Whitney D. E. (1998) The datum flow chain: A systematic approach to assembly design and modeling. Research in Engineering Design 10(3): 150–165. doi:10.1007/BF01607157

  Article  Google Scholar 

• Marian, R. M. (2003) Optimisation of assembly sequences using genetic algorithms. PhD thesis, University of South Australia, Adelaide, Australia

• Marian R. M., Luong L. H. S., Abhary K. (2006) A genetic algorithm for the optimisation of assembly sequences. Computers & Industrial Engineering 50: 503–527. doi:10.1016/j.cie.2005.07.007

  Article  Google Scholar 

• Martelli, A., & Montanari, U. (1973). Additive and/or graphs. In: Proceedings of the third international joint conference on artificial intelligence (pp. 1–11).

• Martelli A., Montanari U. (1978) Optimizing decision trees through heuristically guided search. Communications of the ACM 21(12): 1025–1039

  Article  Google Scholar 

• Meeussen, W., Xiao, J., Schutter, J. D., Bruyninckx, H., & Staffetti, E. (2004). Automatic verification of contact states taking into account manipulator constraints. In: Proceedings of the IEEE international conference on robotics and automation (ICRA) (pp. 3583–3588). doi:10.1109/ROBOT.2004.1308808.

• Meeussen, W., Schutter, J. D., Bruyninckx, H., Xiao, J., & Staffetti, E. (2005). Integration of planning and execution in force controlled compliant motion. In: Proceedings of the IEEE/RSJ international conference on intelligent robots and systems (IROS) (pp. 1217–1222). doi:10.1109/IROS.2005.1545360.

• Meeussen W., Rutgeerts J., Gadeyne K., Bruyninckx H., Schutter J. D. (2007) Contact-state segmentation using particle filters for programming by human demonstration in compliant-motion tasks. IEEE Transactions on Robotics 23(2): 218–231

  Article  Google Scholar 

• Mihaylova, L., Lefebvre, T., Staffetti, E., Bruyninckx, H., & Schutter, J. D. (2001). Tracking contact transitions during force-controlled compliant motion using an interacting multiple model estimator. In: Proceedings of the IEEE international conference on advanced robotics (pp. 665–670).

• Möhring R. H., Skutella M., Stork F. (2004) Scheduling with and/or precedence constraints. SIAM Journal on Computing 33(2): 393–415

  Article  Google Scholar 

• Mosemann, H., Bierwirth, T., Wahl, F. M., & Stoeter, S. (2000). Generating polyhedral convex cones from contact graphs for the identification of assembly process states. In: Proceedings of the IEEE international conference on robotics and automation (ICRA) (pp. 744–749).

• Motavalli S., Islam A. U. (1997) Multi-criteria assembly sequencing. Computer and Industrial Engineering 32(4): 743–751. doi:10.1016/S0360-8352(97)00014-4

  Article  Google Scholar 

• Naphade, K. S., Storer, R. H., & Wu, S. D. (1999a). Graph-theoretic generation of assembly plans, part i: Correct generation of precedence graphs. Technical Report IMSE Technical Report 99T-003, Lehigh University, Bethlehem, Pennsylvania.

• Naphade, K. S., Storer, R. H., & Wu, S. D. (1999b). Graph-theoretic generation of assembly plans, part ii: Problem decomposition and optimization algorithms. Technical Report IMSE Technical Report 99T-003, Lehigh University, Bethlehem, Pennsylvania.

• Nilsson N. J. (1980) Principles of Artificial Intelligence. Tioga, Palo Alto

  Google Scholar 

• Raghavan V., Moloineros J., Sharma R. (1999) Interactive evaluation of assembly sequences using augmented reality. IEEE Transactions on Robotics and Automation 15(3): 435–449

  Article  Google Scholar 

• Ramos, C., ao Rocha, J., & Vale, Z. (2001). A complete complexity study of one-processor assembly and manufacturing planning tasks. In: Proceedings of the 4th IEEE international symposium on assembly and task planning (pp. 369–374).

• Remde, A., Henrich, D., & Wörn, H. (1999). Manipulating deformable linear objects—contact state transitions and transition conditions. In: Proceedings of the IEEE/RSJ international conference on intelligent robots and systems (vol. 3, pp. 1450–1455).

• Remde, A., Henrich, D., & Wörn, H. (2000) Manipulating deformable linear objects—Force based detection of contact state transitions. In: Proceedings of the IEEE international conference on robotics and automation (ICRA) (pp. 1480–1486).

• Romney, B. (1997). Atlas: An automatic assembly sequencing and fixturing system. In: Proceedings of the international conference on theory and practice of geometric modeling (pp. 397–415).

• Romney, B., Godard, C., Goldwasser, M., & Ramkumar, G. (1995). An efficient system for geometric assembly sequence generation and evaluation. In: Proceedings of the ASME international computers in engineering conference (pp. 699–712).

• Rosell, J. (2004). Assembly and task planning using Petri Nets: A survey. Proceedings of the I MECH E Part B journal of engineering manufacture, (vol. 218, pp. 987–994). doi:10.1243/0954405041486019.

• Schwarzer F., Schweikard A., Joskowicz L. (2000) Efficient linear unboundedness testing: Algorithm and applications to translational assembly planning. The International Journal of Robotics Research 19: 817–834. doi:10.1177/02783640022067193

  Article  Google Scholar 

• Schweikard A., Schwarzer F. (1998) Detecting geometric infeasibility. Artificial Intelligence 105(1-2): 139–159

  Article  Google Scholar 

• Sebaaly, M., Fujimoto, H., & Mrad, F. (1996). Linear and non-linear assembly planning: fuzzy graph representation and GA search. In: Proceedings of the 1996 IEEE international conference on robotics and automation (pp. 1533–1538).

• Smith S. S. F. (2004) Using multiple genetic operators to reduce premature convergence in genetic assembly planning. Computers in Industry 54(1): 34–49. doi:10.1016/j.compind.2003.08.00

  Article  Google Scholar 

• Staffetti, E., Ros, L., & Thomas, F. (1999a). Finding infinitesimal motions of objects in assemblies using grassmann-cayley algebra. In: Proceedings of the tenth world congress on the theory of machine and mechanisms (pp. 584–591).

• Staffetti, E., Ros, L., & Thomas, F. (1999b). A simple characterization of the infinitesimal motions separating general polyhedra in contact. In: Proceedings of the 1999 IEEE international conference on robotics and automation (ICRA) (pp. 571–577).

• Staffetti, E., Meeussen, W., & Xiao, J. (2005). A new formalism to characterize contact states involving articulated polyhedral objects. In: Proceedings of the 2005 IEEE international conference on robotics and automation (ICRA) (pp. 3619–3626).

• Sundaram, S., Remmler, I., & Amato, N. (2001). Disassembly sequencing using a motion planning approach. In: Proceedings of the IEEE international conference on robotics and automation (ICRA) (pp. 1475–1480).

• Suzuki, T., Kanehara, T., Inaba, A., & Okuma, S. (1993). On algebraic and graph structural properties of assembly petri net. In: Proceedings of the IEEE international conference on robotics and automation (ICRA) (pp. 507–514).

• Thomas F., Torras C. (1992) Inferring feasible assemblies from spatial constraints. IEEE Transactions on Robotics and Automation 8(2): 228–239

  Article  Google Scholar 

• Thomas, U., Barrenscheen, M., & Wahl, F. (2003). Efficient assembly sequence planning using stereographical projections of c-space obstacles. In: Proceedings of the 2003 IEEE international symposium on assembly and task planning (ISATP 2003) (pp. 96–102).

• Tseng H. E., Li R. K. (1999) A novel means of generating assembly sequences using the connector concept. Journal of Intelligent Manufacturing 10(5): 423–435. doi:10.1023/A:1008971030395

  Article  Google Scholar 

• Tseng H. E., Li J. D., Chang Y. H. (2004) Connector-based approach to assembly planning using a genetic algorithm. International Journal of Production Research 42: 2243–2261

  Article  Google Scholar 

• Wang J., Liu J., Zhong Y. (2005) A novel ant colony algorithm for assembly sequence planning. The International Journal of Advanced Manufacturing Technology 25(11–12): 1137–1143. doi:10.1007/s00170-003-1952-z

  Article  Google Scholar 

• Wang L., Keshavarzmaneh S., Feng H. Y., Buchal R. O. (2008) Assembly process planning and its future in collaborative manufacturing: a review. The International Journal of Advanced Manufacturing Technology 41(1–2): 132–144. doi:10.1007/s00170-008-1458-9

  Google Scholar 

• Wang W. P., Tseng H. E. (2009) Complexity estimation for genetic assembly sequence planning. Journal of the Chinese Institute of Industrial Engineers 26(1): 44–52

  Article  Google Scholar 

• Wilson, R., & Rit, J. (1990) Maintaining geometric dependencies in an assembly planner. In: Proceedings of the 1990 IEEE international conference on robotics and automation (vol. 2, pp. 890–895) Scottsdale, AZ.

• Wilson R. H., Latombe J. C. (1994) Geometric reasoning about mechanical assembly. Artificial Intelligence 71(2): 371–396

  Article  Google Scholar 

• Wilson R. H., Kavraki L., Lozano-Pérez T., Latombe J. C. (1995) Two-handed assembly sequencing. International Journal of Robotics Research 14(4): 335–350

  Article  Google Scholar 

• Wolter, J. (1991). A combinatorial analysis of enumerative data structures for assembly planning. In: Proceedings of the IEEE international conference on robotics and automation (pp 611–618). citeseer.ist.psu.edu/wolter91combinatorial.html

• Wolter, J., Chakrabarty, S., & Tsao, J. (1991). Mating constraint languages for assembly sequence planning. Technical Report 91-038, Texas A&M University.

• Wolter, J. D. (1989). On the automatic generation of assembly plans. In: Proceedings of the 1989 IEEE international conference on robotics and automation (vol. 1, pp. 62–68) Scottsdale, AZ.

• Xiao, J. (1993). Automatic determination of topological contacts in the presence of sensing uncertainties. In: Proceedings of the IEEE international conference on robotics and automation (ICRA) (pp. 65–70).

• Xiao, J., & Ji, X. (2000). A divide-and-merge approach to automatic generation of contact states and planning of contact motion. In: Proceedings of the IEEE international conference on robotics and automation (ICRA) (pp. 750–756).

• Xiao J., Ji X. (2001) Automatic generation of high-level contact state space. The International Journal of Robotics Research 20(7): 584–606

  Article  Google Scholar 

• Xiao, J., & Liu, L. (1998). Contact states: Representation and recognizability in the presence of uncertainties. In: Proceedings of the IEEE/RSJ international conference on intelligent robots and systems (pp. 1151–1156).

• Yuan X. (2002) An interactive approach of assembly planning. IEEE Transactions on Systems, Man, and Cybernetics Part A Systems and Humans 32(4): 522–526

  Article  Google Scholar 

• Zha X. F., Lim S. Y. E., Fok S. C. (1998a) Integrated intelligent design and assembly planning: A survey. The International Journal of Advanced Manufacturing Technology 14(9): 664–685. doi:10.1007/BF01192287

  Article  Google Scholar 

• Zha X. F., Lim S. Y. E., Fok S. C. (1998b) Integrated knowledge-based petri net intelligent flexible assembly planning. Journal of Intelligent Manufacturing 9(3): 235–250. doi:10.1023/A:1008862631701

  Article  Google Scholar 

• Zheng, Y., Pei, R., & Chen, C. (1991). Strategies for automatic assembly of deformable objects. In: Proceedings of 1991 IEEE international conference on robotics and automation (vol. 3, pp. 2598–2603). doi:10.1109/ROBOT.1991.132019.

Download references