IP Library › Granted Patent US 12,358,140
Granted Patent B2
US 12,358,140 · App. 16/909,096 · Granted Jul 15, 2025

Motion planning for multiple robots in shared workspace

Inventors: Sean Murray (Cambridge, MA); William Floyd-Jones (Boston, MA); Xianchao Long (Boston, MA)
Assignee: REALTIME ROBOTICS, INC.
B25J9/1666B25J9/1605B25J9/1682G05B2219/35148G05B2219/40446G05B2219/40475G05B2219/40512
View Patent ↗
Loading inventors, assignments & file history…
Monitor This Case
Get email alerts when status or documents change.
Order Certified Copies
Most orders are placed with the USPTO same day — all within 24 business hours.
Order via The Patent Place →
Pre-filled with this patent's details
Quick Facts
Patent No.
US 12,358,140
App. No.
16/909,096
Granted
Jul 15, 2025
Kind
B2
Abstract

Collision detection useful in motion planning for robotics advantageously represents planned motions of each of a plurality of robots as obstacles when performing motion planning for any given robot in the plurality of robots that operate in a shared workspace, including taking into account the planned motions during collision assessment. Edges of a motion planning graph are assigned cost values, based at least in part on the collision assessment. Obstacles may be pruned as corresponding motions are completed. Motion planning requests may be queued, and some robots skipped, for example in response to an error or blocked condition.

Claims (67)

1. A method of controlling a plurality of robots to operate in a common workspace in which a range of motion of the robots overlap, the method comprising:

generating, by at least one processor, a first motion plan for a robot R 1 of the plurality of robots, wherein the first motion plan for the robot R 1 is in a digital form;

for each of at least one of the robots R i , from i equals 2 to i equals n where n is a total number of the robots in the plurality of robots and n is an integer that is equal to or greater than 2,

representing, by the at least one processor, a number of motions of at least the robot R 1 as at least one obstacle, wherein the representation of the number of motions of at least the robot R 1 as at least one obstacle is in a digital form;

performing, by the at least one processor, collision detection for at least one motion of at least a portion of the robot R i with respect to the representation of the at least one obstacle;

generating, by the at least one processor, a first motion plan for the robot R i based at least in part on the collision detection for the at least one motion of at least the portion of the robot R i , wherein the first motion plan for the robot R i is in a digital form;

executing, by the at least one processor, the respective first motion plan for a corresponding one of the plurality of robots to control operation of at least one of the robots R 1 through R n ; and

in response to completion of at least one motion by the robot R 1 , updating, by the at least one processor, a representation of obstacles to eliminate portions corresponding to the completed at least one motion by the robot R 1 .

2. The method of claim 1 , further comprising:

in response to completion of at least one motion by any one or more of the robots R 2 through R n , updating, by the at least one processor, a representation of obstacles to eliminate portions corresponding to the completed at least one motion by a respective one of the robots R 2 through R n .

3. The method of claim 1 , further comprising:

generating, by the at least one processor, a second motion plan for the robot R 1 of the plurality of robots;

for each of at least one of the robots R i , from i equals 2 to i equals n where n is a total number of the robots in the plurality of robots and n is an integer that is equal to or greater than 2,

representing, by the at least one processor, a number of motions of at least the robot R 1 as at least one obstacle;

performing, by the at least one processor, collision detection for at least one motion of at least a portion of the robot R i with respect to the representation of the at least one obstacle; and

generating, by the at least one processor, a second motion plan for the robot R i based at least in part on the collision detection for the at least one motion of at least the portion of the robot R i ; and the method further comprising:

executing, by the at least one processor, the respective second motion plan for the corresponding one of the plurality of robots to control operation of at least one of the robots R 1 through R n .

4. The method of claim 3 wherein the generating a first motion plan for the robots R 1 through R n occurs in succession from i equals 1 to i equals n.

5. The method of claim 4 wherein the generating a second motion plan for the robots R 1 through R n occurs in succession from i equals 1 to i equals n.

6. The method of claim 4 wherein the generating a second motion plan for the robots R 1 through R n does not occur in succession from i equals 1 to i equals n.

7. The method of claim 3 wherein executing the respective first motion plan for the corresponding one of the plurality of robots to control operation of at least one of the robots R 1 through R n includes providing signals that cause one robot R i to move before the robot R 1 , and wherein:

the updating, by the at least one processor, a representation of obstacles to eliminate portions corresponding to the completed at least one motion by the robot R i in response to completion of at least one motion by the robot R i occurs before performing the generating a second motion plan for the robot R 1 of the plurality of robots.

8. The method of claim 1 , further comprising:

generating, by the at least one processor, a second motion plan for the robot R 1 of the plurality of robots;

for some but not all of two or more robots R i , from i equals 2 to i equals n where n is a total number of the robots in the plurality of robots and n is an integer that is equal to or greater than 3,

representing, by the at least one processor, a number of motions of at least the robot R 1 as at least one obstacle;

performing, by the at least one processor, collision detection for at least one motion of at least a portion of the robot R i with respect to the representation of the at least one obstacle; and

generating, by the at least one processor, a second motion plan for the robot R i based at least in part on the collision detection for the at least one motion of at least the portion of the robot R i ; and the method further comprising:

executing, by the at least one processor, the respective second motion plan for the corresponding one of the plurality of robots to control operation of at least one of the robots R 1 through R n .

9. The method of claim 8 wherein the generating a second motion plan for one of the robots R 2 through R n is skipped.

10. The method of claim 8 wherein the generating a second motion plan for one of the robots R 2 through R n is skipped in response to a respective one of the robots R 2 through R n being blocked from movement by another one of the robots R 2 through R n .

11. The method of claim 8 wherein the generating a second motion plan for one of the robots R 2 through R n is skipped in response to a respective one of the robots R 2 through R n having an error state that indicates an error condition has occurred.

12. The method of claim 1 wherein representing a number of motions of at least the robot R 1 as at least one obstacle includes, for at least one robot R i+1 , representing the motion of two or more of the robots R 1 through R i as obstacles before performing the collision detection for the at least one motion of the robot R i+1 .

13. The method of claim 12 wherein representing the motion of two or more of robots R 1 through R i as obstacles before performing the collision detection for the at least one motion of the robot R i+1 includes: using a set of swept volumes previously computed at a pre-runtime, the swept volumes each of which represents a respective volume swept by at least a portion of the respective one of the robots R 1 through R i as the portion of the respective one of the robots R 1 through R i moves along a trajectory represented by the respective motion.

14. The method of claim 12 , further comprising:

receiving, by the at least one processor, a set of swept volumes previously computed at a pre-runtime, the swept volumes each of which represents a respective volume swept by at least a portion of the respective one of the robots R 1 through R i as the portion of the respective one of the robots R 1 through R i moves along a trajectory represented by the respective motion.

15. The method of claim 12 wherein representing the motion of two or more of the robots R 1 through R i as obstacles before performing the collision detection for the at least one motion of the robot R i+1 includes: representing the motion of two or more of the robots R 1 through R i as at least one of: an occupancy grid, a hierarchical tree or a Euclidean distance field.

16. The method of claim 1 wherein representing each of the motions of at least the robot R 1 as at least one obstacle includes using a respective swept volume to represent the respective motion, the swept volume corresponding to a volume swept by at least a portion of at least the robot R 1 during the respective motion and wherein performing collision detection for at least one motion of at least a portion of the robot R i with respect to the representation of the at least one obstacle includes performing collision detection using a representation of the swept volume which was previously computed at a pre-runtime, the pre-runtime which occurs before a runtime, the runtime being a time during which at least one of the robots performs tasks.

17. The method of claim 1 , further comprising:

for each of the robots R 1 through R n of the plurality of robots, representing, by the at least one processor, the respective robot via a respective motion planning graph, each motion planning graph comprising a plurality of nodes and edges, the nodes which represent respective states of the respective robot and the edges which represent valid transitions between respective states represented by the respective ones of a respective pair of nodes connected by the edge.

18. A system to control a plurality of robots to operate in a common workspace in which a range of motion of the robots overlap, the system comprising:

at least one processor; and

at least one nontransitory storage medium communicatively coupled to the at least one processor and that stores processor-executable instructions which, when executed by the at least one processor, cause the at least one processor to:

generate, by the at least one processor, a first motion plan for a robot R 1 of the plurality of robots;

for each of at least one of the robots R i , from i equals 2 to i equals n where n is a total number of the robots in the plurality of robots and n is an integer that is equal to or greater than 2,

represent, by the at least one processor, a number of motions of at least the robot R 1 as at least one obstacle;

perform collision detection, by the at least one processor, for at least one motion of at least a portion of the robot R i with respect to the representation of the at least one obstacle;

generate, by the at least one processor, a first motion plan for the robot R i based at least in part on the collision detection for the at least one motion of at least the portion of the robot R i ;

executing, by the at least one processor, a respective first motion plan for the corresponding one of the plurality of robots to control operation of at least one of the robots R 1 through R n ; and

in response to completion of at least one motion by the robot R 1 , update a representation of obstacles, by the at least one processor, to eliminate portions corresponding to the completed at least one motion by the robot R 1 .

19. The system of claim 18 wherein, when executed by the at least one processor, the processor-executable instructions cause the at least one processor further to:

in response to completion of at least one motion by any one or more of the robots R 2 through R n , update a representation of obstacles to eliminate portions corresponding to the completed at least one motion by a respective one of the robots R 2 through R n .

20. The system of claim 18 wherein, when executed by the at least one processor, the processor-executable instructions cause the at least one processor further to:

generate a second motion plan for the robot R 1 of the plurality of robots;

for each of at least one of the robots R i , from i equals 2 to i equals n where n is a total number of the robots in the plurality of robots and n is an integer that is equal to or greater than 2,

represent a number of motions of at least the robot R 1 as at least one obstacle;

perform collision detection for at least one motion of at least a portion of the robot R i with respect to the representation of the at least one obstacle; and

generate a second motion plan for the robot R i based at least in part on the collision detection for the at least one motion of at least the portion of the robot R i ; and further:

provide signals to control operation of at least one of the robots R 1 through R n based at least in part on the respective second motion plan for the corresponding one of the plurality of robots.

21. The system of claim 18 wherein, when executed by the at least one processor, the processor-executable instructions cause the at least one processor further to:

generate a second motion plan for the robot R 1 of the plurality of robots;

for some but not all of two or more robots R i , from i equals 2 to i equals n where n is a total number of the robots in the plurality of robots and n is an integer that is equal to or greater than 3,

represent a number of motions of at least the robot R 1 as at least one obstacle;

perform collision detection for at least one motion of at least a portion of the robot R i with respect to the representation of the at least one obstacle;

generate a second motion plan for the robot R i based at least in part on the collision detection for the at least one motion of at least the portion of the robot R i ; and

execute, by the at least one processor the respective second motion plan for the corresponding one of the plurality of robots to control operation of at least one of the robots R 1 through R n , and wherein:

the generation of a second motion plan for one of the robots R 2 through R n is skipped in response to a respective one of the robots R 2 through the R n being blocked from movement by another one of the robots R 2 through R n .

Assignments (2)
SECURITY INTEREST Recorded Oct 22, 2025
From: REALTIME ROBOTICS, INC.
To: FIRST-CITIZENS BANK & TRUST COMPANY
Reel/Frame 074155/0025 →
ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded Sep 3, 2020
From: MURRAY, SEAN; FLOYD-JONES, WILLIAM; LONG, XIANCHAO
To: REALTIME ROBOTICS, INC.
Reel/Frame 053685/0430 →
Continuity (2)
Provisional Application 62865431 · Jun 24, 2019
Related Publication 20200398428A1 · Dec 24, 2020
References Cited (400)
US 4163183A · Dunne et al. · 1979 [cited by applicant]
US 4300198A · Davini · 1981 [cited by applicant]
US 4763276A · Perreirra et al. · 1988 [cited by applicant]
US 4862373A · Meng · 1989 [cited by applicant]
US 4890241A · Hoffman et al. · 1989 [cited by applicant]
US 4949277A · Trovato et al. · 1990 [cited by applicant]
US 5177563A · Everett et al. · 1993 [cited by applicant]
US 5297238A · Wang et al. · 1994 [cited by applicant]
US 5347459A · Greenspan et al. · 1994 [cited by applicant]
US 5544282A · Chen et al. · 1996 [cited by applicant]
US 5727132A · Arimatsu et al. · 1998 [cited by applicant]
US 6004016A · Spector · 1999 [cited by applicant]
US 6049756A · Libby · 2000 [cited by applicant]
US 6089742A · Warmerdam et al. · 2000 [cited by applicant]
US 6259988B1 · Galkowski et al. · 2001 [cited by applicant]
US 6345213B1 · Graeser et al. · 2002 [cited by applicant]
US 6470301B1 · Barral · 2002 [cited by applicant]
US 6493607B1 · Bourne et al. · 2002 [cited by applicant]
US 6526372B1 · Orschel et al. · 2003 [cited by applicant]
US 6526373B1 · Barral · 2003 [cited by applicant]
US 6529852B2 · Knoll et al. · 2003 [cited by applicant]
US 6539294B1 · Kageyama · 2003 [cited by applicant]
US 6629037B1 · Nyland · 2003 [cited by applicant]
US 6671582B1 · Hanley · 2003 [cited by applicant]
US 6836702B1 · Brogaardh et al. · 2004 [cited by applicant]
US 6907133B2 · Gotoh · 2005 [cited by applicant]
US 6944584B1 · Tenney et al. · 2005 [cited by applicant]
US 7493231B2 · Graf · 2009 [cited by applicant]
US 7577498B2 · Jennings et al. · 2009 [cited by applicant]
US 7609020B2 · Kniss et al. · 2009 [cited by applicant]
US 7715946B2 · Watanabe et al. · 2010 [cited by applicant]
US 7865277B1 · Arson et al. · 2011 [cited by applicant]
US 7904202B2 · Hoppe · 2011 [cited by applicant]
US 7940023B2 · Kniss et al. · 2011 [cited by applicant]
US 8082064B2 · Kay · 2011 [cited by applicant]
US 8103085B1 · Zadeh · 2012 [cited by applicant]
US 8111904B2 · Wallack et al. · 2012 [cited by applicant]
US 8162584B2 · Michael et al. · 2012 [cited by applicant]
US 8315738B2 · Chang et al. · 2012 [cited by applicant]
US 8571706B2 · Zhang et al. · 2013 [cited by applicant]
US 8666548B2 · Lim · 2014 [cited by applicant]
US 8825207B2 · Kim et al. · 2014 [cited by applicant]
US 8825208B1 · Benson · 2014 [cited by applicant]
US 8855812B2 · Kapoor · 2014 [cited by applicant]
US 8880216B2 · Izumi et al. · 2014 [cited by applicant]
US 8972057B1 · Freeman et al. · 2015 [cited by applicant]
US 8989897B2 · De Smet · 2015 [cited by applicant]
US 9061421B2 · Trompeter · 2015 [cited by applicant]
US 9092698B2 · Buehler et al. · 2015 [cited by applicant]
US 9102055B1 · Konolige et al. · 2015 [cited by applicant]
US 9227322B2 · Graca et al. · 2016 [cited by applicant]
US 9280899B2 · Biess et al. · 2016 [cited by applicant]
US 9327397B1 · Williams et al. · 2016 [cited by applicant]
US 9333044B2 · Olson · 2016 [cited by applicant]
US 9434072B2 · Buehler et al. · 2016 [cited by applicant]
US 9539058B2 · Tsekos et al. · 2017 [cited by applicant]
US 9632502B1 · Levinson et al. · 2017 [cited by applicant]
US 9645577B1 · Frazzoli et al. · 2017 [cited by applicant]
US 9659236B2 · Barker et al. · 2017 [cited by applicant]
US 9687982B1 · Jules et al. · 2017 [cited by applicant]
US 9687983B1 · Prats · 2017 [cited by applicant]
US 9701015B2 · Buehler et al. · 2017 [cited by applicant]
US 9707682B1 · Konolige et al. · 2017 [cited by applicant]
US 9731724B2 · Yoon · 2017 [cited by applicant]
US 9981382B1 · Strauss et al. · 2018 [cited by applicant]
US 9981383B1 · Nagarajan · 2018 [cited by applicant]
US 10035266B1 · Kroeger · 2018 [cited by applicant]
US 10099372B2 · Vu et al. · 2018 [cited by applicant]
US 10124488B2 · Lee et al. · 2018 [cited by applicant]
US 10131053B1 · Sampedro et al. · 2018 [cited by applicant]
US 10300605B2 · Sato · 2019 [cited by applicant]
US 10303180B1 · Prats · 2019 [cited by applicant]
US 10430641B2 · Gao · 2019 [cited by applicant]
US 10671081B1 · Prats · 2020 [cited by applicant]
US 10688664B2 · Kovacs · 2020 [cited by applicant]
US 10705528B2 · Wierzynski et al. · 2020 [cited by applicant]
US 10723024B2 · Konidaris et al. · 2020 [cited by applicant]
US 10782694B2 · Zhang et al. · 2020 [cited by applicant]
US 10792114B2 · Hashimoto et al. · 2020 [cited by applicant]
US 10959795B2 · Hashimoto et al. · 2021 [cited by applicant]
US 11314254B2 · Macias et al. · 2022 [cited by applicant]
US 11358337B2 · Czinger et al. · 2022 [cited by applicant]
US 11407117B1 · Hickman · 2022 [cited by applicant]
US 11623494B1 · Arnicar et al. · 2023 [cited by applicant]
US 11751948B2 · Gregerson et al. · 2023 [cited by applicant]
US 20020013675A1 · Knoll et al. · 2002 [cited by applicant]
US 20020074964A1 · Quaschner et al. · 2002 [cited by applicant]
US 20050071048A1 · Watanabe et al. · 2005 [cited by applicant]
US 20050216181A1 · Estkowski et al. · 2005 [cited by applicant]
US 20060235610A1 · Ariyur et al. · 2006 [cited by applicant]
US 20060241813A1 · Babu et al. · 2006 [cited by applicant]
US 20060247852A1 · Kortge et al. · 2006 [cited by applicant]
US 20070106422A1 · Jennings et al. · 2007 [cited by applicant]
US 20070112700A1 · Den et al. · 2007 [cited by applicant]
US 20070239315A1 · Sato et al. · 2007 [cited by applicant]
US 20080012517A1 · Kniss et al. · 2008 [cited by applicant]
US 20080125893A1 · Tilove et al. · 2008 [cited by applicant]
US 20080186312A1 · Ahn et al. · 2008 [cited by applicant]
US 20080234864A1 · Sugiura et al. · 2008 [cited by applicant]
US 20090055024A1 · Kay · 2009 [cited by applicant]
US 20090192710A1 · Eidehall et al. · 2009 [cited by applicant]
US 20090234499A1 · Nielsen et al. · 2009 [cited by applicant]
US 20090326711A1 · Chang et al. · 2009 [cited by applicant]
US 20090326876A1 · Miller · 2009 [cited by applicant]
US 20100145516A1 · Cedoz et al. · 2010 [cited by applicant]
US 20100235033A1 · Yamamoto et al. · 2010 [cited by applicant]
US 20110036188A1 · Fujioka et al. · 2011 [cited by applicant]
US 20110066282A1 · Bosscher et al. · 2011 [cited by applicant]
US 20110153080A1 · Shapiro et al. · 2011 [cited by applicant]
US 20110222995A1 · Irie et al. · 2011 [cited by applicant]
US 20110264111A1 · Nowlin et al. · 2011 [cited by applicant]
US 20120010772A1 · Pack et al. · 2012 [cited by applicant]
US 20120053728A1 · Theodorus et al. · 2012 [cited by applicant]
US 20120083964A1 · Montemerlo et al. · 2012 [cited by applicant]
US 20120215351A1 · Mcgee et al. · 2012 [cited by applicant]
US 20120297733A1 · Pierson et al. · 2012 [cited by applicant]
US 20120323357A1 · Izumi et al. · 2012 [cited by applicant]
US 20130076866A1 · Drinkard et al. · 2013 [cited by applicant]
US 20130325244A1 · Wang et al. · 2013 [cited by applicant]
US 20130346348A1 · Buehler et al. · 2013 [cited by applicant]
US 20140012419A1 · Nakajima · 2014 [cited by applicant]
US 20140025201A1 · Ryu et al. · 2014 [cited by applicant]
US 20140025203A1 · Inazumi · 2014 [cited by applicant]
US 20140058406A1 · Tsekos · 2014 [cited by applicant]
US 20140067121A1 · Brooks et al. · 2014 [cited by applicant]
US 20140079524A1 · Shimono et al. · 2014 [cited by applicant]
US 20140121833A1 · Lee et al. · 2014 [cited by applicant]
US 20140121837A1 · Hashiguchi et al. · 2014 [cited by applicant]
US 20140147240A1 · Noda et al. · 2014 [cited by applicant]
US 20140156068A1 · Graca et al. · 2014 [cited by applicant]
US 20140249741A1 · Levien et al. · 2014 [cited by applicant]
US 20140251702A1 · Berger et al. · 2014 [cited by applicant]
US 20140277718A1 · Izhikevich et al. · 2014 [cited by applicant]
US 20140305227A1 · Johns · 2014 [cited by applicant]
US 20140309916A1 · Bushnell · 2014 [cited by applicant]
US 20140368504A1 · Chen et al. · 2014 [cited by applicant]
US 20150005785A1 · Olson · 2015 [cited by applicant]
US 20150037131A1 · Girtman et al. · 2015 [cited by applicant]
US 20150051783A1 · Tamir et al. · 2015 [cited by applicant]
US 20150134111A1 · Nakajima · 2015 [cited by applicant]
US 20150217455A1 · Kikkeri et al. · 2015 [cited by applicant]
US 20150261899A1 · Atohira et al. · 2015 [cited by applicant]
US 20150266182A1 · Strandberg · 2015 [cited by applicant]
US 20160001775A1 · Wilhelm et al. · 2016 [cited by applicant]
US 20160008078A1 · Azizian et al. · 2016 [cited by applicant]
US 20160016312A1 · Lawrence et al. · 2016 [cited by applicant]
US 20160059412A1 · Oleynik · 2016 [cited by applicant]
US 20160107313A1 · Hoffmann et al. · 2016 [cited by applicant]
US 20160112694A1 · Nishi et al. · 2016 [cited by applicant]
US 20160121486A1 · Lipinski et al. · 2016 [cited by applicant]
US 20160121487A1 · Mohan · 2016 [cited by examiner]
US 20160154408A1 · Eade et al. · 2016 [cited by applicant]
US 20160161257A1 · Simpson et al. · 2016 [cited by applicant]
US 20160299507A1 · Shah et al. · 2016 [cited by applicant]
US 20160324587A1 · Olson · 2016 [cited by applicant]
US 20160357187A1 · Ansari · 2016 [cited by applicant]
US 20170001775A1 · Cimmerer et al. · 2017 [cited by applicant]
US 20170004406A1 · Aghamohammadi · 2017 [cited by applicant]
US 20170028559A1 · Davidi · 2017 [cited by examiner]
US 20170120448A1 · Lee et al. · 2017 [cited by applicant]
US 20170123419A1 · Levinson et al. · 2017 [cited by applicant]
US 20170132334A1 · Levinson et al. · 2017 [cited by applicant]
US 20170146999A1 · Cherepinsky et al. · 2017 [cited by applicant]
US 20170157769A1 · Aghamohammadi et al. · 2017 [cited by applicant]
US 20170168485A1 · Berntorp et al. · 2017 [cited by applicant]
US 20170168488A1 · Wierzynski et al. · 2017 [cited by applicant]
US 20170193830A1 · Fragoso et al. · 2017 [cited by applicant]
US 20170210008A1 · Maeda · 2017 [cited by examiner]
US 20170219353A1 · Alesiani · 2017 [cited by applicant]
US 20170252922A1 · Levine et al. · 2017 [cited by applicant]
US 20170252924A1 · Vijayanarasimhan et al. · 2017 [cited by applicant]
US 20170305015A1 · Krasny et al. · 2017 [cited by applicant]
US 20170315530A1 · Godau et al. · 2017 [cited by applicant]
US 20180001472A1 · Konidaris et al. · 2018 [cited by applicant]
US 20180001476A1 · Tan · 2018 [cited by examiner]
US 20180029231A1 · Davis · 2018 [cited by applicant]
US 20180029233A1 · Lager · 2018 [cited by applicant]
US 20180032039A1 · Huynh et al. · 2018 [cited by applicant]
US 20180074505A1 · Lv et al. · 2018 [cited by applicant]
US 20180113468A1 · Russell · 2018 [cited by applicant]
US 20180136662A1 · Kim · 2018 [cited by applicant]
US 20180150077A1 · Danielson et al. · 2018 [cited by applicant]
US 20180172450A1 · Lalonde et al. · 2018 [cited by applicant]
US 20180173242A1 · Lalonde · 2018 [cited by examiner]
US 20180189683A1 · Newman · 2018 [cited by applicant]
US 20180222050A1 · Vu et al. · 2018 [cited by applicant]
US 20180222051A1 · Vu et al. · 2018 [cited by applicant]
US 20180229368A1 · Leitner et al. · 2018 [cited by applicant]
US 20180281786A1 · Oyaizu et al. · 2018 [cited by applicant]
US 20180339456A1 · Czinger et al. · 2018 [cited by applicant]
US 20180349702A1 · Gildert et al. · 2018 [cited by applicant]
US 20190015981A1 · Yabushita et al. · 2019 [cited by applicant]
US 20190039242A1 · Fujii et al. · 2019 [cited by applicant]
US 20190087976A1 · Sugahara et al. · 2019 [cited by applicant]
US 20190101930A1 · Yadmellat · 2019 [cited by applicant]
US 20190105779A1 · Einav · 2019 [cited by applicant]
US 20190143518A1 · Maeda · 2019 [cited by applicant]
US 20190163191A1 · Sorin et al. · 2019 [cited by applicant]
US 20190164430A1 · Nix · 2019 [cited by applicant]
US 20190196480A1 · Taylor · 2019 [cited by examiner]
US 20190216555A1 · Dimaio et al. · 2019 [cited by applicant]
US 20190232496A1 · Graichen et al. · 2019 [cited by applicant]
US 20190234751A1 · Takhirov · 2019 [cited by applicant]
US 20190240835A1 · Sorin et al. · 2019 [cited by applicant]
US 20190262993A1 · Cole et al. · 2019 [cited by applicant]
US 20190291277A1 · Oleynik · 2019 [cited by applicant]
US 20190293443A1 · Kelly et al. · 2019 [cited by applicant]
US 20190391597A1 · Dupuis · 2019 [cited by applicant]
US 20200030971A1 · Oleynik · 2020 [cited by applicant]
US 20200069134A1 · Ebrahimi Afrouzi · 2020 [cited by examiner]
US 20200078097A1 · Gregerson et al. · 2020 [cited by applicant]
US 20200097014A1 · Wang · 2020 [cited by applicant]
US 20200215686A1 · Vijayanarasimhan et al. · 2020 [cited by applicant]
US 20200331146A1 · Vu et al. · 2020 [cited by applicant]
US 20200331155A1 · Vu et al. · 2020 [cited by applicant]
US 20200338730A1 · Yamauchi et al. · 2020 [cited by applicant]
US 20200338733A1 · Dupuis · 2020 [cited by examiner]
US 20200353917A1 · Leitermann et al. · 2020 [cited by applicant]
US 20200368910A1 · Chu · 2020 [cited by examiner]
US 20210009351A1 · Beinhofer et al. · 2021 [cited by applicant]
US 20210178591A1 · Floyd-jones et al. · 2021 [cited by applicant]
US 20220305648A1 · Oleynik · 2022 [cited by applicant]
US 20220339875A1 · Czinger et al. · 2022 [cited by applicant]
US 20230031545A1 · Oleynik · 2023 [cited by applicant]
US 20230063205A1 · Nerkar · 2023 [cited by applicant]
US 20230363833A1 · Gregerson et al. · 2023 [cited by applicant]
CA 3071332A1 · 2019 [cited by applicant]
CN 101837591A · 2010 [cited by applicant]
CN 102814813A · 2012 [cited by applicant]
CN 103722565A · 2014 [cited by applicant]
CN 104407616A · 2015 [cited by applicant]
CN 104858876A · 2015 [cited by applicant]
CN 102186638B · 2016 [cited by applicant]
CN 106660208A · 2017 [cited by applicant]
CN 107073710A · 2017 [cited by applicant]
CN 107206592A · 2017 [cited by applicant]
CN 107486858A · 2017 [cited by applicant]
CN 108297059A · 2018 [cited by applicant]
CN 108453702A · 2018 [cited by applicant]
CN 108789416A · 2018 [cited by applicant]
CN 108858183A · 2018 [cited by applicant]
CN 108942920A · 2018 [cited by applicant]
CN 109521763A · 2019 [cited by applicant]
CN 109782763B · 2021 [cited by applicant]
CN 114073585A · 2022 [cited by applicant]
EP 1241628A2 · 2002 [cited by applicant]
EP 1901150A1 · 2008 [cited by applicant]
EP 2306153A2 · 2011 [cited by applicant]
EP 3250347A1 · 2017 [cited by applicant]
EP 3725472A1 · 2020 [cited by applicant]
JP 07100755 · 1995 [cited by applicant]
JP 1997212229 · 1997 [cited by applicant]
JP 1148177 · 1999 [cited by applicant]
JP 11296229A · 1999 [cited by applicant]
JP 2001166806A · 2001 [cited by applicant]
JP 2002073130A · 2002 [cited by applicant]
JP 2003127077A · 2003 [cited by applicant]
JP 2005022062A · 2005 [cited by applicant]
JP 2005032196A · 2005 [cited by applicant]
JP 2006224740A · 2006 [cited by applicant]
JP 2007257274A · 2007 [cited by applicant]
JP 2007531110A · 2007 [cited by applicant]
JP 2008065755A · 2008 [cited by applicant]
JP 2008134165A · 2008 [cited by applicant]
JP 2010061293A · 2010 [cited by applicant]
JP 2010210592A · 2010 [cited by applicant]
JP 2011075382A · 2011 [cited by applicant]
JP 2011249711A · 2011 [cited by applicant]
JP 2012056023A · 2012 [cited by applicant]
JP 2012190405A · 2012 [cited by applicant]
JP 2012243029A · 2012 [cited by applicant]
JP 2013193194A · 2013 [cited by applicant]
JP 2014184498A · 2014 [cited by applicant]
JP 2015044274A · 2015 [cited by applicant]
JP 2015517142A · 2015 [cited by applicant]
JP 2015208811A · 2015 [cited by applicant]
JP 2016099257A · 2016 [cited by applicant]
JP 2016190315A · 2016 [cited by applicant]
JP 2016209969A · 2016 [cited by applicant]
JP 2017131973A · 2017 [cited by applicant]
JP 2017136677A · 2017 [cited by applicant]
JP 2017148908A · 2017 [cited by applicant]
JP 2018505788A · 2018 [cited by applicant]
JP 2018130793A · 2018 [cited by applicant]
JP 2018134703A · 2018 [cited by applicant]
JP 2018144158A · 2018 [cited by applicant]
JP 2018144166A · 2018 [cited by applicant]
JP 2019136848A · 2019 [cited by applicant]
JP 2019188530A · 2019 [cited by applicant]
JP 2020049623A · 2020 [cited by applicant]
JP 2020082332A · 2020 [cited by applicant]
JP 2020110885A · 2020 [cited by applicant]
KR 19980024584A · 1998 [cited by applicant]
KR 20110026776A · 2011 [cited by applicant]
KR 20130112507A · 2013 [cited by applicant]
KR 20150126482A · 2015 [cited by applicant]
KR 20170018564A · 2017 [cited by applicant]
KR 20170050166A · 2017 [cited by applicant]
KR 20180125646A · 2018 [cited by applicant]
TW 201318793A · 2013 [cited by applicant]
TW 615691B · 2018 [cited by applicant]
TW 653130B · 2019 [cited by applicant]
WO 9924914A1 · 1999 [cited by applicant]
WO 2011096327A1 · 2011 [cited by applicant]
WO 2015113203A1 · 2015 [cited by applicant]
WO 2016122840A1 · 2016 [cited by applicant]
WO 2017168187A1 · 2017 [cited by applicant]
WO 2017214581A1 · 2017 [cited by applicant]
WO 2018043525A1 · 2018 [cited by applicant]
WO 2019183141A1 · 2019 [cited by applicant]
WO 2020040979A1 · 2020 [cited by applicant]
WO 2020117958A1 · 2020 [cited by applicant]
Non-Final Office Action Issued in U.S. Appl. No. 16/268,290, Mailed Date: Jun. 17, 2021, 35 pages. [cited by applicant]
Communication Pursuant to Article 94(3) EPC, issued in European Application No. 18209405.2, Mailed Date: Nov. 23, 2020, 4 pages. [cited by applicant]
European Search Report dated Nov. 17, 2020 for EP Application No. 16743821.7, 4 pages. [cited by applicant]
Non-Final Office Action Issued in U.S. Appl. No. 16/308,693, Mailed Date: Dec. 11, 2020, 17 pages. [cited by applicant]
Final Office Action mailed Aug. 2, 2021 for U.S. Appl. No. 16/240,086 in 66 pages. [cited by applicant]
Notice of Allowance mailed Sep. 23, 2021, for Ritchey, “Motion Planning for Autonomous Vehicles and Reconfigurable Motion Planning Processors,” U.S. Appl. No. 16/615,493, 11 pages. [cited by applicant]
Notice of Allowance mailed Sep. 24, 2021, for Ritchey, “Motion Planning of a Robot Storing a Discretized Environment on One or More Processors and Improved Operation of Same,” U.S. Appl. No. 16/268,290, 8 pages. [cited by applicant]
Non-Final Office Action Issued in U.S. Appl. No. 16/268,290, Mailed Date: Jan. 27, 2021, 54 pages. [cited by applicant]
Communication Pursuant to Article 94(3) EPC, issued in European Application No. 17811131.6, Mailed Date: Jun. 16, 2020, 5 pages. [cited by applicant]
Extended European Search Report dated Apr. 10, 2018 for EP Application No. 16743821.7, in 9 pages. [cited by applicant]
Extended European Search Report issued in European Application No. 17811131.6, Mailed Date: Apr. 24, 2019, 16 pages. [cited by applicant]
Extended European Search Report issued in European Application No. 18209405.2, Mailed Date: Aug. 2, 2019, 9 pages. [cited by applicant]
First Office Action issued in Chinese No. 201680006941.3 with English translation, mailed Sep. 29, 2019, 16 pages. [cited by applicant]
First Office Action issued in Japanese Patent Application No. 2017-557268, Mailed Date: Aug. 7, 2018, 15 pages. [cited by applicant]
International Search Report and Written Opinion dated Jul. 29, 2020, in PCT/US2020/028343, 11 pages. [cited by applicant]
International Search Report and Written Opinion for PCT/US2019/016700 mailed May 20, 2019, 14 pages. [cited by applicant]
International Search Report and Written Opinion for PCT/US2019/023031 dated Aug. 14, 2019 in 19 pages. [cited by applicant]
International Search Report and Written Opinion for PCT/US2019/064511, mailed Mar. 27, 2020, 10 pages. [cited by applicant]
International Search Report and Written Opinion issued in PCT Application No. PCT/2020/034551, Mailed Aug. 31, 2020, 18 pages. [cited by applicant]
International Search Report and Written Opinion issued in PCT Application No. PCT/US2016/012204; Mailed Date: Mar. 21, 2016, 10 pages. [cited by applicant]
International Search Report and Written Opinion issued in PCT Application No. PCT/US2017/036880; Mailed Date: Oct. 10, 2017, 15 pages. [cited by applicant]
International Search Report and Written Opinion issued in PCT Application No. PCT/US2019/045270; Mailed Date: Nov. 25, 2019, 11 pages. [cited by applicant]
International Search Report and Written Opinion issued in PCT/US2019/012209, Mail Date: Apr. 25, 2019, 24 pages. [cited by applicant]
International Search Report and Written Opinion, mailed Jun. 23, 2020 for PCT/US2020/039193, 9 pages. [cited by applicant]
Non-Final Office Action Issued in U.S. Appl. No. 16/308,693, mailed Jun. 1, 2020, 16 pages. [cited by applicant]
Non-Final Office Action Issued in U.S. Appl. No. 15/546,441, Mailed Sep. 17, 2019, 58 Pages. [cited by applicant]
Office Action Issued in Japanese Application No. 2018-564836, mailed Dec. 3, 2019, 3 Pages. [cited by applicant]
Office Action Issued in Japanese Application No. 2018-564836, mailed May 19, 2020, 3 Pages. [cited by applicant]
pr.pdf (Or | Definition of Or by Merriam-Webster, Sep. 9, 2019, https://www.merriam-webster.com/dictionary/or, pp. 1-12; Year: 2019. [cited by applicant]
Second Office Action issued in Japanese Patent Application No. 2017-557268, Mailed Date: Feb. 26, 2019, 5 pages. [cited by applicant]
Atay, Nuzhet , et al., “A Motion Planning Processor on Reconfigurable Hardware”, All Computer Science and Engineering Research, Computer Science and Engineering; Report No. WUCSE-2005-46; Sep. 23, 2005. [cited by applicant]
Hauck, Scott , et al., “Configuration Compression for the Xilinx XC6200 FPGA”, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 18, No. 8; Aug. 1999. [cited by applicant]
Johnson, David E., et al., “Bound Coherence for Minimum Distance Computations”, Proceedings of the 1999 IEEE International Conference on Robotics and Automation, May 1999. [cited by applicant]
Kavraki, L.E. , et al., “Probabilistic Roadmaps for Path Planning in High-Dimensional Configuration Spaces”, IEEE Transactions on Robotics and Automation, IEEE Inc.; vol. 12, No. 4, pp. 566-580; Aug. 1, 1996. [cited by applicant]
Murray, Sean , et al., “Robot Motion Planning on a Chip”, Robotics: Science and Systems 2016; Jun. 22, 2016; 9 pages. [cited by applicant]
Murray, Sean , et al., “The microarchitecture of a real-time robot motion planning accelerator”, 2016 49th Annual IEEE/ACM International Symposium on Microarchitecture (Micro), IEEE, Oct. 15, 2016, 12 pages. [cited by applicant]
Rodriguez, Carlos , et al., “Planning manipulation movements of a dual-arm system considering obstacle removing”, Robotics and Autonomous Systems, Elsevier Science Publishers, vol. 62, No. 12, pp. 1816-1826; Aug. 1, 201… [cited by applicant]
Stilman, Mike , et al., “Manipulation Planning Among Movable Obstacles”, Proceedings of the IEEE Int. Conf. on Robotics and Automation, Apr. 2007. [cited by applicant]
Siciliano et al. “Robotics. Modelling, Planning and Control”, Chapter 12: Motion Planning, pp. 523-559, 2009. [cited by applicant]
Chen, Chao , Motion Planning for Nonholonomic Vehicles with Space Exploration Guided Heuristic Search, 2016, IEEE.com, Whole Document, 140 pages. [cited by applicant]
Pan, Jia , et al., Efficient Configuration Space Construction and Optimization for Motion Planning, 2015, Research Robotics, Whole Document, 12 pages. [cited by applicant]
European Search Report issued in European Application No. 19771537.8, Mailed Date: Mar. 29, 2021, 8 pages. [cited by applicant]
Final Office Action Issued in U.S. Appl. No. 16/268,290, Mailed Date: Apr. 21, 2021, 58 pages. [cited by applicant]
Murray, Sean , et al., “Robot Motion Planning on a Chip”, Robotics: Science and Systems, Jan. 1, 2016, 9 pages. [cited by applicant]
Rodriguez, Carlos , et al., “Planning manipulation movements of a dual-arm system considering obstacle removing”, Robotics and Autonomous Systems 62 (2014), Elsevier, Journal homepage: www.elsevier.com/locate/robot, pp.… [cited by applicant]
European Search Report dated Jul. 23, 2021, for European Application No. 19851097.6, 15 pages. [cited by applicant]
Taiwanese First Office Action—Application No. 106119452 dated Jun. 18, 2021, 25 pages. [cited by applicant]
Corrales, J.A. , et al., Safe Human-robot interaction based on dynamic sphere-swept line bounding volumes, Robotic and Computer-Integrated Manufacturing 27 (2011) 177-185, 9 page. [cited by applicant]
Pobil, Angel P, et al., “A New Representation for Collision Avoidance and Detection”, Proceedings of the 1992 IEEE, XP000300485, pp. 246-251. [cited by applicant]
Sato, Yuichi , et al., “Efficient Collision Detection using Fast Distance-Calculation Algorithms for Convex and Non-Convex Objects”, Proceeding of the 1996 IEEE, XP-000750294, 8 pages. [cited by applicant]
Turrillas, Alexander Martin, “Improvement of a Multi-Body Collision Computation Framework and Its Application to Robot (Self-) Collision Avoidance”, German Aerospace Center (DLR). Master's Thesis, Jun. 1, 2015, 34 pages. [cited by applicant]
Non-Final Office Action Issued in U.S. Appl. No. 16/240,086, Mailed Date: Feb. 11, 2021, 79 pages. [cited by applicant]
Non-Final Office Action Issued in U.S. Appl. No. 16/308,693, Mailed May 14, 2021, 16 pages. [cited by applicant]
International Search Report and Written Opinion for PCT/US2021/061427, mailed Apr. 29, 2022, 14 pages. [cited by applicant]
Notice of Reasons for Rejection, issued in corresponding Japanese Application No. 2021-509212, dated Apr. 7, 2022, 6 pages (English Translation). [cited by applicant]
Kececi F et al:“Improving Visually Servoed Disassembly Operations by Automatic Camera Placement”, Proceedings of the 1998 IEEE International Conference on Robotics and Automation. ICRA '98. May 16-20, 1998; New York, NY… [cited by applicant]
Klampfl Erica et al: “Optimization of workcell layouts in a mixed-model assembly line environment” International Journal of Flexible Manufacturing Systems, Kluwer Academic Publishers, Boston, vol. 17, No. 4, 23 pages, O… [cited by applicant]
Li, et al., “A Novel Cost Function for Decision-Making Strategies in Automotive Collision Avoidance Systems”, 2018 IEEE, ICVES, 8 pages. [cited by applicant]
Lim, Zhen Yang et al., “Multi-objective hybrid algorithms for layout optimization in multi-robot cellular manufacturing systems”, Knowledge-Based Systems, vol. 120, pp. 87-98. [cited by applicant]
Lin Jianjie et al: “An Efficient and Time-Optimal Trajectory Generation Approach for Waypoints Under Kinematic Constraints and Error Bounds”, 2018 IEEE/RSJ International Conference on Intelligent Robots and Systems (IRO… [cited by applicant]
Long Tao et al: “Optimization on multi-robot workcell layout in vertical plane”, Information and Automation (ICIA), 2011 IEEE International Conference on, IEEE, Jun. 6, 2011, 6 pages. [cited by applicant]
Magrini Emanuele et al: “Human-robot coexistence and interaction in open industrial cells”, Robotics and Computer Integrated Manufacturing, Elsevier Science Publishers BV. Barking, GB, vol. 61, Aug. 5, 2019 (Aug. 5, 201… [cited by applicant]
Non Final Office Action for U.S. Appl. No. 16/883,376, mailed Sep. 27, 2022, 26 pages. [cited by applicant]
Non Final Office Action for U.S. Appl. No. 17/909,801, mailed Jul. 30, 2024, 18 pages. [cited by applicant]
Non-Final Office Action Issued in U.S. Appl. No. 17/270,597, mailed Aug. 18, 2023, 25 pages. [cited by applicant]
Non-Final Office Action Issued in U.S. Appl. No. 17/506,364, Mailed Apr. 28, 2023, 50 pages. [cited by applicant]
On-Final Office Action Issued in U.S. Appl. No. 17/604,285, mailed Nov. 21, 2023, 28 pages. [cited by applicant]
Non-Final Office Action Issued in U.S. Appl. No. 18/221,027, mailed Feb. 29, 2024, 13 pages. [cited by applicant]
Non-Final Office Action Issued in U.S. Appl. No. 18/222,801, mailed Feb. 15, 2024, 44 pages. [cited by applicant]
Non-Final Office Action Issued in U.S. Appl. No. 16/981,467, Mailed Mar. 16, 2023, 19 pages. [cited by applicant]
Non-Final Office Action mailed Sep. 14, 2022, for U.S. Appl. No. 16/999,339, 18 pages. [cited by applicant]
Notice of Allowance for U.S. Appl. No. 17/153,662, mailed Dec. 6, 2022, 15 pages. [cited by applicant]
Notice of Allowance for U.S. Appl. No. 18/221,027, mailed Jul. 1, 2024, 10 pages. [cited by applicant]
Notice of Allowance for U.S. Appl. No. 18/222,801, mailed Jul. 3, 2024, 9 pages. [cited by applicant]
Notice of Allowance, Japanese Application No. 2023-532462, dated Oct. 29, 2024, 3 pages. [cited by applicant]
Notice of Reasons for Refusal dated Nov. 27, 2023, for Japanese Application No. 2021-561986, 10 pages. [cited by applicant]
Notice of Reasons for Refusal for Japanese Patent Application No. 2021-571340, mailed Aug. 8, 2023, 8 pages. [cited by applicant]
Notice of Reasons for Refusal for Japanese Patent Application No. 2022-562247, mailed Sep. 25, 2023, 7 pages. [cited by applicant]
Notice of Reasons for Refusal. Japanese Application No. 2022-556467, dated Sep. 28, 2023, 10 pages. [cited by applicant]
Notice of Reasons for Refusal. Japanese Application No. 2023-524134, dated Mar. 12, 2024, 6 pages. [cited by applicant]
Notice of Reasons for Refusal. Japanese Application No. 2023-532462, dated Jun. 21, 2024, 25 pages. [cited by applicant]
Notice of Reasons for Rejection dated Feb. 16, 2023, for Japanese Application No. 2021-571340, 10 pages. [cited by applicant]
Notice of Reasons for Rejection dated Feb. 7, 2023, for Japanese Application No. 2022-054900, 7 pages. [cited by applicant]
Office Action issued in Taiwan Application No. 108104094, mailed Feb. 6, 2023, 24 pages. [cited by applicant]
Office Action issued in Taiwan Application No. 109113033, mailed Jan. 19, 2024, 10 pages. [cited by applicant]
Office Action issued in Taiwan Application No. 109118558, mailed Jan. 4, 2024, 8 pages. [cited by applicant]
Office Action, ROC (Taiwan) Pat. Appln. No. 108130161 and Search Report—APP.108130161—mailed Sep. 19, 2023. [cited by applicant]
Oleynikova, et al., “Singed Distance Fields: A Natural Representation for Both Mapping and Planning”, 2016, 7 pages. [cited by applicant]
Cited By (2)
US 12,545,518 US 12,679,342