66:
390:
operators also exist: Action 1, lay-tablecloth, Action 2, Put-out (plates), Action 3, Put-out (silverware), and Action 4, Put-out (glasses). However, a threat arises if Action 2, 3, or 4 comes before Action 1. This threat is that the precondition to the start of the algorithm will be unsatisfied as the table will no longer be clear. Thus, constraints exist that must be added to the algorithm that force
Actions 2, 3, and 4 to come after Action 1. Once these steps are completed, the algorithm will finish and the goal will have been completed.
916:
25:
136:
226:
traversed in any order, after which the end is reachable. In a partial-order plan, ordering between these obstacles is specified only when needed. The bridge must be traversed first. Second, either the see-saw or swing-set can be traversed. Third, the remaining obstacle can be traversed. Then the end can be traversed. Partial-order planning relies upon the
493:
implications. When coding a robot to do a certain task, the creator needs to take into account how much energy is needed. Though a partial-order plan may be quicker it may not be worth the energy cost for the robot. The creator must be aware of and weigh these two options to build an efficient robot.
389:
of the algorithm is constrained between its start and finish. The algorithm starts, producing the initial state and finishes when all parts of the goal have been achieved. In the setting a table example, two types of actions exist that must be addressed: the put-out and lay operators. Four unsolved
376:
The initial state is the starting conditions, and can be thought of as the preconditions to the task at hand. For a task of setting the table, the initial state could be a clear table. The goal is simply the final action that needs to be accomplished, for example setting the table. The operators of
225:
Consider the following situation: a person must travel from the start to the end of an obstacle course. The course is composed of a bridge, a see-saw, and a swing-set. The bridge must be traversed before the see-saw and swing-set are reachable. Once reachable, the see-saw and swing-set can be
468:. The determining factor that makes a subgoal trivially or laboriously serializable is the search space of different plans. They found that partial-order planning is more adept at finding the quickest path, and is therefore the more efficient of these two main types of planning.
440:, in which actions are sequenced all at once and for the entirety of the task at hand. The question arises when one has two competing processes, which one is better? Anthony Barret and Daniel Weld have argued in their 1993 book, that partial-order planning is superior to
213:
that maintains a partial ordering between actions and only commits ordering between actions when forced to, that is, ordering of actions is partial. Also this planning doesn't specify which action will come out first when two actions are processed. By contrast,
427:
Partial-order planning algorithms are known for being both sound and complete, with sound being defined as the total ordering of the algorithm, and complete being defined as the capability to find a solution, given that a solution does in fact exist.
488:
One drawback of this type of planning system is that it requires a lot more computational power for each node. This higher per-node cost occurs because the algorithm for partial-order planning is more complex than others. This has important
372:
where the set of possible partial-order plans is the search space. The initial state would be the plan with the open preconditions equal to the goal conditions. The final state would be any plan with no open preconditions, i.e. a solution.
246:
is a plan which specifies all actions that must be taken, but only specifies the order between actions when needed. It is the result of a partial-order planner. A partial-order plan consists of four components:
445:
300:
of a partial order plan is a total order plan derived from the particular partial order plan; in other words, both order plans consist of the same actions, with the order in the linearization being a
480:. Using this type of incremental planning system solves this problem quickly and efficiently. This was a result of partial-order planning that solidified its place as an efficient planning system.
581:
516:
Kambhampati, S., Knoblock, C.A., Yang, Q. (1994). Planning as
Refinement Search: A Unified Framework for Evaluating Design Tradeoffs in Partial-Order Planning. Elsevier Science.
531:
Barrett, A., and Weld, D. (1993). Partial-Order
Planning: Evaluating Possible Efficiency Gains. University of Washington: Department of Computer Science and Engineering. Notes
377:
the algorithm are the actions by which the task is accomplished. For this example there may be two operators: lay (tablecloth), and place (glasses, plates, and silverware).
465:
461:
457:
449:
146:
218:
maintains a total ordering between all actions at every stage of planning. Given a problem in which some sequence of actions is needed to achieve a goal, a
521:
Poole, D., Mackworth, A. (2010). Partial-Order
Planning in Artificial Intelligence Foundations of Computational Agents. Cambridge University Press.
460:
facilitates a planner’s ability to perform quickly when dealing with goals that contain subgoals. Planners perform more slowly when dealing with
157:
95:
588:
353:
which will construct a partial-order plan and search for a solution. The input is the problem description, consisting of descriptions of the
386:
290:
To keep the possible orders of the actions as open as possible, the set of order conditions and causal links must be as small as possible.
399:
976:
537:
Simmons, Reid. (2001). “Planning, Execution & Learning 1. Partial Order
Planning.” Carnegie Mellon University. Pittsburgh. Notes.
541:
329:
This is a partial plan because the order for finding eggs, flour and milk is not specified, the agent can wander around the store
957:
38:
981:
597:
402:
that threaten to break connected actions, thus potentially destroying the entire plan. There are two ways to resolve threats:
546:
530:
865:
526:
Dyer, C. R. “Partial-Order
Planning (Chapter 11).”(2003) CS 540. University of Wisconsin-Madison. Madison, Wisconsin.
193:
175:
117:
52:
88:
855:
690:
845:
761:
675:
574:
950:
741:
718:
670:
44:
398:
As seen in the algorithm presented above, partial-order planning can encounter certain threats, meaning
222:
specifies all actions that must be taken, but specifies an ordering between actions only where needed.
520:
888:
698:
78:
536:
802:
515:
82:
74:
150:
that states a
Knowledge editor's personal feelings or presents an original argument about a topic.
923:
832:
542:
http://pdf.aminer.org/000/744/302/partial_order_planning_evaluating_possible_efficiency_gains.pdf
490:
931:
275:. It specifies which actions meet which preconditions of other actions. Alternatively, a set of
153:
943:
840:
817:
797:
703:
99:
766:
647:
632:
622:
286:. It specifies which preconditions are not fulfilled by any action in the partial-order plan.
898:
878:
708:
617:
547:
http://pdf.aminer.org/000/037/660/decomposition_and_causality_in_partial_order_planning.pdf
453:
448:, in which they found that partial-order planning performs better because it produces more
441:
437:
8:
680:
601:
566:
561:
787:
210:
525:
893:
850:
822:
733:
713:
612:
509:
330:
637:
627:
417:
406:
369:
350:
301:
873:
642:
477:
927:
970:
657:
268:
for the actions. It specifies the conditions about the order of some actions.
264:
551:
333:
accumulating all the items on its shopping list until the list is complete.
723:
444:, as it is faster and thus more efficient. They tested this theory using
556:
346:
915:
421:
411:
807:
751:
476:
Partial-order plans are known to easily and optimally solve the
293:
A plan is a solution if the set of open preconditions is empty.
782:
424:
orders the possible threat before the connection it threatens.
420:
orders the possible threat after the connection it threatens.
812:
792:
756:
665:
746:
147:
personal reflection, personal essay, or argumentative essay
596:
483:
431:
304:
of the partial order in the original partial order plan.
562:
http://www.grastien.net/ban/teaching/06-planning4.pdf
312:For example, a plan for baking a cake might start:
968:
87:but its sources remain unclear because it lacks
951:
582:
510:An Introduction To Least Commitment Planning
53:Learn how and when to remove these messages
958:
944:
589:
575:
504:Artificial Intelligence: A Modern Approach
436:Partial-order planning is the opposite of
552:http://dl.acm.org/citation.cfm?id=1867345
194:Learn how and when to remove this message
176:Learn how and when to remove this message
118:Learn how and when to remove this message
336:
484:Disadvantages to partial-order planning
969:
471:
446:Korf’s taxonomy of subgoal collections
432:Partial-order vs. total-order planning
570:
233:
910:
368:The problem can be interpreted as a
129:
59:
18:
13:
557:http://arxiv.org/pdf/1106.0249.pdf
14:
993:
977:Automated planning and scheduling
279:between the variables in actions.
34:This article has multiple issues.
914:
134:
64:
23:
506:by Stuart Russell, Peter Norvig
42:or discuss these issues on the
1:
982:Artificial intelligence stubs
497:
380:
319:get eggs; get flour; get milk
228:principle of least commitment
930:. You can help Knowledge by
846:Constraint logic programming
762:Knowledge Interchange Format
719:Procedural reasoning systems
676:Expert systems for mortgages
671:Connectionist expert systems
7:
742:Attempto Controlled English
16:Topic in automated planning
10:
998:
909:
393:
307:
889:Preference-based planning
864:
831:
775:
732:
689:
656:
608:
598:Knowledge representation
466:nonserializable subgoals
462:laboriously serializable
73:This article includes a
924:artificial intelligence
833:Constraint satisfaction
491:artificial intelligence
458:Trivial serializability
450:trivial serializability
102:more precise citations.
926:-related article is a
884:Partial-order planning
841:Constraint programming
207:Partial-order planning
156:by rewriting it in an
767:Web Ontology Language
709:Deductive classifiers
648:Knowledge engineering
633:Model-based reasoning
623:Commonsense reasoning
343:partial-order planner
337:Partial-order planner
230:for its efficiency.
899:State space planning
879:Multi-agent planning
681:Legal expert systems
618:Case-based reasoning
454:total-order planning
442:total-order planning
438:total-order planning
216:total-order planning
472:The Sussman anomaly
866:Automated planning
734:Ontology languages
704:Constraint solvers
284:open preconditions
240:partial-order plan
234:Partial-order plan
220:partial-order plan
211:automated planning
209:is an approach to
158:encyclopedic style
145:is written like a
75:list of references
939:
938:
907:
906:
894:Reactive planning
851:Local consistency
691:Reasoning systems
638:Inference engines
613:Backward chaining
325:go to the kitchen
322:pay for all goods
204:
203:
196:
186:
185:
178:
128:
127:
120:
57:
989:
960:
953:
946:
918:
911:
643:Proof assistants
628:Forward chaining
591:
584:
577:
568:
567:
302:linear extension
199:
192:
181:
174:
170:
167:
161:
138:
137:
130:
123:
116:
112:
109:
103:
98:this article by
89:inline citations
68:
67:
60:
49:
27:
26:
19:
997:
996:
992:
991:
990:
988:
987:
986:
967:
966:
965:
964:
908:
903:
874:Motion planning
860:
827:
776:Theorem provers
771:
728:
699:Theorem provers
685:
652:
604:
595:
500:
486:
478:Sussman anomaly
474:
434:
396:
383:
339:
316:go to the store
310:
255:(also known as
236:
200:
189:
188:
187:
182:
171:
165:
162:
154:help improve it
151:
139:
135:
124:
113:
107:
104:
93:
79:related reading
69:
65:
28:
24:
17:
12:
11:
5:
995:
985:
984:
979:
963:
962:
955:
948:
940:
937:
936:
919:
905:
904:
902:
901:
896:
891:
886:
881:
876:
870:
868:
862:
861:
859:
858:
853:
848:
843:
837:
835:
829:
828:
826:
825:
820:
815:
810:
805:
800:
795:
790:
785:
779:
777:
773:
772:
770:
769:
764:
759:
754:
749:
744:
738:
736:
730:
729:
727:
726:
721:
716:
714:Logic programs
711:
706:
701:
695:
693:
687:
686:
684:
683:
678:
673:
668:
662:
660:
658:Expert systems
654:
653:
651:
650:
645:
640:
635:
630:
625:
620:
615:
609:
606:
605:
594:
593:
586:
579:
571:
565:
564:
559:
554:
549:
544:
539:
534:
528:
523:
518:
513:
512:by Daniel Weld
507:
499:
496:
485:
482:
473:
470:
433:
430:
415:
414:
409:
395:
392:
382:
379:
370:search problem
338:
335:
327:
326:
323:
320:
317:
309:
306:
288:
287:
280:
269:
260:
235:
232:
202:
201:
184:
183:
142:
140:
133:
126:
125:
83:external links
72:
70:
63:
58:
32:
31:
29:
22:
15:
9:
6:
4:
3:
2:
994:
983:
980:
978:
975:
974:
972:
961:
956:
954:
949:
947:
942:
941:
935:
933:
929:
925:
920:
917:
913:
912:
900:
897:
895:
892:
890:
887:
885:
882:
880:
877:
875:
872:
871:
869:
867:
863:
857:
854:
852:
849:
847:
844:
842:
839:
838:
836:
834:
830:
824:
821:
819:
816:
814:
811:
809:
806:
804:
801:
799:
796:
794:
791:
789:
786:
784:
781:
780:
778:
774:
768:
765:
763:
760:
758:
755:
753:
750:
748:
745:
743:
740:
739:
737:
735:
731:
725:
722:
720:
717:
715:
712:
710:
707:
705:
702:
700:
697:
696:
694:
692:
688:
682:
679:
677:
674:
672:
669:
667:
664:
663:
661:
659:
655:
649:
646:
644:
641:
639:
636:
634:
631:
629:
626:
624:
621:
619:
616:
614:
611:
610:
607:
603:
599:
592:
587:
585:
580:
578:
573:
572:
569:
563:
560:
558:
555:
553:
550:
548:
545:
543:
540:
538:
535:
532:
529:
527:
524:
522:
519:
517:
514:
511:
508:
505:
502:
501:
495:
492:
481:
479:
469:
467:
463:
459:
455:
451:
447:
443:
439:
429:
425:
423:
419:
413:
410:
408:
405:
404:
403:
401:
391:
388:
378:
374:
371:
366:
364:
361:and possible
360:
356:
355:initial state
352:
348:
344:
334:
332:
324:
321:
318:
315:
314:
313:
305:
303:
299:
298:linearization
294:
291:
285:
281:
278:
274:
270:
267:
266:
265:partial order
261:
258:
254:
250:
249:
248:
245:
241:
231:
229:
223:
221:
217:
212:
208:
198:
195:
180:
177:
169:
159:
155:
149:
148:
143:This article
141:
132:
131:
122:
119:
111:
101:
97:
91:
90:
84:
80:
76:
71:
62:
61:
56:
54:
47:
46:
41:
40:
35:
30:
21:
20:
932:expanding it
921:
883:
724:Rule engines
503:
487:
475:
435:
426:
416:
397:
384:
375:
367:
362:
358:
354:
342:
340:
328:
311:
297:
295:
292:
289:
283:
276:
273:causal links
272:
263:
256:
252:
244:partial plan
243:
239:
237:
227:
224:
219:
215:
206:
205:
190:
172:
163:
144:
114:
105:
94:Please help
86:
50:
43:
37:
36:Please help
33:
856:SMT solvers
100:introducing
971:Categories
498:References
387:plan space
381:Plan space
331:reactively
166:April 2014
39:improve it
602:reasoning
418:Promotion
407:Promotion
400:orderings
347:algorithm
282:A set of
271:A set of
257:operators
251:A set of
108:June 2013
45:talk page
422:Demotion
412:Demotion
277:bindings
808:Prover9
803:Paradox
752:F-logic
394:Threats
363:actions
351:program
308:Example
253:actions
152:Please
96:improve
783:CARINE
357:, the
345:is an
922:This
813:SPASS
798:Otter
793:Nqthm
757:FO(.)
666:CLIPS
452:than
81:, or
928:stub
747:CycL
600:and
385:The
359:goal
818:TPS
464:or
349:or
242:or
973::
823:Z3
456:.
365:.
341:A
296:A
262:A
259:).
238:A
85:,
77:,
48:.
959:e
952:t
945:v
934:.
788:E
590:e
583:t
576:v
533:.
197:)
191:(
179:)
173:(
168:)
164:(
160:.
121:)
115:(
110:)
106:(
92:.
55:)
51:(
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.