{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,3]],"date-time":"2026-08-03T22:17:06Z","timestamp":1785795426910,"version":"3.56.0"},"reference-count":22,"publisher":"Springer Science and Business Media LLC","issue":"10","license":[{"start":{"date-parts":[[2022,9,8]],"date-time":"2022-09-08T00:00:00Z","timestamp":1662595200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,9,8]],"date-time":"2022-09-08T00:00:00Z","timestamp":1662595200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100008294","name":"Louisiana State University","doi-asserted-by":"publisher","award":["Faculty Travel Grant"],"award-info":[{"award-number":["Faculty Travel Grant"]}],"id":[{"id":"10.13039\/100008294","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["EP\/V009877\/1"],"award-info":[{"award-number":["EP\/V009877\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100008982","name":"National Science Foundation","doi-asserted-by":"publisher","award":["DMS 1811071"],"award-info":[{"award-number":["DMS 1811071"]}],"id":[{"id":"10.13039\/501100008982","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Ann Math Artif Intell"],"published-print":{"date-parts":[[2022,10]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Parametrized motion planning algorithms have high degrees of universality and flexibility, as they are designed to work under a variety of external conditions, which are viewed as parameters and form part of the input of the underlying motion planning problem. In this paper, we analyze the parametrized motion planning problem for the motion of many distinct points in the plane, moving without collision and avoiding multiple distinct obstacles with a priori unknown positions. This complements our prior work Cohen et al. [3] (SIAM J. Appl. Algebra Geom. <jats:bold>5<\/jats:bold>, 229\u2013249), where parametrized motion planning algorithms were introduced, and the obstacle-avoiding collision-free motion planning problem in three-dimensional space was fully investigated. The planar case requires different algebraic and topological tools than its spatial analog.<\/jats:p>","DOI":"10.1007\/s10472-022-09801-6","type":"journal-article","created":{"date-parts":[[2022,9,8]],"date-time":"2022-09-08T05:02:47Z","timestamp":1662613367000},"page":"999-1015","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":10,"title":["Parametrized topological complexity of collision-free motion planning in the plane"],"prefix":"10.1007","volume":"90","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-5845-2523","authenticated-orcid":false,"given":"Daniel C.","family":"Cohen","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Michael","family":"Farber","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Shmuel","family":"Weinberger","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2022,9,8]]},"reference":[{"key":"9801_CR1","doi-asserted-by":"publisher","first-page":"1200","DOI":"10.1112\/jtopol\/jtu018","volume":"7","author":"K Adiprasito","year":"2014","unstructured":"Adiprasito, K.: Combinatorial stratifications and minimality of 2-arrangements. J. Topol. 7, 1200\u20131220 (2014). MR3286901","journal-title":"J. Topol."},{"key":"9801_CR2","doi-asserted-by":"crossref","unstructured":"Cohen, D.: Topological complexity of classical configuration spaces and related objects. In: Topological complexity and related topics pp. 41\u201360, Contemp. Math., vol. 702, Amer. Math. Soc., Providence, RI. MR3762831 (2018)","DOI":"10.1090\/conm\/702\/14104"},{"key":"9801_CR3","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1137\/20M1358505","volume":"5","author":"D Cohen","year":"2021","unstructured":"Cohen, D., Farber, M., Weinberger, S.: Topology of parametrized motion planning algorithms. SIAM J. Appl. Algebra Geom. 5, 229\u2013249 (2021). MR4272901","journal-title":"SIAM J. Appl. Algebra Geom."},{"key":"9801_CR4","doi-asserted-by":"publisher","first-page":"625","DOI":"10.1007\/PL00004452","volume":"319","author":"M de Longueville","year":"2001","unstructured":"de Longueville, M., Schultz, C.: The cohomology rings of complements of subspace arrangements. Math. Ann. 319, 625\u2013646 (2001). MR1825401","journal-title":"Math. Ann."},{"key":"9801_CR5","doi-asserted-by":"publisher","first-page":"4547","DOI":"10.1090\/proc\/15094","volume":"148","author":"A Dranishnikov","year":"2020","unstructured":"Dranishnikov, A.: On topological complexity of hyperbolic groups. Proc. Amer. Math. Soc. 148, 4547\u20134556 (2020). MR4135318","journal-title":"Proc. Amer. Math. Soc."},{"key":"9801_CR6","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-56446-8","volume-title":"Geometry and Topology of Configuration Spaces, Springer Monographs in Mathematics","author":"E Fadell","year":"2001","unstructured":"Fadell, E., Husseini, S.: Geometry and Topology of Configuration Spaces, Springer Monographs in Mathematics. Springer, Berlin (2001). MR1802664"},{"key":"9801_CR7","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1007\/s00454-002-0760-9","volume":"29","author":"M Farber","year":"2003","unstructured":"Farber, M.: Topological complexity of motion planning. Discrete Comput. Geom. 29, 211\u2013221 (2003). MR1957228","journal-title":"Discrete Comput. Geom."},{"key":"9801_CR8","doi-asserted-by":"crossref","unstructured":"Farber, M.: Topology of robot motion planning. In: Morse Theoretic Methods in Non-linear Analysis and in Symplectic Topology, pp. 185\u2013230, NATO Science Series II: Mathematics, Physics and Chemistry. vol. 217. Springer (2006).\u00a0MR2276952","DOI":"10.1007\/1-4020-4266-3_05"},{"key":"9801_CR9","doi-asserted-by":"crossref","unstructured":"Farber, M.: Configuration spaces and robot motion planning algorithms. In: Combinatorial and Toric Homotopy: Introductory Lectures, pp. 263\u2013303, Lect. Notes Ser. Inst. Math. Sci. Natl. Univ. Singap., vol. 35, World Sci. Publ., Hackensack, NJ. (2018).\u00a0MR3792464","DOI":"10.1142\/9789813226579_0005"},{"key":"9801_CR10","doi-asserted-by":"publisher","first-page":"1841","DOI":"10.1090\/S0002-9939-08-09808-0","volume":"137","author":"M Farber","year":"2009","unstructured":"Farber, M., Grant, M.: Topological complexity of configuration spaces. Proc. Amer. Math. Soc. 137, 1841\u20131847 (2009). MR2470845","journal-title":"Proc. Amer. Math. Soc."},{"key":"9801_CR11","doi-asserted-by":"crossref","unstructured":"Farber, M., Grant, M., Yuzvinsky, S.: Topological complexity of collision free motion planning algorithms in the presence of multiple moving obstacles. In: Topology and Robotics, pp. 75\u201383, Contemp. Math., vol. 438, Amer. Math. Soc., Providence, RI. (2007).\u00a0MR2359030","DOI":"10.1090\/conm\/438\/08446"},{"key":"9801_CR12","volume-title":"Stratified Morse theory, Ergebnisse der Mathematik und ihrer Grenzgebiete (3) 14","author":"M Goresky","year":"1988","unstructured":"Goresky, M., MacPherson, R.: Stratified Morse theory, Ergebnisse der Mathematik und ihrer Grenzgebiete (3) 14. Springer, Berlin (1988). MR0932724"},{"key":"9801_CR13","doi-asserted-by":"publisher","first-page":"667","DOI":"10.1007\/s00209-019-02366-x","volume":"295","author":"M Grant","year":"2020","unstructured":"Grant, M., Mescher, S.: Topological complexity of symplectic manifolds. Math. Z. 295, 667\u2013679 (2020). MR4100027","journal-title":"Math. Z."},{"key":"9801_CR14","doi-asserted-by":"publisher","first-page":"2050040, 19","DOI":"10.1142\/S1793830920500408","volume":"12","author":"C Ipanaque Zapata","year":"2020","unstructured":"Ipanaque Zapata, C., Gonz\u00e1lez, J.: Multitasking collision-free optimal motion planning algorithms in Euclidean spaces. Discrete Math. Algorithms Appl. 12, 2050040, 19 (2020). MR4120432","journal-title":"Discrete Math. Algorithms Appl."},{"key":"9801_CR15","unstructured":"Latombe, J.-C.: Robot Motion Planning, Springer Science Springer Science+Business Media New York, Business Media New York (2012)"},{"key":"9801_CR16","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511546877","volume-title":"Planning Algorithms","author":"SM LaValle","year":"2006","unstructured":"LaValle, S.M.: Planning Algorithms. Cambridge University Press, Cambridge (2006). MR2424564"},{"key":"9801_CR17","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1142\/S179352532050003X","volume":"13","author":"A Murillo","year":"2021","unstructured":"Murillo, A., Wu, J.: Topological complexity of the work map. J. Topol. Anal. 13, 219\u2013238 (2021). MR4243078","journal-title":"J. Topol. Anal."},{"key":"9801_CR18","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-02772-1","volume-title":"Arrangements of hyperplanes, Grundlehren Math. Wiss, vol. 300","author":"P Orlik","year":"1992","unstructured":"Orlik, P., Terao, H.: Arrangements of hyperplanes, Grundlehren Math. Wiss, vol. 300. Springer, New York (1992). MR1217488"},{"key":"9801_CR19","doi-asserted-by":"publisher","first-page":"107","DOI":"10.4310\/HHA.2019.v21.n2.a7","volume":"21","author":"P Paves\u0306i\u0107","year":"2019","unstructured":"Paves\u0306i\u0107, P.: Topological complexity of a map. Homology Homotopy Appl 21, 107\u2013130 (2019). MR3921612","journal-title":"Homology Homotopy Appl"},{"key":"9801_CR20","first-page":"49","volume":"55","author":"AS Schwarz","year":"1966","unstructured":"Schwarz, A.S.: The genus of a fiber space. Amer. Math. Sci. Transl. 55, 49\u2013140 (1966). MR0154284","journal-title":"Amer. Math. Sci. Transl."},{"key":"9801_CR21","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1090\/S0273-0979-1981-14858-8","volume":"4","author":"S Smale","year":"1981","unstructured":"Smale, S.: The fundamental theorem of algebra and complexity theory. Bull. Amer. Math. Soc. (N.S.) 4, 1\u201336 (1981). MR0590817","journal-title":"Bull. Amer. Math. Soc. (N.S.)"},{"key":"9801_CR22","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4684-9322-1","volume-title":"Algebraic Topology, corrected reprint","author":"E Spanier","year":"1981","unstructured":"Spanier, E.: Algebraic Topology, corrected reprint. Springer, New York (1981). MR066655"}],"updated-by":[{"DOI":"10.1007\/s10472-022-09821-2","type":"correction","label":"Correction","source":"publisher","updated":{"date-parts":[[2022,12,1]],"date-time":"2022-12-01T00:00:00Z","timestamp":1669852800000}}],"container-title":["Annals of Mathematics and Artificial Intelligence"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10472-022-09801-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10472-022-09801-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10472-022-09801-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,1]],"date-time":"2022-12-01T05:12:42Z","timestamp":1669871562000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10472-022-09801-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,9,8]]},"references-count":22,"journal-issue":{"issue":"10","published-print":{"date-parts":[[2022,10]]}},"alternative-id":["9801"],"URL":"https:\/\/doi.org\/10.1007\/s10472-022-09801-6","relation":{"correction":[{"id-type":"doi","id":"10.1007\/s10472-022-09821-2","asserted-by":"object"}]},"ISSN":["1012-2443","1573-7470"],"issn-type":[{"value":"1012-2443","type":"print"},{"value":"1573-7470","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,9,8]]},"assertion":[{"value":"30 May 2022","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 September 2022","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 December 2022","order":3,"name":"change_date","label":"Change Date","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"Correction","order":4,"name":"change_type","label":"Change Type","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"A Correction to this paper has been published:","order":5,"name":"change_details","label":"Change Details","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"https:\/\/doi.org\/10.1007\/s10472-022-09821-2","URL":"https:\/\/doi.org\/10.1007\/s10472-022-09821-2","order":6,"name":"change_details","label":"Change Details","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"<!--Emphasis Type='Bold' removed-->Conflict of Interests"}}]}}