268:
260:
276:
238:
216:
791:. When proving this property mathematically, one has to make sure, that it happens in finite time and not just in the asymptotic limit. This is especially problematic, if there occur infinite sequences (that converge only in the limiting case) during a specific proving technique, since then, theoretically, the algorithm will never stop. Intuitive "tricks" (often based on induction) are typically mistakenly thought to converge, which they do only for the infinite limit. In other words, the solution exists, but the planner will never report it. This property therefore is related to
208:
803:, that will simply kill the process. The watchdog has to be independent of all processes (typically realized by low level interrupt routines). The asymptotic case described in the previous paragraph, however, will not be reached in this way. It will report the best one it has found so far (which is better than nothing) or none, but cannot correctly report that there is none. All realizations including a watchdog are always incomplete (except all cases can be evaluated in finite time).
1736:
2319:
710:, it has been proven that as the number of configurations N grows higher, the probability that the above algorithm finds a solution approaches 1 exponentially. Visibility is not explicitly dependent on the dimension of C; it is possible to have a high-dimensional space with "good" visibility or a low-dimensional space with "poor" visibility. The experimental success of sample-based methods suggests that most commonly seen spaces have good visibility.
570:
2331:
25:
588:
579:
461:. Potential-field algorithms are efficient, but fall prey to local minima (an exception is the harmonic potential fields). Sampling-based algorithms avoid the problem of local minima, and solve many problems quite quickly. They are unable to determine that no path exists, but they have a probability of failure that decreases to zero as more time is spent.
813:
is the property that the planner is guaranteed to find a path if the resolution of an underlying grid is fine enough. Most resolution complete planners are grid-based or interval-based. The computational complexity of resolution complete planners is dependent on the number of points in the underlying
657:
One approach is to treat the robot's configuration as a point in a potential field that combines attraction to the goal, and repulsion from obstacles. The resulting trajectory is output as the path. This approach has advantages in that the trajectory is produced with little computation. However, they
163:
inside a building to a distant waypoint. It should execute this task while avoiding walls and not falling down stairs. A motion planning algorithm would take a description of these tasks as input, and produce the speed and turning commands sent to the robot's wheels. Motion planning algorithms might
433:
Target space is a subspace of free space which denotes where we want the robot to move to. In global motion planning, target space is observable by the robot's sensors. However, in local motion planning, the robot cannot observe the target space in some states. To solve this problem, the robot goes
806:
Completeness can only be provided by a very rigorous mathematical correctness proof (often aided by tools and graph based methods) and should only be done by specialized experts if the application includes safety content. On the other hand, disproving completeness is easy, since one just needs to
820:
is the property that as more "work" is performed, the probability that the planner fails to find a path, if one exists, asymptotically approaches zero. Several sample-based methods are probabilistically complete. The performance of a probabilistically complete planner is measured by the rate of
662:
of the potential field and fail to find a path, or can find a non-optimal path. The artificial potential fields can be treated as continuum equations similar to electrostatic potential fields (treating the robot like a point charge), or motion through the field can be discretized using a set of
698:
These algorithms work well for high-dimensional configuration spaces, because unlike combinatorial algorithms, their running time is not (explicitly) exponentially dependent on the dimension of C. They are also (generally) substantially easier to implement. They are probabilistically complete,
746:
If only one or a few planning queries are needed, it is not always necessary to construct a roadmap of the entire space. Tree-growing variants are typically faster for this case (single-query planning). Roadmaps are still useful if many queries are to be made on the same space (multi-query
464:
Sampling-based algorithms are currently considered state-of-the-art for motion planning in high-dimensional spaces, and have been applied to problems which have dozens or even hundreds of dimensions (robotic manipulators, biological molecules, animated digital characters, and
164:
address robots with a larger number of joints (e.g., industrial manipulators), more complex tasks (e.g. manipulation of objects), different constraints (e.g., a car that can only drive forward), and uncertainty (e.g. imperfect models of the environment or robot).
477:
Grid-based approaches overlay a grid on configuration space and assume each configuration is identified with a grid point. At each grid point, the robot is allowed to move to adjacent grid points as long as the line between them is completely contained within
648:
Given a bundle of rays around the current position attributed with their length hitting a wall, the robot moves into the direction of the longest ray unless a door is identified. Such an algorithm was used for modeling emergency egress from buildings.
798:
In practice, the termination of the algorithm can always be guaranteed by using a counter, that allows only for a maximum number of iterations and then always stops with or without solution. For realtime systems, this is typically achieved by using a
283:
A basic motion planning problem is to compute a continuous path that connects a start configuration S and a goal configuration G, while avoiding collision with known obstacles. The robot and obstacle geometry is described in a 2D or 3D
573:
Motion from the initial configuration (blue) to the final configuration of the hook, avoiding the two obstacles (red segments). The left-bottom corner of the hook has to stay on the horizontal line, which makes the hook two degrees of
563:. As for the grid-based approach, the interval approach is inappropriate for high-dimensional problems, due to the fact that the number of boxes to be generated grows exponentially with respect to the dimension of configuration space.
827:
planners do not always produce a feasible path when one exists (see first paragraph). Sometimes incomplete planners do work well in practice, since they always stop after a guarantied time and allow other routines to take over.
691:. To find a path that connects S and G, they are added to the roadmap. If a path in the roadmap links S and G, the planner succeeds, and returns that path. If not, the reason is not definitive: either there is no path in C
743:
It is possible to substantially reduce the number of milestones needed to solve a given problem by allowing curved eye sights (for example by crawling on the obstacles that block the way between two milestones).
582:
Decomposition with boxes covering the configuration space: The subpaving X is the union all red boxes and the subpaving X is the union of red and green boxes. The path corresponds to the motion represented
507:
Grid-based approaches often need to search repeatedly, for example, when the knowledge of the robot about the configuration space changes or the configuration space itself changes during path following.
807:
find one infinite loop or one wrong result returned. Formal
Verification/Correctness of algorithms is a research field on its own. The correct setup of these test cases is a highly sophisticated task.
787:
if the planner in finite time either produces a solution or correctly reports that there is none. Most complete algorithms are geometry-based. The performance of a complete planner is assessed by its
591:
This figure corresponds to the same path as above but obtained with many fewer boxes. The algorithm avoids bisecting boxes in parts of the configuration space that do not influence the final result.
520:
These approaches are similar to grid-based search approaches except that they generate a paving covering entirely the configuration space instead of a grid. The paving is decomposed into two
450:
Low-dimensional problems can be solved with grid-based algorithms that overlay a grid on top of configuration space, or geometric algorithms that compute the shape and connectivity of C
795:
and serves in most cases as a theoretical underpinning/guidance. Planners based on a brute force approach are always complete, but are only realizable for finite and discrete setups.
566:
An illustration is provided by the three figures on the right where a hook with two degrees of freedom has to move from the left to the right, avoiding two horizontal small segments.
308:
If the robot is a single point (zero-sized) translating in a 2-dimensional plane (the workspace), C is a plane, and a configuration can be represented using two parameters (x, y).
1386:
Scordamaglia, V.; Nardi, V. A. (2021). "A set-based trajectory planning algorithm for a network controlled skid-steered tracked mobile robot subject to skid and slip phenomena".
675:
Sampling-based algorithms represent the configuration space with a roadmap of sampled configurations. A basic algorithm samples N configurations in C, and retains those in C
821:
convergence. For practical applications, one usually uses this property, since it allows setting up the time-out for the watchdog based on an average convergence time.
497:. Furthermore, the number of points on the grid grows exponentially in the configuration space dimension, which make them inappropriate for high-dimensional problems.
547:
The robot is thus allowed to move freely in X, and cannot go outside X. To both subpavings, a neighbor graph is built and paths can be found using algorithms such as
377:
336:
504:
approaches find shorter paths by propagating information along grid edges (to search fast) without constraining their paths to grid edges (to find short paths).
667:
or a probabilistic navigation function are sorts of artificial potential functions which have the quality of not having minimum points except the target point.
500:
Traditional grid-based approaches produce paths whose heading changes are constrained to multiples of a given base angle, often resulting in suboptimal paths.
493:
These approaches require setting a grid resolution. Search is faster with coarser grids, but the algorithm will fail to find paths through narrow portions of C
434:
through several virtual target spaces, each of which is located within the observable area (around the robot). A virtual target space is called a sub-goal.
1596:
1166:
Wolf, Joerg
Christian; Robinson, Paul; Davies, Mansel (2004). "Vector Field path planning and control of an autonomous robot in a dynamic environment".
1725:
595:
699:
meaning the probability that they will produce a solution approaches 1 as more time is spent. However, they cannot determine if no solution exists.
730:
ones, though some recent work argues that the effect of the source of randomness is minimal compared to the effect of the sampling distribution.
512:
algorithms replan fast by using experience with the previous similar path-planning problems to speed up their search for the current one.
311:
If the robot is a 2D shape that can translate and rotate, the workspace is still 2-dimensional. However, C is the special
Euclidean group
1098:
Delanoue, N.; Jaulin, L.; Cottenceau, B. (2006). "Counting the Number of
Connected Components of a Set and Its Application to Robotics".
2367:
814:
grid, which is O(1/h), where h is the resolution (the length of one side of a grid cell) and d is the configuration space dimension.
352:
If the robot is a solid 3D shape that can translate and rotate, the workspace is 3-dimensional, but C is the special
Euclidean group
598:
has shown that the decomposition with subpavings using interval analysis also makes it possible to characterize the topology of C
458:
1341:
Shvalb, N.; Ben Moshe, B.; Medina, O. (2013). "A real-time motion planning algorithm for a hyper-redundant set of mechanisms".
559:. When no path exists in X from one initial configuration to the goal, we have the guarantee that no feasible path exists in C
89:
2362:
2304:
2064:
1573:
1514:
1483:
1440:
1260:
1130:
61:
1985:
1421:
Kucner, Tomasz Piotr; Lilienthal, Achim J.; Magnusson, Martin; Palmieri, Luigi; Srinivas
Swaminathan, Chittaranjan (2020).
255:, where dark gray = the objects, light gray = configurations where the robot would touch an object or leave the workspace.
996:
918:
720:
Nonuniform sampling distributions attempt to place more milestones in areas that improve the connectivity of the roadmap.
1657:
68:
1184:
1533:
140:
to find a sequence of valid configurations that moves the object from the source to destination. The term is used in
108:
619:
42:
788:
75:
46:
683:. A roadmap is then constructed that connects two milestones P and Q if the line segment PQ is completely in C
1980:
1473:
767:
301:
289:
717:
It is typically much faster to only test segments between nearby pairs of milestones, rather than all pairs.
57:
2256:
509:
1011:- mathematical problem of finding the largest two-dimensional shape that can be maneuvered around a corner
389:
If the robot is a fixed-base manipulator with N revolute joints (and no closed-loops), C is N-dimensional.
267:
2130:
2074:
442:
Obstacle space is a space that the robot can not move to. Obstacle space is not opposite of free space.
259:
2294:
1690:
2357:
2282:
1025:
942:
1355:
1152:
1113:
275:
237:
215:
734:
346:
1931:
1926:
548:
501:
35:
457:
Exact motion planning for high-dimensional systems under complex constraints is computationally
2125:
1650:
1350:
1108:
1041:
141:
1201:
2236:
2090:
1700:
1047:
844:
772:
362:
321:
137:
82:
1551:
2186:
2110:
1875:
1835:
1685:
1422:
1099:
1020:
188:
8:
2335:
2277:
2140:
1840:
1680:
1240:
1073:
1008:
907:
792:
757:
664:
552:
537:
487:
422:
398:
The set of configurations that avoids collision with obstacles is called the free space C
196:
2246:
2221:
2211:
2176:
2120:
2100:
2047:
2020:
1958:
1870:
1804:
1705:
1454:
1403:
1368:
1323:
1297:
1266:
1221:
1140:
985:
418:
145:
1597:
Jean-Claude
Latombe talks about his work with robots and motion planning, 5 April 2000
349:
of 2D rotations), and a configuration can be represented using 3 parameters (x, y, θ).
2323:
2287:
2216:
2145:
2032:
1818:
1720:
1695:
1643:
1569:
1558:
1529:
1510:
1479:
1446:
1436:
1407:
1327:
1315:
1256:
1225:
1126:
1052:
483:
180:
1458:
1372:
1270:
544:
cannot be described by linear inequalities in order to have a guaranteed enclosure.
482:(this is tested with collision detection). This discretizes the set of actions, and
2272:
2150:
2135:
2010:
2002:
1921:
1880:
1865:
1813:
1715:
1428:
1395:
1360:
1307:
1248:
1213:
1118:
964:
898:
are those that mix discrete and continuous behavior. Examples of such systems are:
614:
168:
2181:
2166:
2069:
2051:
1916:
1789:
1767:
1757:
1565:
1540:
1504:
1188:
990:
980:
624:
192:
241:
Configuration space for a rectangular translating robot (pictured red). White =
2299:
2115:
2105:
2027:
1970:
1911:
1850:
1845:
1830:
1762:
1399:
1285:
975:
895:
800:
382:(3), and a configuration requires 6 parameters: (x, y, z) for translation, and
1432:
1364:
1252:
1217:
836:
Many algorithms have been developed to handle variants of this basic problem.
207:
2351:
2251:
2206:
1890:
1885:
1860:
1855:
1553:
1545:
1450:
1319:
1311:
634:
533:
288:, while the motion is represented as a path in (possibly higher-dimensional)
153:
2015:
1990:
1975:
1948:
1938:
1799:
1710:
1181:
912:
854:
727:
659:
466:
383:
176:
160:
2037:
1963:
1953:
1943:
1906:
1823:
1784:
1735:
1243:; Motwani, R. (1997). "Path planning in expansive configuration spaces".
1036:
1014:
737:
723:
409:
Often, it is prohibitively difficult to explicitly compute the shape of C
1122:
726:
samples typically produce a better covering of configuration space than
425:
tests if the robot's geometry collides with the environment's geometry.
969:
184:
172:
1630:
1107:. Lecture Notes in Computer Science. Vol. 3732. pp. 93–101.
2201:
2095:
1794:
1618:
569:
521:
1202:"Probability Navigation Function for Stochastic Static Environments"
1101:
Applied
Parallel Computing. State of the Art in Scientific Computing
24:
2241:
2191:
1666:
1302:
902:
149:
1541:
1424:
Probabilistic
Mapping of Spatial Motion Patterns for Mobile Robots
1245:
Proceedings of International Conference on Robotics and Automation
2171:
1752:
1420:
1284:
Lai, Tin; Morere, Philippe; Ramos, Fabio; Francis, Gilad (2020).
587:
2226:
1777:
1772:
1624:
1524:
1612:
578:
2196:
1744:
1606:
179:, as well as applications in other fields, such as animating
2231:
1635:
1602:
1030:
687:. Again, collision detection is used to test inclusion in C
167:
Motion planning has several robotics applications, such as
1580:
Chapter 13: Robot Motion Planning: pp. 267–290.
304:
C is the set of all possible configurations. For example:
300:
A configuration describes the pose of the robot, and the
1206:
International Journal of Control, Automation and Systems
1097:
555:. When a path is feasible in X, it is also feasible in C
413:. However, testing whether a given configuration is in C
1591:
1528:, Steven M. LaValle, 2006, Cambridge University Press,
762:
1238:
490:) are used to find a path from the start to the goal.
1340:
1283:
1200:
Hacohen, Shlomi; Shoval, Shraga; Shvalb, Nir (2019).
1017:– similar traditional issue in mechanical engineering
602:
such as counting its number of connected components.
365:
324:
733:
Employs local-sampling by performing a directional
421:
determine the position of the robot's geometry, and
219:
Configuration space of a point-sized robot. White =
1544:, H. Choset, W. Burgard, S. Hutchinson, G. Kantor,
1199:
695:, or the planner did not sample enough milestones.
49:. Unsourced material may be challenged and removed.
1557:
1165:
371:
330:
1471:
1385:
406:in C is called the obstacle or forbidden region.
2349:
1590:"Open Robotics Automation Virtual Environment",
1548:, K. Lynch, and S. Thrun, MIT Press, April 2005.
778:
1427:. Cognitive Systems Monographs. Vol. 40.
713:There are many variants of this basic scheme:
652:
1651:
751:
1388:Journal of Intelligent & Robotic Systems
948:
670:
1465:
839:
1658:
1644:
1074:"Path planning using intervals and graphs"
875:Moving obstacles (time cannot go backward)
1509:. Springer Science & Business Media.
1354:
1301:
1112:
885:
109:Learn how and when to remove this message
1286:"Bayesian Local Sampling-Based Planning"
586:
577:
568:
515:
274:
266:
258:
236:
214:
206:
1502:
610:Point robots among polygonal obstacles
605:
2350:
1071:
740:with some local proposal distribution.
295:
2065:Simultaneous localization and mapping
1639:
1629:"Robot Motion Planning and Control",
1290:IEEE Robotics and Automation Letters
1168:Proc. 2004 FIRA Robot World Congress
630:Translating objects among obstacles
472:
47:adding citations to reliable sources
18:
1631:http://www.laas.fr/%7Ejpl/book.html
1247:. Vol. 3. pp. 2719–2726.
997:computer-aided architectural design
831:
524:X,X made with boxes such that X ⊂ C
159:For example, consider navigating a
13:
1619:https://ai.stanford.edu/~mitul/mpk
1556:& Otfried Schwarzkopf (2000).
1496:
1033:- The Open Motion Planning Library
640:Finding the way out of a building
14:
2379:
2368:Automated planning and scheduling
1584:
1472:Steven M. LaValle (29 May 2006).
890:
437:
2329:
2318:
2317:
1734:
1552:Mark de Berg; Marc van Kreveld;
1170:. Busan, South Korea: Paper 151.
850:Manipulator arms (with dynamics)
23:
2330:
1601:"Open Motion Planning Library (
1414:
958:
783:A motion planner is said to be
428:
34:needs additional citations for
1478:. Cambridge University Press.
1379:
1334:
1277:
1232:
1193:
1174:
1159:
1091:
1065:
924:
1:
1503:Latombe, Jean-Claude (2012).
1182:Planning Algorithms Chapter 8
1058:
1044:– multi-robot motion planning
768:Rapidly-exploring random tree
445:
393:
2363:Theoretical computer science
1665:
1625:http://simox.sourceforge.net
995:Safety and accessibility in
872:Acceleration bounded systems
779:Completeness and performance
510:Incremental heuristic search
7:
2075:Vision-guided robot systems
1613:http://msl.cs.uiuc.edu/msl/
1611:"Motion Strategy Library",
1002:
986:Digital character animation
653:Artificial potential fields
202:
10:
2384:
2295:Technological unemployment
1607:http://ompl.kavrakilab.org
1400:10.1007/s10846-020-01267-0
878:Bevel-tip steerable needle
818:Probabilistic completeness
752:List of notable algorithms
271:Example of an invalid path
2313:
2283:Workplace robotics safety
2265:
2159:
2083:
2046:
2001:
1899:
1743:
1732:
1673:
1433:10.1007/978-3-030-41808-3
1365:10.1017/S0263574713000489
1253:10.1109/ROBOT.1997.619371
1218:10.1007/s12555-018-0563-2
1026:Mountain climbing problem
949:Environmental constraints
943:Networked control systems
881:Differential drive robots
671:Sampling-based algorithms
540:could thus be used when C
1564:(2nd revised ed.).
1312:10.1109/LRA.2020.2969145
840:Differential constraints
789:computational complexity
735:Markov chain Monte Carlo
347:special orthogonal group
2131:Human–robot interaction
1617:"Motion Planning Kit",
1394:. Springer Nature B.V.
811:Resolution completeness
502:Any-angle path planning
372:{\displaystyle \times }
331:{\displaystyle \times }
263:Example of a valid path
1560:Computational Geometry
1042:Pebble motion problems
886:Optimality constraints
658:can become trapped in
592:
584:
575:
373:
332:
280:
272:
264:
256:
234:
212:
211:Example of a workspace
175:, and robot design in
142:computational geometry
2237:Starship Technologies
1506:Robot Motion Planning
1187:15 April 2021 at the
1048:Shortest path problem
919:Reconfigurable robots
773:Probabilistic roadmap
590:
581:
572:
534:set inversion problem
528:⊂ X. Characterizing C
516:Interval-based search
417:is efficient. First,
402:. The complement of C
374:
333:
279:Example of a road map
278:
270:
262:
240:
218:
210:
138:computational problem
134:piano mover's problem
16:Computational problem
2187:Energid Technologies
1592:http://openrave.org/
1021:Kinodynamic planning
903:Robotic manipulation
663:linguistic rules. A
606:Geometric algorithms
363:
322:
197:biological molecules
189:architectural design
43:improve this article
2278:Powered exoskeleton
1525:Planning Algorithms
1475:Planning Algorithms
1123:10.1007/11558958_11
1072:Jaulin, L. (2001).
1009:Moving sofa problem
939:Sensorless planning
933:Missing information
908:Mechanical assembly
793:Turing completeness
665:navigation function
532:amounts to solve a
423:collision detection
302:configuration space
296:Configuration space
290:configuration space
195:, and the study of
128:(also known as the
2247:Universal Robotics
2222:Intuitive Surgical
2212:Harvest Automation
2177:Barrett Technology
1959:Robotic spacecraft
1805:Audio-Animatronics
1241:J.C. Latombe, J.C.
1081:Reliable Computing
930:Motion uncertainty
644:farthest ray trace
620:Cell decomposition
593:
585:
576:
419:forward kinematics
369:
328:
281:
273:
265:
257:
235:
213:
181:digital characters
146:computer animation
130:navigation problem
2345:
2344:
2288:Robotic tech vest
2217:Honeybee Robotics
2033:Electric unicycle
1986:remotely-operated
1575:978-3-540-65620-3
1516:978-1-4615-4022-9
1485:978-1-139-45517-6
1442:978-3-030-41807-6
1262:978-0-7803-3612-4
1180:Lavalle, Steven,
1132:978-3-540-29067-4
1053:Velocity obstacle
954:Maps of dynamics
538:Interval analysis
484:search algorithms
473:Grid-based search
119:
118:
111:
93:
58:"Motion planning"
2375:
2358:Robot kinematics
2333:
2332:
2321:
2320:
2305:Fictional robots
2273:Critique of work
1922:Unmanned vehicle
1738:
1660:
1653:
1646:
1637:
1636:
1579:
1563:
1520:
1490:
1489:
1469:
1463:
1462:
1418:
1412:
1411:
1383:
1377:
1376:
1358:
1349:(8): 1327–1335.
1338:
1332:
1331:
1305:
1296:(2): 1954–1961.
1281:
1275:
1274:
1236:
1230:
1229:
1212:(8): 2097–2113.
1197:
1191:
1178:
1172:
1171:
1163:
1157:
1156:
1150:
1146:
1144:
1136:
1116:
1106:
1095:
1089:
1088:
1078:
1069:
965:Robot navigation
832:Problem variants
615:Visibility graph
596:Nicolas Delanoue
378:
376:
375:
370:
337:
335:
334:
329:
114:
107:
103:
100:
94:
92:
51:
27:
19:
2383:
2382:
2378:
2377:
2376:
2374:
2373:
2372:
2348:
2347:
2346:
2341:
2309:
2261:
2182:Boston Dynamics
2167:Amazon Robotics
2155:
2079:
2070:Visual odometry
2060:Motion planning
2042:
1997:
1917:Continuum robot
1900:Classifications
1895:
1758:Anthropomorphic
1739:
1730:
1726:AI competitions
1669:
1664:
1587:
1576:
1566:Springer-Verlag
1517:
1499:
1497:Further reading
1494:
1493:
1486:
1470:
1466:
1443:
1419:
1415:
1384:
1380:
1356:10.1.1.473.7966
1339:
1335:
1282:
1278:
1263:
1237:
1233:
1198:
1194:
1189:Wayback Machine
1179:
1175:
1164:
1160:
1148:
1147:
1138:
1137:
1133:
1114:10.1.1.123.6764
1104:
1096:
1092:
1076:
1070:
1066:
1061:
1005:
991:Protein folding
981:Robotic surgery
961:
951:
927:
893:
888:
842:
834:
781:
754:
709:
706:conditions on C
694:
690:
686:
678:
673:
655:
625:Voronoi diagram
608:
601:
562:
558:
543:
531:
527:
518:
496:
481:
475:
453:
448:
440:
431:
416:
412:
405:
401:
396:
364:
361:
360:
323:
320:
319:
298:
253:
246:
231:
224:
205:
193:robotic surgery
122:Motion planning
115:
104:
98:
95:
52:
50:
40:
28:
17:
12:
11:
5:
2381:
2371:
2370:
2365:
2360:
2343:
2342:
2340:
2339:
2327:
2314:
2311:
2310:
2308:
2307:
2302:
2300:Terrainability
2297:
2292:
2291:
2290:
2280:
2275:
2269:
2267:
2263:
2262:
2260:
2259:
2254:
2249:
2244:
2239:
2234:
2229:
2224:
2219:
2214:
2209:
2204:
2199:
2194:
2189:
2184:
2179:
2174:
2169:
2163:
2161:
2157:
2156:
2154:
2153:
2148:
2143:
2138:
2133:
2128:
2123:
2118:
2113:
2108:
2103:
2098:
2093:
2087:
2085:
2081:
2080:
2078:
2077:
2072:
2067:
2062:
2056:
2054:
2044:
2043:
2041:
2040:
2035:
2030:
2025:
2024:
2023:
2013:
2007:
2005:
1999:
1998:
1996:
1995:
1994:
1993:
1988:
1978:
1973:
1968:
1967:
1966:
1956:
1951:
1946:
1941:
1936:
1935:
1934:
1929:
1919:
1914:
1912:Cloud robotics
1909:
1903:
1901:
1897:
1896:
1894:
1893:
1888:
1883:
1878:
1873:
1868:
1863:
1858:
1853:
1848:
1843:
1838:
1833:
1828:
1827:
1826:
1816:
1811:
1810:
1809:
1808:
1807:
1792:
1787:
1782:
1781:
1780:
1775:
1770:
1765:
1755:
1749:
1747:
1741:
1740:
1733:
1731:
1729:
1728:
1723:
1718:
1713:
1708:
1703:
1698:
1693:
1688:
1683:
1677:
1675:
1671:
1670:
1663:
1662:
1655:
1648:
1640:
1634:
1633:
1627:
1621:
1615:
1609:
1599:
1594:
1586:
1585:External links
1583:
1582:
1581:
1574:
1549:
1537:
1521:
1515:
1498:
1495:
1492:
1491:
1484:
1464:
1441:
1413:
1378:
1333:
1276:
1261:
1231:
1192:
1173:
1158:
1149:|journal=
1131:
1090:
1063:
1062:
1060:
1057:
1056:
1055:
1050:
1045:
1039:
1034:
1028:
1023:
1018:
1012:
1004:
1001:
1000:
999:
993:
988:
983:
978:
976:driverless car
972:
967:
960:
957:
956:
955:
950:
947:
946:
945:
940:
937:
936:Active sensing
934:
931:
926:
923:
922:
921:
916:
910:
905:
896:Hybrid systems
892:
891:Hybrid systems
889:
887:
884:
883:
882:
879:
876:
873:
870:
867:
864:
861:
852:
851:
841:
838:
833:
830:
801:watchdog timer
780:
777:
776:
775:
770:
765:
760:
753:
750:
749:
748:
744:
741:
731:
721:
718:
707:
692:
688:
684:
676:
672:
669:
654:
651:
646:
645:
638:
637:
628:
627:
622:
617:
607:
604:
599:
560:
556:
541:
529:
525:
517:
514:
494:
479:
474:
471:
451:
447:
444:
439:
438:Obstacle space
436:
430:
427:
414:
410:
403:
399:
395:
392:
391:
390:
387:
368:
350:
327:
309:
297:
294:
251:
244:
229:
222:
204:
201:
154:computer games
117:
116:
31:
29:
22:
15:
9:
6:
4:
3:
2:
2380:
2369:
2366:
2364:
2361:
2359:
2356:
2355:
2353:
2338:
2337:
2328:
2326:
2325:
2316:
2315:
2312:
2306:
2303:
2301:
2298:
2296:
2293:
2289:
2286:
2285:
2284:
2281:
2279:
2276:
2274:
2271:
2270:
2268:
2264:
2258:
2255:
2253:
2252:Wolf Robotics
2250:
2248:
2245:
2243:
2240:
2238:
2235:
2233:
2230:
2228:
2225:
2223:
2220:
2218:
2215:
2213:
2210:
2208:
2207:Foster-Miller
2205:
2203:
2200:
2198:
2195:
2193:
2190:
2188:
2185:
2183:
2180:
2178:
2175:
2173:
2170:
2168:
2165:
2164:
2162:
2158:
2152:
2149:
2147:
2144:
2142:
2139:
2137:
2134:
2132:
2129:
2127:
2126:Developmental
2124:
2122:
2119:
2117:
2114:
2112:
2109:
2107:
2104:
2102:
2099:
2097:
2094:
2092:
2089:
2088:
2086:
2082:
2076:
2073:
2071:
2068:
2066:
2063:
2061:
2058:
2057:
2055:
2053:
2049:
2045:
2039:
2036:
2034:
2031:
2029:
2026:
2022:
2019:
2018:
2017:
2014:
2012:
2009:
2008:
2006:
2004:
2000:
1992:
1989:
1987:
1984:
1983:
1982:
1979:
1977:
1974:
1972:
1969:
1965:
1962:
1961:
1960:
1957:
1955:
1952:
1950:
1947:
1945:
1942:
1940:
1937:
1933:
1930:
1928:
1925:
1924:
1923:
1920:
1918:
1915:
1913:
1910:
1908:
1905:
1904:
1902:
1898:
1892:
1891:Soft robotics
1889:
1887:
1886:BEAM robotics
1884:
1882:
1879:
1877:
1874:
1872:
1869:
1867:
1864:
1862:
1859:
1857:
1854:
1852:
1849:
1847:
1844:
1842:
1841:Entertainment
1839:
1837:
1834:
1832:
1829:
1825:
1822:
1821:
1820:
1817:
1815:
1812:
1806:
1803:
1802:
1801:
1798:
1797:
1796:
1793:
1791:
1788:
1786:
1783:
1779:
1776:
1774:
1771:
1769:
1766:
1764:
1761:
1760:
1759:
1756:
1754:
1751:
1750:
1748:
1746:
1742:
1737:
1727:
1724:
1722:
1719:
1717:
1714:
1712:
1709:
1707:
1704:
1702:
1699:
1697:
1694:
1692:
1689:
1687:
1684:
1682:
1679:
1678:
1676:
1674:Main articles
1672:
1668:
1661:
1656:
1654:
1649:
1647:
1642:
1641:
1638:
1632:
1628:
1626:
1622:
1620:
1616:
1614:
1610:
1608:
1604:
1600:
1598:
1595:
1593:
1589:
1588:
1577:
1571:
1567:
1562:
1561:
1555:
1554:Mark Overmars
1550:
1547:
1546:L. E. Kavraki
1543:
1542:
1538:
1535:
1534:0-521-86205-1
1531:
1527:
1526:
1522:
1518:
1512:
1508:
1507:
1501:
1500:
1487:
1481:
1477:
1476:
1468:
1460:
1456:
1452:
1448:
1444:
1438:
1434:
1430:
1426:
1425:
1417:
1409:
1405:
1401:
1397:
1393:
1389:
1382:
1374:
1370:
1366:
1362:
1357:
1352:
1348:
1344:
1337:
1329:
1325:
1321:
1317:
1313:
1309:
1304:
1299:
1295:
1291:
1287:
1280:
1272:
1268:
1264:
1258:
1254:
1250:
1246:
1242:
1235:
1227:
1223:
1219:
1215:
1211:
1207:
1203:
1196:
1190:
1186:
1183:
1177:
1169:
1162:
1154:
1142:
1134:
1128:
1124:
1120:
1115:
1110:
1103:
1102:
1094:
1086:
1082:
1075:
1068:
1064:
1054:
1051:
1049:
1046:
1043:
1040:
1038:
1035:
1032:
1029:
1027:
1024:
1022:
1019:
1016:
1013:
1010:
1007:
1006:
998:
994:
992:
989:
987:
984:
982:
979:
977:
973:
971:
968:
966:
963:
962:
953:
952:
944:
941:
938:
935:
932:
929:
928:
920:
917:
914:
911:
909:
906:
904:
901:
900:
899:
897:
880:
877:
874:
871:
868:
865:
862:
859:
858:
857:
856:
849:
848:
847:
846:
837:
829:
826:
822:
819:
815:
812:
808:
804:
802:
796:
794:
790:
786:
774:
771:
769:
766:
764:
761:
759:
756:
755:
745:
742:
739:
736:
732:
729:
725:
722:
719:
716:
715:
714:
711:
705:
700:
696:
682:
668:
666:
661:
650:
643:
642:
641:
636:
635:Minkowski sum
633:
632:
631:
626:
623:
621:
618:
616:
613:
612:
611:
603:
597:
589:
580:
571:
567:
564:
554:
550:
545:
539:
535:
523:
513:
511:
505:
503:
498:
491:
489:
485:
470:
468:
467:legged robots
462:
460:
455:
443:
435:
426:
424:
420:
407:
388:
385:
381:
366:
359:
355:
351:
348:
344:
340:
325:
318:
314:
310:
307:
306:
305:
303:
293:
291:
287:
277:
269:
261:
254:
247:
239:
232:
225:
217:
209:
200:
198:
194:
190:
186:
182:
178:
174:
170:
165:
162:
157:
155:
151:
147:
143:
139:
135:
131:
127:
126:path planning
123:
113:
110:
102:
91:
88:
84:
81:
77:
74:
70:
67:
63:
60: –
59:
55:
54:Find sources:
48:
44:
38:
37:
32:This article
30:
26:
21:
20:
2334:
2322:
2091:Evolutionary
2059:
2038:Robotic fins
1991:Robotic fish
1976:Telerobotics
1949:Nanorobotics
1939:Mobile robot
1876:Food service
1871:Agricultural
1721:Competitions
1706:Hall of Fame
1559:
1539:
1523:
1505:
1474:
1467:
1423:
1416:
1391:
1387:
1381:
1346:
1342:
1336:
1293:
1289:
1279:
1244:
1234:
1209:
1205:
1195:
1176:
1167:
1161:
1100:
1093:
1084:
1080:
1067:
959:Applications
913:Legged robot
894:
855:Nonholonomic
853:
843:
835:
824:
823:
817:
816:
810:
809:
805:
797:
784:
782:
728:pseudorandom
712:
703:
702:Given basic
701:
697:
680:
674:
660:local minima
656:
647:
639:
629:
609:
594:
565:
546:
519:
506:
499:
492:
476:
463:
456:
449:
441:
432:
429:Target space
408:
397:
384:Euler angles
379:
357:
353:
342:
338:
316:
312:
299:
285:
282:
249:
242:
227:
220:
177:CAD software
166:
161:mobile robot
158:
133:
129:
125:
121:
120:
105:
96:
86:
79:
72:
65:
53:
41:Please help
36:verification
33:
2111:Open-source
1964:Space probe
1954:Necrobotics
1944:Microbotics
1907:Biorobotics
1836:Educational
1819:Articulated
1800:Animatronic
1785:Claytronics
1037:Pathfinding
1015:Gimbal lock
925:Uncertainty
738:random walk
724:Quasirandom
459:intractable
345:(2) is the
341:(2) (where
2352:Categories
2151:Ubiquitous
2141:Perceptual
2048:Navigation
2003:Locomotion
1981:Underwater
1866:Disability
1814:Industrial
1303:1909.03452
1059:References
970:Automation
915:locomotion
825:Incomplete
704:visibility
681:milestones
679:to use as
522:subpavings
446:Algorithms
394:Free space
386:(α, β, γ).
185:video game
173:automation
69:newspapers
2202:Figure AI
2160:Companies
2136:Paradigms
2121:Adaptable
2101:Simulator
1795:Automaton
1790:Companion
1701:Geography
1623:"Simox",
1451:1867-4925
1408:229326435
1351:CiteSeerX
1328:210838739
1320:2377-3766
1239:Hsu, D.;
1226:164509949
1151:ignored (
1141:cite book
1109:CiteSeerX
866:Unicycles
845:Holonomic
747:planning)
367:×
326:×
286:workspace
248:, gray =
226:, gray =
99:June 2013
2324:Category
2242:Symbotic
2192:FarmWise
2146:Situated
2116:Software
2084:Research
2028:Climbing
1851:Military
1846:Juggling
1831:Domestic
1763:Humanoid
1686:Glossary
1667:Robotics
1459:52087877
1373:17483785
1343:Robotica
1271:11070889
1185:Archived
1003:See also
785:complete
574:freedom.
549:Dijkstra
203:Concepts
169:autonomy
150:robotics
2336:Outline
2266:Related
2257:Yaskawa
2172:Anybots
2052:mapping
2021:Hexapod
2016:Walking
1861:Service
1856:Medical
1768:Android
1753:Aerobot
1696:History
1681:Outline
136:) is a
132:or the
124:, also
83:scholar
2227:IRobot
2011:Tracks
1932:ground
1927:aerial
1881:Retail
1778:Gynoid
1773:Cyborg
1711:Ethics
1572:
1532:
1513:
1482:
1457:
1449:
1439:
1406:
1371:
1353:
1326:
1318:
1269:
1259:
1224:
1129:
1111:
869:Planes
860:Drones
583:above.
486:(like
315:(2) =
85:
78:
71:
64:
56:
2197:FANUC
2106:Suite
1971:Swarm
1745:Types
1691:Index
1455:S2CID
1404:S2CID
1369:S2CID
1324:S2CID
1298:arXiv
1267:S2CID
1222:S2CID
1105:(PDF)
1077:(PDF)
354:SE(3)
90:JSTOR
76:books
2232:KUKA
2096:Kits
2050:and
1716:Laws
1605:)",
1603:OMPL
1570:ISBN
1530:ISBN
1511:ISBN
1480:ISBN
1447:ISSN
1437:ISBN
1316:ISSN
1257:ISBN
1153:help
1127:ISBN
1087:(1).
1031:OMPL
974:The
863:Cars
708:free
693:free
689:free
685:free
677:free
600:free
561:free
557:free
542:free
530:free
526:free
495:free
480:free
452:free
415:free
411:free
404:free
400:free
245:free
223:free
152:and
62:news
1824:arm
1429:doi
1396:doi
1392:101
1361:doi
1308:doi
1249:doi
1214:doi
1119:doi
551:or
469:).
252:obs
230:obs
45:by
2354::
1568:.
1453:.
1445:.
1435:.
1402:.
1390:.
1367:.
1359:.
1347:31
1345:.
1322:.
1314:.
1306:.
1292:.
1288:.
1265:.
1255:.
1220:.
1210:17
1208:.
1204:.
1145::
1143:}}
1139:{{
1125:.
1117:.
1083:.
1079:.
763:D*
758:A*
553:A*
536:.
488:A*
454:.
380:SO
356:=
343:SO
339:SO
313:SE
292:.
199:.
191:,
187:,
183:,
171:,
156:.
148:,
144:,
1659:e
1652:t
1645:v
1578:.
1536:.
1519:.
1488:.
1461:.
1431::
1410:.
1398::
1375:.
1363::
1330:.
1310::
1300::
1294:5
1273:.
1251::
1228:.
1216::
1155:)
1135:.
1121::
1085:7
478:C
358:R
317:R
250:C
243:C
233:.
228:C
221:C
112:)
106:(
101:)
97:(
87:·
80:·
73:·
66:·
39:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
