{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,2]],"date-time":"2026-05-02T09:50:14Z","timestamp":1777715414591,"version":"3.51.4"},"reference-count":33,"publisher":"SAGE Publications","issue":"4","license":[{"start":{"date-parts":[[1995,8,1]],"date-time":"1995-08-01T00:00:00Z","timestamp":807235200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/journals.sagepub.com\/page\/policies\/text-and-data-mining-license"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["The International Journal of Robotics Research"],"published-print":{"date-parts":[[1995,8]]},"abstract":"<jats:p>\n                    <jats:italic toggle=\"yes\">This article considers the computational complexity of automat ically determining assembly sequences for mechanical products. Specifically, we address the partitioning problem: given an assembly of rigid parts, identify a proper subassembly that can be removed as a rigid object without disturbing the rest of the assembly. We examine the complexity of the partition ing problem under various types of relative motions allowed for the subassemblies. We show that when arbitrary motions are allowed to separate the two subassemblies, partitioning is NP-complete.<\/jats:italic>\n                  <\/jats:p>\n                  <jats:p>\n                    <jats:italic toggle=\"yes\">We then describe a general framework for reasoning about assembly motions called the interference diagram. In its most general form the interference diagram yields an exponential- time algorithm to partition an assembly. However, two special cases of the interference diagram studied in this article yield polynomial-time sequencing algorithms. The first case occurs when assembly motions are restricted to single translations. The second case considers infinitesimal rigid motions in translation and rotation and yields a superset of all feasible partitionings. These two algorithms have important practical applications in assembly planning.<\/jats:italic>\n                  <\/jats:p>","DOI":"10.1177\/027836499501400403","type":"journal-article","created":{"date-parts":[[2007,3,4]],"date-time":"2007-03-04T20:24:06Z","timestamp":1173039846000},"page":"335-350","source":"Crossref","is-referenced-by-count":44,"title":["Two-Handed Assembly Sequencing"],"prefix":"10.1177","volume":"14","author":[{"given":"Randall H.","family":"Wilson","sequence":"first","affiliation":[{"name":"Intelligent Systems and Robotics Center Sandia National Laboratories Albuquerque, New Mexico 87185-0951"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lydia","family":"Kavraki","sequence":"additional","affiliation":[{"name":"Computer Science Robotics Laboratory Stanford University Stanford, California 94305"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jean-Claude","family":"Latombe","sequence":"additional","affiliation":[{"name":"Computer Science Robotics Laboratory Stanford University Stanford, California 94305"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tom\u00e1s","family":"Lozano-P\u00e9rez","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology Artificial Intelligence Laboratory Cambridge, Massachusetts 02139"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"179","published-online":{"date-parts":[[1995,8]]},"reference":[{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/73833.73870"},{"key":"e_1_2_2_3_1","volume-title":"Algorithmic methods and software tools for the generation of mechanical assembly sequences. Master's thesis","author":"Baldwin, D.F.","year":"1990","unstructured":"Baldwin, D.F. 1990. Algorithmic methods and software tools for the generation of mechanical assembly sequences. Master's thesis. Massachusetts Institute of Technology."},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/70.68072"},{"key":"e_1_2_2_5_1","volume-title":"Assembly Automation and Product Design","author":"Boothroyd, G.","year":"1991","unstructured":"Boothroyd, G. 1991. Assembly Automation and Product Design. New York: Marcel Dekker."},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/147508.147511"},{"key":"e_1_2_2_7_1","first-page":"2404","article-title":"KBAP: An industrial prototype of knowledge-based assembly planner","author":"Delchambre, A.","year":"1992","unstructured":"Delchambre, A., and Gaspart, P. 1992. KBAP: An industrial prototype of knowledge-based assembly planner. Proc. of the IEEE Int. Conf. on Robotics and Automation , pp. 2404-2409.","journal-title":"Proc. of the IEEE Int. Conf. on Robotics and Automation"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-61568-9"},{"key":"e_1_2_2_9_1","volume-title":"MH-1: A Computer-Operated Mechanical Hand. Sc.D. thesis","author":"Ernst, H.A.","year":"1961","unstructured":"Ernst, H.A. 1961. MH-1: A Computer-Operated Mechanical Hand. Sc.D. thesis , Massachusetts Institute of Technology."},{"key":"e_1_2_2_10_1","volume-title":"Computers and Intractability","author":"Garey, M.R.","year":"1979","unstructured":"Garey, M.R., and Johnson, D.S. 1979. Computers and Intractability. San Francisco : W. H. Freeman."},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4613-8227-0"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.2172\/10190498"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/70.294206"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4615-4038-0_12"},{"key":"e_1_2_2_15_1","volume-title":"Computer-Aided Mechanical Assembly Planning","author":"L. S.","year":"1991","unstructured":"Homem de Mello, L. S., and Lee, S. (eds.). 1991. Computer-Aided Mechanical Assembly Planning. Boston: Kluwer Academic."},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/70.75905"},{"key":"e_1_2_2_17_1","volume-title":"Force feedback in precise assembly tasks","author":"Inoue, H.","year":"1974","unstructured":"Inoue, H. 1974. Force feedback in precise assembly tasks. Technical report AIM-308. AI Laboratory, Massachusetts Institute of Technology ."},{"key":"e_1_2_2_18_1","article-title":"Partitioning a planar assembly into two connected parts is NP-complete","author":"Kavraki, L.","unstructured":"Kavraki, L. and Kolountzakis, M.N. in press. Partitioning a planar assembly into two connected parts is NP-complete. Information Processing Letters.","journal-title":"Information Processing Letters"},{"key":"e_1_2_2_19_1","volume-title":"Complexity of partitioning a planar assembly","author":"Kavraki, L.","year":"1993","unstructured":"Kavraki, L., and Latombe, J.-C. 1993. Complexity of partitioning a planar assembly. Technical report STAN-CS-93-1467. Department of Computer Science, Stanford University."},{"key":"e_1_2_2_20_1","volume-title":"Graph certificates, lookahead in dynamic graph problems, and assembly planning in robotics (Tech. Rep. No. SAND94-3128)","author":"Khanna, S.","year":"1994","unstructured":"Khanna, S., Motwani, R., and Wilson, R.H. 1994. Graph certificates, lookahead in dynamic graph problems, and assembly planning in robotics (Tech. Rep. No. SAND94-3128). Albuquerque, NM: Sandia National Laboratories ."},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/0010-4485(87)90146-1"},{"key":"e_1_2_2_22_1","first-page":"428","article-title":"Path planning algorithms for assembly sequence planning","author":"Krishnan, S.S.","year":"1991","unstructured":"Krishnan, S.S., and Sanderson, A.C. 1991. Path planning algorithms for assembly sequence planning . Int. Conf. on Intelligent Robotics, pp. 428-439.","journal-title":"Int. Conf. on Intelligent Robotics"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1983.1676196"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01840373"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/73393.73424"},{"key":"e_1_2_2_26_1","volume-title":"An extension of screw theory and its application to the automation of industrial assemblies. Ph.D. dissertation","author":"Ohwovoriole, M.S.","year":"1980","unstructured":"Ohwovoriole, M.S. 1980. An extension of screw theory and its application to the automation of industrial assemblies. Ph.D. dissertation, Stanford University."},{"key":"e_1_2_2_27_1","volume-title":"Computational complexity of motion and stability of polygons. Ph.D. dissertation","author":"Palmer, R.S.","year":"1989","unstructured":"Palmer, R.S. 1989. Computational complexity of motion and stability of polygons. Ph.D. dissertation, Cornell University."},{"key":"e_1_2_2_28_1","first-page":"2329","article-title":"Mobility of bodies in contact\u2014I: A new second order mobility index for multiple-finger grasps","author":"Rimon, E.","year":"1994","unstructured":"Rimon, E., and Burdick, J. 1994. Mobility of bodies in contact\u2014I: A new second order mobility index for multiple-finger grasps. Proc. of the IEEE Int. Conf. on Robotics and Automation, pp. 2329-2335.","journal-title":"Proc. of the IEEE Int. Conf. on Robotics and Automation"},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1002\/cpa.3160360305"},{"key":"e_1_2_2_30_1","volume-title":"On geometric assembly planning","author":"Wilson, R.H.","year":"1992","unstructured":"Wilson, R.H. 1992. On geometric assembly planning. Ph.D. dissertation, Stanford University. Stanford technical report STAN-CS-92-1416."},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(94)90048-5"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.21236\/ADA326085"},{"key":"e_1_2_2_33_1","doi-asserted-by":"crossref","unstructured":"Wilson R.H. and Rit J-F. 1991. Maintaining geometric dependencies in assembly planning . In Homem de Mello L. S. and Lee S. (eds.): Computer-Aided Mechanical Assembly Planning. Boston: Kluwer Academic pp. 217-242.","DOI":"10.1007\/978-1-4615-4038-0_9"},{"key":"e_1_2_2_34_1","volume-title":"On the automatic generation of plans for mechanical assembly. Ph.D. dissertation","author":"Wolter, J.D.","year":"1988","unstructured":"Wolter, J.D. 1988. On the automatic generation of plans for mechanical assembly. Ph.D. dissertation, University of Michigan."}],"container-title":["The International Journal of Robotics Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/027836499501400403","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/027836499501400403","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T10:15:06Z","timestamp":1777457706000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/10.1177\/027836499501400403"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995,8]]},"references-count":33,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1995,8]]}},"alternative-id":["10.1177\/027836499501400403"],"URL":"https:\/\/doi.org\/10.1177\/027836499501400403","relation":{},"ISSN":["0278-3649","1741-3176"],"issn-type":[{"value":"0278-3649","type":"print"},{"value":"1741-3176","type":"electronic"}],"subject":[],"published":{"date-parts":[[1995,8]]}}}