IP Library › Granted Patent US 12,330,310
Granted Patent B2
US 12,330,310 · App. 17/270,597 · Granted Jun 17, 2025

Collision detection useful in motion planning for robotics

Inventors: William Thomas Floyd-Jones (Boston, MA); Sean Michael Murray (Cambridge, MA); George Dimitri Konidaris (Boston, MA); Daniel Jeremy Sorin (Boston, MA)
Assignee: REALTIME ROBOTICS, INC.
B25J9/1666B25J9/1671G05B2219/40438G05B2219/40475
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,330,310
App. No.
17/270,597
Filed
Feb 23, 2021
Granted
Jun 17, 2025
Kind
B2
Art Unit
3657
USPC
700/255
Abstract

Collision detection useful in motion planning for robotics advantageously employs data structure representations of robots, persistent obstacles and transient obstacles in an environment in which a robot will operate. Data structures may take the form of hierarchical data structures ((e.g., octrees, sets of volumes or boxes (e.g., a tree of axis-aligned bounding boxes (AABBs), a tree of oriented (not axis-aligned) bounding boxes, or a tree of spheres)) or non-hierarchical data structures (e.g., Euclidean Distance Fields) Such can result in computational efficiency, reduce memory requirements, and lower power consumption. The collision detection can take the form as a standalone function, providing a Boolean result that can be employed in executing any of a variety of different motion planning algorithms.

Claims (62)

1. A method of operation of at least one component of a processor-based system useful in motion planning for robotics, the method comprising:

during a configuration time,

for a robot represented by a kinematic model, generating a data structure representation of the robot, the data structure representation of the robot in a form of a hierarchical tree structure; and

for an environment, generating a data structure representation of a set of persistent obstacles in the environment, the data structure representation of the set of persistent obstacles in the environment including the representation of a first number of obstacles for which a respective volume in the environment occupied by each of the obstacles of the first number of obstacles is known at the configuration time; and

during a run time,

for each of at least a first number of poses of the robot, determining, by at least one set of circuitry, whether any portion of the robot will collide with another portion of the robot based at least in part on the data structure representation of the robot;

for each of at least a second number of poses of the robot, determining, by at least one set of circuitry, whether any portion of the robot will collide with any persistent obstacles in an environment in which the robot operates based at least in part on the data structure representation of the set of persistent obstacles in the environment;

for each of at least a third number of poses of the robot, determining, by at least one set of circuitry, whether any portion of the robot will collide with any transient obstacles in the environment based at least in part on a data structure representation of a set of transient obstacles in the environment, the data structure representation including a representation of a second number of obstacles in the environment, for which, a respective volume in the environment occupied by each of the obstacles of the second number of obstacles is known during at least some portion of the run time and for which the respective volume in the environment occupied by each of the obstacles is not known at the configuration time; and

providing a signal that represents whether or not a collision has been detected for at least one of the poses.

2. The method of claim 1 wherein generating the data structure representation of the set of persistent obstacles in the environment comprises generating a hierarchy of bounding volumes.

3. The method of claim 2 wherein generating a hierarchy of bounding volumes comprises generating a hierarchy of bounding boxes with triangle meshes as leaf nodes.

4. The method of claim 2 wherein generating a hierarchy of bounding volumes comprises generating a hierarchy of spheres.

5. The method of claim 2 wherein generating a hierarchy of bounding volumes comprises generating a k-ary sphere tree.

6. The method of claim 2 wherein generating a hierarchy of bounding volumes comprises generating a hierarchy of axis-aligned bounding boxes, or a hierarchy of oriented bounding boxes.

7. The method of claim 1 wherein generating the data structure representation of the set of persistent obstacles in the environment comprises generating an octree that stores voxel occupancy information that represents the set of persistent obstacles in the environment.

8. The method of claim 1 wherein generating the data structure representation of the robot comprises generating a k-ary tree.

9. The method of claim 1 wherein generating the data structure representation of the robot comprises for each of a number of links of the robot, generating a respective k-ary tree.

10. The method of claim 1 wherein generating the data structure representation of the robot comprises for each of a number of links of the robot, generating a respective 8-ary tree with a tree depth equal to or greater than four.

11. The method of claim 1 wherein generating the data structure representation of the robot comprises for each of a number of links of the robot, generating a respective k-ary tree, where each node of the k-ary tree is a sphere that is identified as occupied if any portion of the respective sphere is occupied.

12. The method of claim 1 wherein the robot comprises a robotic appendage, and further comprising:

for a motion of the robot appendage between a first pose of the robot appendage and a second pose of the robot appendage, computing a plurality of intermediate poses of the robot appendage, the plurality of intermediate poses between the first and the second poses of the robot appendage in a C-space of the robotic appendage, until a dimension between a number of pairs of successively adjacent poses in the C-space satisfies a received value for a motion subdivision granularity, the motion subdivision granularity being a maximum spacing that is acceptable for a particular problem.

13. The method of claim 12 wherein computing a plurality of intermediate poses of the robot appendage includes:

for each of a number of joints of the robotic appendage, interpolating between a respective position and orientation for the joint in the first and the second poses to obtain an n th intermediate pose; and

for each of the joints of the robotic appendage iteratively interpolating between a respective position and orientation for the joint in a respective pair of nearest neighbor poses for a respective i th iteration until an end condition is reached.

14. The method of claim 13 wherein the end condition is a distance between successively adjacent poses that satisfies motion subdivision granularity to obtain an nth intermediate pose, and further comprising:

for a number of the iterations, determining whether the end condition has been reached.

15. The method of claim 12 , further comprising:

for each of a number of the poses, performing forward kinematics on the kinematic robot model to compute a number of transforms of each link of the robotic appendage.

16. The method of claim 1 wherein at least one of: determining whether any portion of the robot will collide with another portion of the robot, determining whether any portion of the robot will collide with any persistent obstacles, or determining whether any portion of the robot will collide with any transient obstacles comprises determining based on the hierarchical representation of the robot and based on a Euclidean Distance Field representation of the environment, collision detection starting at a root of the tree hierarchical representation and working towards leaf nodes, where if there are intersections at a non-leaf node level, the collision detection proceeds down to a next level of the hierarchical tree representation.

17. A system to generate collision assessments useful in motion planning for robotics, the system comprising:

at least one processor;

at least one non-transitory processor-readable medium that stores at least one of processor-executable instructions or data which, when executed by the at least one processor, causes the at least one processor to:

during a configuration time,

for a robot represented by a kinematic model, generate the data structure representation of the robot, the data structure representation of the robot in a form of a hierarchical tree structure; and

for an environment, generate a data structure representation of a set of persistent obstacles in the environment, the data structure representation of the set of persistent obstacles in the environment including the representation of a first number of obstacles for which a respective volume in the environment occupied by each of the obstacles of the first number of obstacles is known at the configuration time; and

during a run time,

for each of at least a first number of poses of the robot, determine whether any portion of the robot will collide with another portion of the robot based at least in part on the data structure representation of the robot;

for each of at least a second number of poses of the robot, determine whether any portion of the robot will collide with any persistent obstacles in an environment in which the robot operates based at least in part on the data structure representation of the set of persistent obstacles in the environment;

for each of at least a third number of poses of the robot, determine whether any portion of the robot will collide with any transient obstacles in the environment based at least in part on a data structure representation of a set of transient obstacles in the environment, the data structure representation including a representation of a second number of obstacles in the environment, for which, a respective volume in the environment occupied by each of the obstacles of the second number of obstacles is known during at least some portion of the run time and for which the respective volume in the environment occupied by each of the obstacles is not known at the configuration time; and

provide a signal that represents whether or not a collision has been detected for at least one of the poses.

18. The system of claim 17 wherein to generate the data structure representation of the set of persistent obstacles in the environment the at least one processor generates a hierarchy of bounding volumes.

19. The system of claim 18 wherein to generate a hierarchy of bounding volumes the at least one processor generates a hierarchy of bounding boxes with triangle meshes as leaf nodes.

20. The system of claim 18 wherein to generate a hierarchy of bounding volumes the at least one processor generates a hierarchy of spheres.

21. The system of claim 18 wherein to generate a hierarchy of bounding volumes the at least one processor generates a k-ary sphere tree.

22. The system of claim 18 wherein to generate a hierarchy of bounding volumes the at least one processor generates a hierarchy of axis-aligned bounding boxes.

23. The system of claim 18 wherein to generate a hierarchy of bounding volumes the at least one processor generates a hierarchy of oriented bounding boxes.

24. The system of claim 17 wherein to generate the data structure representation of the set of persistent obstacles in the environment the at least one processor generates an octree that stores voxel occupancy information that represents the set of persistent obstacles in the environment.

25. The system of claim 17 wherein to generate the data structure representation of the robot the at least one processor generates a k-ary tree.

26. The system of claim 17 wherein to generate the data structure representation of the robot the at least one processor generates a respective k-ary tree for each of a number of links of the robot.

27. The system of claim 17 wherein to generate the data structure representation of the robot the at least one processor generates a respective 8-ary tree for each of a number of links of the robot.

28. The system of claim 17 wherein to generate the data structure representation of the robot the at least one processor generates a respective 8-ary tree with a tree depth equal to or greater than four for each of a number of links of the robot.

29. The system of claim 17 wherein to generate the data structure representation of the robot the at least one processor generates a respective k-ary tree for each of a number of links of the robot, where each node of the k-ary tree is a sphere that is identified as occupied if any portion of the respective sphere is occupied.

30. The system of claim 17 wherein the robot comprises a robotic appendage, and wherein execution of the at least one of processor-executable instructions or data further cause the at least processor to:

for a motion of the robot appendage between a first pose of the robot appendage and a second pose of the robot appendage, compute a plurality of intermediate poses of the robot appendage, the plurality of intermediate poses between the first and the second poses of the robot appendage in a C-space of the robotic appendage, until a dimension between a number of pairs of successively adjacent poses in the C-space satisfies a received value for a motion subdivision granularity, the motion subdivision granularity being a maximum spacing that is acceptable for a particular problem.

31. The system of claim 30 wherein to compute a plurality of intermediate poses of the robot appendage the at least one processor:

for each of a number of joints of the robotic appendage, interpolate between a respective position and orientation for the joint in the first and the second poses to obtain an n th intermediate pose; and

for each of the joints of the robotic appendage iteratively interpolates between a respective position and orientation for the joint in a respective pair of nearest neighbor poses for a respective i th iteration until an end condition is reached.

32. The system of claim 31 wherein the end condition is a distance between successively adjacent poses that satisfies motion subdivision granularity to obtain an nth intermediate pose, and wherein execution of the at least one of processor-executable instructions or data further cause the at least processor to:

for a number of the iterations, determine whether the end condition has been reached.

33. The system of claim 30 wherein execution of the at least one of processor-executable instructions or data further cause the at least processor to:

for each of a number of the poses, perform forward kinematics on the kinematic robot model to compute a number of transforms of each link of the robotic appendage.

34. The system of claim 17 wherein at least one of: the determination of whether any portion of the robot will collide with another portion of the robot, the determination of whether any portion of the robot will collide with any persistent obstacles, or the determination of whether any portion of the robot will collide with any transient obstacles comprises a determination based on the hierarchical representation of the robot and based on a Euclidean Distance Field representation of the environment, collision detection which starts at a root of the tree hierarchical representation and works towards a number of leaf nodes, where if there are intersections at a non-leaf node level, the collision detection proceeds down to a next level of the hierarchical tree representation.

Assignments (1)
SECURITY INTEREST Recorded Oct 22, 2025
From: REALTIME ROBOTICS, INC.
To: FIRST-CITIZENS BANK & TRUST COMPANY
Reel/Frame 074155/0025 →
Continuity (2)
Provisional Application 62722067 · Aug 23, 2018
Related Publication 20210178591A1 · Jun 17, 2021
References Cited (317)
US 4163183A · Dunne et al. · 1979 [cited by applicant]
US 4300198A · Davini · 1981 [cited by applicant]
US 4862373A · Meng · 1989 [cited by applicant]
US 4949277A · Trovato et al. · 1990 [cited by applicant]
US 5347459A · Greenspan et al. · 1994 [cited by applicant]
US 5544282A · Chen et al. · 1996 [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 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 6671582B1 · Hanley · 2003 [cited by applicant]
US 7577498B2 · Jennings et al. · 2009 [cited by applicant]
US 7609020B2 · Kniss et al. · 2009 [cited by applicant]
US 7865277B1 · Larson et al. · 2011 [cited by applicant]
US 7940023B2 · Kniss et al. · 2011 [cited by applicant]
US 8082064B2 · Kay · 2011 [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 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 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 examiner]
US 10430641B2 · Gao · 2019 [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 11358337B2 · Czinger et al. · 2022 [cited by applicant]
US 11623494B1 · Arnicar 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 20030155881A1 · Hamann et al. · 2003 [cited by applicant]
US 20040249509A1 · Rogers et al. · 2004 [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 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 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 · 2008 [cited by examiner]
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 20090295323A1 · Papiernik 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 20110066282A1 · Bosscher et al. · 2011 [cited by applicant]
US 20110153080A1 · Shapiro et al. · 2011 [cited by applicant]
US 20120010772A1 · Pack 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 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 20140309916A1 · Bushnell · 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 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 20160107313A1 · Hoffmann · 2016 [cited by examiner]
US 20160112694A1 · Nishi et al. · 2016 [cited by applicant]
US 20160121486A1 · Lipinski et al. · 2016 [cited by applicant]
US 20160121487A1 · Mohan et al. · 2016 [cited by applicant]
US 20160154408A1 · Eade 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 20170004406A1 · Aghamohammadi · 2017 [cited by applicant]
US 20170028559A1 · Davidi et al. · 2017 [cited by applicant]
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 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 et al. · 2018 [cited by applicant]
US 20180029233A1 · Lager · 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 et al. · 2018 [cited by applicant]
US 20180189683A1 · Newman · 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 20190015981A1 · Yabushita · 2019 [cited by examiner]
US 20190039242A1 · Fujii · 2019 [cited by examiner]
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 applicant]
US 20190232496A1 · Graichen et al. · 2019 [cited by applicant]
US 20190262993A1 · Cole et al. · 2019 [cited by applicant]
US 20190293443A1 · Kelly et al. · 2019 [cited by applicant]
US 20190391597A1 · Dupuis · 2019 [cited by applicant]
US 20200069134A1 · Ebrahimi Afrouzi et al. · 2020 [cited by applicant]
US 20200097014A1 · Wang · 2020 [cited by applicant]
US 20200331146A1 · Vu et al. · 2020 [cited by applicant]
US 20200338730A1 · Yamauchi et al. · 2020 [cited by applicant]
US 20200338733A1 · Dupuis et al. · 2020 [cited by applicant]
US 20200353917A1 · Leitermann et al. · 2020 [cited by applicant]
US 20200368910A1 · Chu et al. · 2020 [cited by applicant]
US 20210009351A1 · Beinhofer et al. · 2021 [cited by applicant]
US 20220339875A1 · Czinger et al. · 2022 [cited by applicant]
US 20230063205A1 · Nerkar · 2023 [cited by applicant]
CN 101837591A · 2010 [cited by applicant]
CN 102814813A · 2012 [cited by applicant]
CN 104858876A · 2015 [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 108789416A · 2018 [cited by applicant]
CN 108858183A · 2018 [cited by applicant]
CN 108942920A · 2018 [cited by applicant]
EP 1901150A1 · 2008 [cited by applicant]
EP 2306153A2 · 2011 [cited by applicant]
EP 3250347A1 · 2017 [cited by applicant]
EP 3486612A1 · 2019 [cited by applicant]
EP 3725472A1 · 2020 [cited by applicant]
JP 11296229A · 1999 [cited by applicant]
JP 2002073130A · 2002 [cited by applicant]
JP 2003127077A · 2003 [cited by applicant]
JP 2005032196A · 2005 [cited by applicant]
JP 2006224740A · 2006 [cited by applicant]
JP 2007257274A · 2007 [cited by applicant]
JP 2008065755A · 2008 [cited by applicant]
JP 2010061293A · 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 2017131973A · 2017 [cited by applicant]
JP 2018505788A · 2018 [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 20170044987A · 2017 [cited by applicant]
KR 20170050166A · 2017 [cited by applicant]
KR 20180125646A · 2018 [cited by applicant]
TW 201318793A · 2013 [cited by applicant]
WO 9924914A1 · 1999 [cited by applicant]
WO 2015113203A1 · 2015 [cited by applicant]
WO WO2016122840A1 · 2016 [cited by examiner]
WO 2017168187A1 · 2017 [cited by applicant]
WO 2017214581A1 · 2017 [cited by applicant]
WO 2019183141A1 · 2019 [cited by applicant]
WO 2020040979A1 · 2020 [cited by applicant]
WO 2020117958A1 · 2020 [cited by applicant]
Oleynikova, Helen; Millane, Alexander; Taylor, Zachary; Galceran, Enric; Nieto, Juan; Siegwart, Roland “Signed Distance Fields: A Natural Representation for Both Mapping and Planning”, 2016 (Year: 2016). [cited by examiner]
Non-Final Office Action Issued in U.S. Appl. No. 16/268,290, Mailed Date: Jun. 17, 2021, 35 pages. [cited by applicant]
Barral D et al: “Simulated Annealing Combined With a Constructive Algorithm for Optimising Assembly Workcell Layout”, The International Journal of Advanced Manufacturing Technology, Springer, London, vol. 17, No. 8, Jan… [cited by applicant]
Extended EP Search Report mailed Nov. 7, 2022, EP App No. 21744840.6-1205, 14 pages. [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, … [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]
Pashkevich AP et al: “Multiobjective optimisation of robot location in a workcell using genetic algorithms”, Control '98. UKACC International Conference on (Conf. Publ. No. 455) Swansea, UK Sep. 1-4, 1998, London, UK, v… [cited by applicant]
Zhen Yang et al: “Multi-objective hybrid algorithms for layout optimization in multi-robot cellular manufacturing systems”, Knowledge-Based Systems, Elsevier, Amsterdam, NL, vol. 120, Jan. 3, 2017, 12 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]
International Search Report and Written Opinion for PCT/US2021/061427, mailed Apr. 29, 2022, 14 pages. [cited by applicant]
Non-Final Office Action Issued in U.S. Appl. No. 16/909,096 Mailed May 6, 2022, 49 pages. [cited by applicant]
Bharathi Akilan et al: “Feedrate optimization for smooth minimum-time trajectory generation with higher order constraints”, The International Journal of Advanced Manufacturing Technology,vol. 82, No. 5, Jun. 28, 2015 (J… [cited by applicant]
Dong et al: “Feed-rate optimization with jerk constraints for generating minimum-time trajectories”, International Journal of Machine Tool Design and Research, Pergamon Press, Oxford, GB, vol. 47, No. 12-13, Aug. 9, 200… [cited by applicant]
Extended EP Search Report mailed Jul. 18, 2022 EP App No. 20832308.9-1205, 10 pages. [cited by applicant]
Extended EP Search Report mailed Jul. 25, 2022 EP App No. 20857383.2-1205, 10 pages. [cited by applicant]
Sonja MacFarlane et al: “Jerk-Bounded Manipulator Trajectory Planning: Design for Real-Time Applications”, IEEE Transactions on Robotics and Automation, IEEE Inc, New York, US, vol. 19, No. 1, Feb. 1, 2003 (Feb. 1, 2003… [cited by applicant]
Final Office Action mailed Sep. 7, 2022, for U.S. Appl. No. 16/909,096, 54 pages. [cited by applicant]
Gasparetto A et al: “Experimental validation and comparative analysis of optimal time-jerk algorithms for trajectory planning”, Robotics and Computer Integrated Manufacturing, Elsevier Science Publishers BV. , Barking, … [cited by applicant]
Gasparetto et al: “A new method for smooth trajectory planning of robot manipulators”, Mechanism and Machine Theory, Pergamon, Amsterdam, NL, vol. 42, No. 4, Jan. 26, 2007. [cited by applicant]
Haschke R et al: “On-Line Planning of Time-Opti.mal, Jerk-Limited Trajectories”, Internet Citation, Jul. 1, 2008 (Jul. 1, 2008), pp. 1-6, XP00278977 6. [cited by applicant]
Jan Mattmuller et al: “Calculating a near time-optimal jerk-constrained trajectory along a specified smooth path”, The International Journal of Advanced Manufacturing Technology, Springer, Berlin, DE, vol. 45, No. 9-10,… [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]
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 malled Sep. 14, 2022, for U.S. Appl. No. 16/999,339, 18 pages. [cited by applicant]
Ratliff, et al., “CHOMP: Gradient Optimization Techniques for Efficient Motion Planning”, 2009 IEEE International Conferenced on Robotics and Automation, Kobe, Japan, May 12-17, 2009, 6 pages. [cited by applicant]
S. Saravana Perumaal et al: “Automated Trajectory Planner of Industrial Robot for Pick-and-Place Task”, International Journal of Advanced Robotic Systems, vol. 10, No. 2, Jan. 1, 2013. [cited by applicant]
Notice of Reasons for Rejection dated Feb. 16, 2023, for Japanese Application No. 2021-571340, 10 pages. [cited by applicant]
Office Action issued in Taiwan Application No. 108104094, mailed Feb. 6, 2023, 24 pages. [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]
Japanese Office Action, Japanese Application No. 2021-576425, Mar. 13, 2023, 14 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]
Communication Pursuant to Article 94(3) EPC, issued in European Application No. 17811131.6, Mailed Date: Jun. 16, 2020, 5 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, Mailed Date: Nov. 17, 2020 for EP Application No. 16743821.7, 4 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]
Extended European Search Report, Mailed Date: Apr. 10, 2018 for EP Application No. 16743821.7, in 9 pages. [cited by applicant]
First Office Action issued in Chinese No. 201680006941.3 with English translation, Mailed Date: 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 for PCT/US2019/016700, Mailed Date: May 20, 2019, 14 pages. [cited by applicant]
International Search Report and Written Opinion for PCT/US2019/023031, Mailed Date: Aug. 14, 2019 in 19 pages. [cited by applicant]
International Search Report and Written Opinion for PCT/US2019/064511, Mailed Date: Mar. 27, 2020, 10 pages. [cited by applicant]
International Search Report and Written Opinion issued in PCT Application No. PCT/2020/034551, Mailed Date: 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, Mailed Date: Apr. 25, 2019, 24 pages. [cited by applicant]
International Search Report and Written Opinion, Mailed Date: Jul. 29, 2020, in PCT/US2020/028343, 11 pages. [cited by applicant]
International Search Report and Written Opinion, Mailed Date: Nov. 23, 2020, for PCT/US2020/047429, 11 Pages. [cited by applicant]
International Search Report and Written Opinion, Mailed Date: Sep. 29, 2020 for PCT/US2020/039193, 9 pages. [cited by applicant]
Invitation to Pay Additional Fees and, Where Applicable, Protest Fee issued in PCT/US2017/036880, Mailed Date: Aug. 14, 2017, 2 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/268,290, Mailed Date: Jan. 27, 2021, 54 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]
Non-Final Office Action Issued in U.S. Appl. No. 16/308,693, Mailed Date: 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 Date: Dec. 3, 2019, 3 Pages. [cited by applicant]
Office Action Issued in Japanese Application No. 2018-564836, Mailed Date: May 19, 2020, 5 Pages. [cited by applicant]
or.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]
Hassan, “Modeling and Stochastic Optimization of Complete Coverage under Uncertainties in Multi-Robot Base Placements,” 2016, Intelligent Robots and Systems (IROS} (Year: 2016). [cited by applicant]
Hassan, et al., “An Approach to Base Placement for Effective Collaboration of Multiple Autonomous Industrial Robots,” 2015 IEEE International Conference on Robotics and Automation (ICRA}, pp. 3286-3291 (Year: 2015). [cited by applicant]
Hassan, et al., “Simultaneous area partitioning and allocation for complete coverage by multiple autonomous industrial robots,” 2017, Autonomous Robots 41, pp. 1609-1628 (Year: 2017). [cited by applicant]
Hassan, et al., “Task Oriented Area Partitioning and Allocation for Optimal Operation of Multiple Industrial Robots in Unstructured Environments,” 2014, 13th International Conference on Control, Automation, Robotics & V… [cited by applicant]
Kalawoun, “Motion planning of multi-robot system for airplane stripping,” 2019, Universite Clermont Auvergne (Year: 2019). [cited by applicant]
Kapanoglu, et al., “A pattern-based genetic algorithm for multi-robot coverage path planning minimizing completion time,” 2012, Journal of Intelligent Manufacturing 23, pp. 1035-1045 (Year: 2012). [cited by applicant]
Notice of Allowance for U.S. Appl. No. 17/153,662, mailed Dec. 6, 2022, 15 pages. [cited by applicant]
Pires, et al., “Robot Trajectory Planning Using Multi-objective Genetic Algorithm Optimization,” 2004, Genetic and Evolutionary Computation—GECCO 2004, pp. 615-626 (Year: 2004). [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]
Extended EP Search Report mailed May 10, 2023, EP App No. 20818760.9-1012, 9 pages. [cited by applicant]
First Office Action and Search Report issued in Chinese No. 202080040382.4 with English translation, Mailed Date: May 26, 2023, 15 pages. [cited by applicant]
First Office Action issued in Chinese No. 202080059714.3 with English translation, Mailed Date: May 24, 2023, 24 pages. [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]
Non-Final Office Action Issued in U.S. Appl. No. 17/506,364, Mailed Apr. 28, 2023, 50 pages. [cited by applicant]
Schwesinger, “Motion Planning n Dynamic Environments with Application to Self-Driving Vehicles”, Dr. Andreas Krause, Jan. 1, 2017, XP093029842. [cited by applicant]
First Office Action issued in Chinese No. 201980024188.4 with English translation, Mailed Date: Feb. 22, 2023, 28 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]
Notice of Reasons for Rejection dated Feb. 7, 2023, for Japanese Application No. 2022-054900, 7 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]