1336:
BoxAt(Location), Level(low) Postconditions: Level(high), not Level(low) // climb down from the box _ClimbDown(Location)_ Preconditions: At(Location), BoxAt(Location), Level(high) Postconditions: Level(low), not Level(high) // move monkey and box from X to Y _MoveBox(X, Y)_ Preconditions: At(X), BoxAt(X), Level(low) Postconditions: BoxAt(Y), not BoxAt(X), At(Y), not At(X) // take the bananas _TakeBananas(Location)_ Preconditions: At(Location), BananasAt(Location), Level(high) Postconditions: Have(bananas)
1368:, the robot monkey has to execute a sequence of actions to reach the banana at the ceiling. A single action provides a small change in the game. To simplify the planning process, it make sense to invent an abstract action, which isn't available in the normal rule description. The super-action consists of low level actions and can reach high-level goals. The advantage is that the
310:
Formally, a state is a set of conditions: a state is represented by the set of conditions that are true in it. Transitions between states are modeled by a transition function, which is a function mapping states into new states that result from the execution of actions. Since states are represented by
1335:
Actions: // move from X to Y _Move(X, Y)_ Preconditions: At(X), Level(low) Postconditions: not At(X), At(Y) // climb up on the box _ClimbUp(Location)_ Preconditions: At(Location),
1319:
are all assumed false. This is often a limiting assumption, as there are natural examples of planning problems in which the initial state is not fully known. Extensions of STRIPS have been developed to deal with partially known initial states.
951:
227:, each element being a set of conditions. These four sets specify, in order, which conditions must be true for the action to be executable, which ones must be false, which ones are made true by the action and which ones are made false;
577:
1383:, a macro-operator is called an option. Similar to the definition within AI planning, the idea is, to provide a temporal abstraction (span over a longer period) and to modify the game state directly on a higher layer.
1328:
A monkey is at location A in a lab. There is a box in location C. The monkey wants the bananas that are hanging from the ceiling in location B, but it needs to move the box and climb onto it in order to reach them.
411:
225:
617:
1296:, which are implicitly existentially quantified. In other words, an action represents all possible propositional actions that can be obtained by replacing each free variable with a value.
956:
A plan for a STRIPS instance is a sequence of actions such that the state that results from executing the actions in order from the initial state satisfies the goal conditions. Formally,
1146:
786:
678:
353:
124:
1057:
733:
484:
1208:
301:
646:
1175:
510:
1290:
792:
1632:
441:
1246:
1317:
705:
461:
269:
247:
177:
147:
1019:
1379:. The idea is, not to plan the domain itself, but in the pre-step, a heuristics is created that allows the domain to be solved much faster. In the context of
520:
512:, can be defined as follows, using the simplifying assumption that actions can always be executed but have no effect if their preconditions are not met:
1605:
361:
307:
A plan for such a planning instance is a sequence of operators that can be executed from the initial state and that leads to a goal state.
1677:
1682:
186:
1222:
version of STRIPS; in practice, conditions are often about objects: for example, that the position of a robot can be modeled by a
1687:
1408:
584:
303:, which specify which conditions are true and false, respectively, in order for a state to be considered a goal state.
1659:
1443:
1062:
741:
651:
1435:
314:
85:
249:
is the initial state, given as the set of conditions that are initially true (all others are assumed false);
1024:
718:
469:
1181:
1392:
274:
1533:. Proceedings of the 20th International Joint Conference on Artificial Intelligence. pp. 1898–1903.
1489:
1299:
The initial state is considered fully known in the language described above: conditions that are not in
625:
1403:
1365:
33:
1457:
1369:
1506:
1154:
489:
44:
of the inputs to this planner. This language is the base for most of the languages for expressing
1223:
946:{\displaystyle \operatorname {succ} (C,)=\operatorname {succ} (\operatorname {succ} (C,a_{1}),)}
1692:
1501:
1452:
1380:
1251:
154:
1599:
1574:"Between MDPs and semi-MDPs: A framework for temporal abstraction in reinforcement learning"
419:
8:
1376:
1219:
1228:
1571:
1549:
Iterative macro-operators revisited: Applying program synthesis to learning in planning
1470:
1398:
1302:
690:
572:{\displaystyle \operatorname {succ} (C,\langle \alpha ,\beta ,\gamma ,\delta \rangle )}
446:
254:
232:
162:
132:
45:
25:
1590:
1573:
1332:
Initial state: At(A), Level(low), BoxAt(C), BananasAt(B) Goal state: Have(bananas)
959:
67:
The specification of the goal states – situations that the planner is trying to reach;
1655:
1641:
1515:
1466:
37:
1585:
1552:
1511:
1474:
1462:
1436:"STRIPS: A New Approach to the Application of Theorem Proving to Problem Solving"
1414:
49:
41:
1349:
1348:. Various restrictions can be enforced in order to decide if a plan exists in
735:
can be extended to sequences of actions by the following recursive equations:
1671:
1293:
29:
311:
sets of conditions, the transition function relative to the STRIPS instance
1645:
1551:(Technical report). School of Computer Science Carnegie Mellon University.
1353:
1622:
C. Bäckström and B. Nebel (1995). Complexity results for SAS+ planning.
1344:
Deciding whether any plan exists for a propositional STRIPS instance is
73:
preconditions (what must be established before the action is performed);
1557:
1544:
406:{\displaystyle \operatorname {succ} :2^{P}\times O\rightarrow 2^{P},}
48:
problem instances in use today; such languages are commonly known as
76:
postconditions (what is established after the action is performed).
1375:
Identifying new macro operators for a domain can be realized with
1433:
1292:
means that the robot is in Room1. In this case, actions can have
1572:
Sutton, Richard S and Precup, Doina and Singh, Satinder (1999).
271:
is the specification of the goal state; this is given as a pair
1654:(2nd ed.), Upper Saddle River, New Jersey: Prentice Hall,
1649:
1490:"The Computational Complexity of Propositional STRIPS Planning"
1345:
70:
A set of actions. For each action, the following are included:
220:{\displaystyle \langle \alpha ,\beta ,\gamma ,\delta \rangle }
52:. This article only describes the language, not the planner.
1372:
is lower, and longer tasks can be planned by the solver.
1633:
International Joint
Conference on Artificial Intelligence
1629:
T. Bylander (1991). Complexity results for planning. In
594:
1305:
1254:
1231:
1184:
1157:
1065:
1027:
962:
795:
744:
721:
693:
654:
628:
587:
523:
492:
472:
449:
422:
364:
317:
277:
257:
235:
189:
183:(i.e., actions); each operator is itself a quadruple
165:
135:
126:, in which each component has the following meaning:
88:
1531:
Reducing
Accidental Complexity in Planning Problems
463:, and is therefore the set of all possible states.
1311:
1284:
1240:
1202:
1169:
1140:
1051:
1013:
945:
780:
727:
699:
672:
640:
611:
571:
504:
478:
455:
435:
405:
347:
295:
263:
241:
219:
171:
141:
118:
82:Mathematically, a STRIPS instance is a quadruple
1434:Richard E. Fikes, Nils J. Nilsson (Winter 1971).
612:{\displaystyle (C\backslash \delta )\cup \gamma }
1669:
40:. The same name was later used to refer to the
1528:
1640:
1604:: CS1 maint: multiple names: authors list (
1487:
1046:
1034:
563:
539:
342:
318:
290:
278:
214:
190:
113:
89:
1543:
1141:{\displaystyle F=\operatorname {succ} (I,)}
781:{\displaystyle \operatorname {succ} (C,)=C}
1651:Artificial Intelligence: A Modern Approach
1323:
18:Stanford Research Institute Problem Solver
1589:
1556:
1505:
1456:
673:{\displaystyle \beta \cap C=\varnothing }
1148:satisfies the following two conditions:
348:{\displaystyle \langle P,O,I,G\rangle }
119:{\displaystyle \langle P,O,I,G\rangle }
1670:
1052:{\displaystyle G=\langle N,M\rangle }
728:{\displaystyle \operatorname {succ} }
479:{\displaystyle \operatorname {succ} }
1203:{\displaystyle M\cap F=\varnothing }
1409:Planning Domain Definition Language
1218:The above language is actually the
296:{\displaystyle \langle N,M\rangle }
13:
1678:History of artificial intelligence
1616:
641:{\displaystyle \alpha \subseteq C}
60:A STRIPS instance is composed of:
14:
1704:
1683:Automated planning and scheduling
1359:
1197:
667:
1488:Tom Bylander (September 1994).
1565:
1537:
1522:
1481:
1427:
1279:
1261:
1135:
1132:
1087:
1078:
1008:
963:
940:
937:
905:
899:
880:
871:
859:
856:
811:
802:
769:
766:
760:
751:
600:
588:
566:
530:
387:
1:
1591:10.1016/s0004-3702(99)00052-1
1420:
1339:
1213:
443:is the set of all subsets of
55:
1516:10.1016/0004-3702(94)90081-7
1467:10.1016/0004-3702(71)90010-5
1170:{\displaystyle N\subseteq F}
619:
505:{\displaystyle C\subseteq P}
7:
1631:Proceedings of the Twelfth
1393:Action description language
1386:
10:
1709:
1688:SRI International software
1624:Computational Intelligence
1584:(1–2). Elsevier: 181–211.
1404:Hierarchical task network
1366:monkey and banana problem
1285:{\displaystyle At(room1)}
1370:computational complexity
466:The transition function
1578:Artificial Intelligence
1529:Haslum, Patrik (2007).
1494:Artificial Intelligence
1444:Artificial Intelligence
1352:or at least make it an
1324:A sample STRIPS problem
155:propositional variables
20:, known by its acronym
1381:reinforcement learning
1313:
1286:
1242:
1204:
1171:
1142:
1053:
1015:
947:
782:
729:
701:
674:
642:
613:
573:
506:
480:
457:
437:
407:
349:
297:
265:
243:
221:
173:
143:
120:
1314:
1287:
1243:
1205:
1172:
1143:
1054:
1016:
948:
783:
730:
702:
675:
643:
614:
574:
507:
481:
458:
438:
436:{\displaystyle 2^{P}}
408:
350:
298:
266:
244:
222:
174:
144:
121:
1303:
1252:
1229:
1182:
1155:
1063:
1025:
960:
793:
742:
719:
691:
652:
626:
585:
521:
490:
470:
447:
420:
362:
315:
275:
255:
233:
187:
163:
133:
86:
1377:genetic programming
1642:Russell, Stuart J.
1558:10.21236/ada363524
1399:Automated planning
1309:
1282:
1241:{\displaystyle At}
1238:
1200:
1167:
1138:
1049:
1011:
943:
778:
725:
697:
670:
638:
609:
569:
502:
476:
453:
433:
403:
345:
293:
261:
239:
217:
169:
139:
116:
46:automated planning
1312:{\displaystyle I}
765:
713:
712:
700:{\displaystyle C}
456:{\displaystyle P}
264:{\displaystyle G}
242:{\displaystyle I}
172:{\displaystyle O}
142:{\displaystyle P}
64:An initial state;
38:SRI International
26:automated planner
1700:
1664:
1637:, pages 274-279.
1610:
1609:
1603:
1595:
1593:
1569:
1563:
1562:
1560:
1541:
1535:
1534:
1526:
1520:
1519:
1509:
1500:(1–2): 165–204.
1485:
1479:
1478:
1460:
1451:(3–4): 189–208.
1440:
1431:
1318:
1316:
1315:
1310:
1291:
1289:
1288:
1283:
1247:
1245:
1244:
1239:
1209:
1207:
1206:
1201:
1176:
1174:
1173:
1168:
1147:
1145:
1144:
1139:
1131:
1130:
1112:
1111:
1099:
1098:
1058:
1056:
1055:
1050:
1020:
1018:
1017:
1014:{\displaystyle }
1012:
1007:
1006:
988:
987:
975:
974:
952:
950:
949:
944:
936:
935:
917:
916:
898:
897:
855:
854:
836:
835:
823:
822:
787:
785:
784:
779:
763:
734:
732:
731:
726:
706:
704:
703:
698:
679:
677:
676:
671:
647:
645:
644:
639:
618:
616:
615:
610:
578:
576:
575:
570:
515:
514:
511:
509:
508:
503:
485:
483:
482:
477:
462:
460:
459:
454:
442:
440:
439:
434:
432:
431:
412:
410:
409:
404:
399:
398:
380:
379:
354:
352:
351:
346:
302:
300:
299:
294:
270:
268:
267:
262:
248:
246:
245:
240:
226:
224:
223:
218:
178:
176:
175:
170:
148:
146:
145:
140:
125:
123:
122:
117:
50:action languages
1708:
1707:
1703:
1702:
1701:
1699:
1698:
1697:
1668:
1667:
1662:
1619:
1617:Further reading
1614:
1613:
1597:
1596:
1570:
1566:
1542:
1538:
1527:
1523:
1486:
1482:
1438:
1432:
1428:
1423:
1415:Sussman anomaly
1389:
1362:
1350:polynomial time
1346:PSPACE-complete
1342:
1337:
1333:
1326:
1304:
1301:
1300:
1253:
1250:
1249:
1230:
1227:
1226:
1216:
1183:
1180:
1179:
1156:
1153:
1152:
1126:
1122:
1107:
1103:
1094:
1090:
1064:
1061:
1060:
1026:
1023:
1022:
1002:
998:
983:
979:
970:
966:
961:
958:
957:
931:
927:
912:
908:
893:
889:
850:
846:
831:
827:
818:
814:
794:
791:
790:
743:
740:
739:
720:
717:
716:
692:
689:
688:
653:
650:
649:
627:
624:
623:
586:
583:
582:
522:
519:
518:
491:
488:
487:
471:
468:
467:
448:
445:
444:
427:
423:
421:
418:
417:
394:
390:
375:
371:
363:
360:
359:
316:
313:
312:
276:
273:
272:
256:
253:
252:
234:
231:
230:
188:
185:
184:
164:
161:
160:
134:
131:
130:
87:
84:
83:
58:
42:formal language
12:
11:
5:
1706:
1696:
1695:
1690:
1685:
1680:
1666:
1665:
1660:
1638:
1627:
1618:
1615:
1612:
1611:
1564:
1536:
1521:
1480:
1458:10.1.1.78.8292
1425:
1424:
1422:
1419:
1418:
1417:
1412:
1406:
1401:
1396:
1388:
1385:
1361:
1360:Macro operator
1358:
1341:
1338:
1334:
1331:
1325:
1322:
1308:
1294:free variables
1281:
1278:
1275:
1272:
1269:
1266:
1263:
1260:
1257:
1237:
1234:
1215:
1212:
1211:
1210:
1199:
1196:
1193:
1190:
1187:
1177:
1166:
1163:
1160:
1137:
1134:
1129:
1125:
1121:
1118:
1115:
1110:
1106:
1102:
1097:
1093:
1089:
1086:
1083:
1080:
1077:
1074:
1071:
1068:
1048:
1045:
1042:
1039:
1036:
1033:
1030:
1021:is a plan for
1010:
1005:
1001:
997:
994:
991:
986:
982:
978:
973:
969:
965:
954:
953:
942:
939:
934:
930:
926:
923:
920:
915:
911:
907:
904:
901:
896:
892:
888:
885:
882:
879:
876:
873:
870:
867:
864:
861:
858:
853:
849:
845:
842:
839:
834:
830:
826:
821:
817:
813:
810:
807:
804:
801:
798:
788:
777:
774:
771:
768:
762:
759:
756:
753:
750:
747:
724:
711:
710:
707:
696:
685:
681:
680:
669:
666:
663:
660:
657:
637:
634:
631:
620:
608:
605:
602:
599:
596:
593:
590:
579:
568:
565:
562:
559:
556:
553:
550:
547:
544:
541:
538:
535:
532:
529:
526:
501:
498:
495:
475:
452:
430:
426:
414:
413:
402:
397:
393:
389:
386:
383:
378:
374:
370:
367:
355:is a function
344:
341:
338:
335:
332:
329:
326:
323:
320:
305:
304:
292:
289:
286:
283:
280:
260:
250:
238:
228:
216:
213:
210:
207:
204:
201:
198:
195:
192:
168:
158:
138:
115:
112:
109:
106:
103:
100:
97:
94:
91:
80:
79:
78:
77:
74:
68:
65:
57:
54:
9:
6:
4:
3:
2:
1705:
1694:
1693:1971 software
1691:
1689:
1686:
1684:
1681:
1679:
1676:
1675:
1673:
1663:
1661:0-13-790395-2
1657:
1653:
1652:
1647:
1646:Norvig, Peter
1643:
1639:
1636:
1634:
1628:
1626:, 11:625-656.
1625:
1621:
1620:
1607:
1601:
1592:
1587:
1583:
1579:
1575:
1568:
1559:
1554:
1550:
1546:
1540:
1532:
1525:
1517:
1513:
1508:
1507:10.1.1.23.199
1503:
1499:
1495:
1491:
1484:
1476:
1472:
1468:
1464:
1459:
1454:
1450:
1446:
1445:
1437:
1430:
1426:
1416:
1413:
1410:
1407:
1405:
1402:
1400:
1397:
1394:
1391:
1390:
1384:
1382:
1378:
1373:
1371:
1367:
1357:
1355:
1351:
1347:
1330:
1321:
1306:
1297:
1295:
1276:
1273:
1270:
1267:
1264:
1258:
1255:
1235:
1232:
1225:
1221:
1220:propositional
1194:
1191:
1188:
1185:
1178:
1164:
1161:
1158:
1151:
1150:
1149:
1127:
1123:
1119:
1116:
1113:
1108:
1104:
1100:
1095:
1091:
1084:
1081:
1075:
1072:
1069:
1066:
1043:
1040:
1037:
1031:
1028:
1003:
999:
995:
992:
989:
984:
980:
976:
971:
967:
932:
928:
924:
921:
918:
913:
909:
902:
894:
890:
886:
883:
877:
874:
868:
865:
862:
851:
847:
843:
840:
837:
832:
828:
824:
819:
815:
808:
805:
799:
796:
789:
775:
772:
757:
754:
748:
745:
738:
737:
736:
722:
715:The function
708:
694:
686:
683:
682:
664:
661:
658:
655:
635:
632:
629:
621:
606:
603:
597:
591:
580:
560:
557:
554:
551:
548:
545:
542:
536:
533:
527:
524:
517:
516:
513:
499:
496:
493:
473:
464:
450:
428:
424:
400:
395:
391:
384:
381:
376:
372:
368:
365:
358:
357:
356:
339:
336:
333:
330:
327:
324:
321:
308:
287:
284:
281:
258:
251:
236:
229:
211:
208:
205:
202:
199:
196:
193:
182:
166:
159:
156:
152:
136:
129:
128:
127:
110:
107:
104:
101:
98:
95:
92:
75:
72:
71:
69:
66:
63:
62:
61:
53:
51:
47:
43:
39:
35:
31:
30:Richard Fikes
28:developed by
27:
23:
19:
1650:
1630:
1623:
1600:cite journal
1581:
1577:
1567:
1548:
1539:
1530:
1524:
1497:
1493:
1483:
1448:
1442:
1429:
1374:
1363:
1343:
1327:
1298:
1217:
955:
714:
486:for a state
465:
415:
309:
306:
180:
179:is a set of
150:
149:is a set of
81:
59:
34:Nils Nilsson
21:
17:
15:
1545:Schmid, Ute
1354:NP-complete
36:in 1971 at
1672:Categories
1635:(IJCAI'91)
1421:References
1340:Complexity
1214:Extensions
709:otherwise
151:conditions
56:Definition
1502:CiteSeerX
1453:CiteSeerX
1356:problem.
1224:predicate
1198:∅
1189:∩
1162:⊆
1117:…
1076:
1047:⟩
1035:⟨
993:…
922:…
878:
869:
841:…
800:
749:
668:∅
659:∩
656:β
633:⊆
630:α
607:γ
604:∪
598:δ
595:∖
564:⟩
561:δ
555:γ
549:β
543:α
540:⟨
528:
497:⊆
388:→
382:×
343:⟩
319:⟨
291:⟩
279:⟨
215:⟩
212:δ
206:γ
200:β
194:α
191:⟨
181:operators
114:⟩
90:⟨
1648:(2003),
1547:(1999).
1387:See also
24:, is an
1475:8623866
1364:In the
684:
153:(i.e.,
1658:
1504:
1473:
1455:
1411:(PDDL)
1248:, and
764:
416:where
22:STRIPS
1471:S2CID
1439:(PDF)
1395:(ADL)
1656:ISBN
1606:link
1073:succ
875:succ
866:succ
797:succ
746:succ
723:succ
648:and
525:succ
474:succ
366:succ
32:and
16:The
1586:doi
1582:112
1553:doi
1512:doi
1463:doi
1059:if
622:if
1674::
1644:;
1602:}}
1598:{{
1580:.
1576:.
1510:.
1498:69
1496:.
1492:.
1469:.
1461:.
1447:.
1441:.
687:=
581:=
157:);
1608:)
1594:.
1588::
1561:.
1555::
1518:.
1514::
1477:.
1465::
1449:2
1307:I
1280:)
1277:1
1274:m
1271:o
1268:o
1265:r
1262:(
1259:t
1256:A
1236:t
1233:A
1195:=
1192:F
1186:M
1165:F
1159:N
1136:)
1133:]
1128:n
1124:a
1120:,
1114:,
1109:2
1105:a
1101:,
1096:1
1092:a
1088:[
1085:,
1082:I
1079:(
1070:=
1067:F
1044:M
1041:,
1038:N
1032:=
1029:G
1009:]
1004:n
1000:a
996:,
990:,
985:2
981:a
977:,
972:1
968:a
964:[
941:)
938:]
933:n
929:a
925:,
919:,
914:2
910:a
906:[
903:,
900:)
895:1
891:a
887:,
884:C
881:(
872:(
863:=
860:)
857:]
852:n
848:a
844:,
838:,
833:2
829:a
825:,
820:1
816:a
812:[
809:,
806:C
803:(
776:C
773:=
770:)
767:]
761:[
758:,
755:C
752:(
695:C
665:=
662:C
636:C
601:)
592:C
589:(
567:)
558:,
552:,
546:,
537:,
534:C
531:(
500:P
494:C
451:P
429:P
425:2
401:,
396:P
392:2
385:O
377:P
373:2
369::
340:G
337:,
334:I
331:,
328:O
325:,
322:P
288:M
285:,
282:N
259:G
237:I
209:,
203:,
197:,
167:O
137:P
111:G
108:,
105:I
102:,
99:O
96:,
93:P
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.