36:
593:
improves efficiency by reducing the number of states in the search. For example, a state in the Pacman space includes information about the direction Pacman is facing (up, down, left, or right). Since it does not cost anything to change directions in Pacman, search states for Pacman would not include this information and reduce the size of the search space by a factor of 4, one for each direction Pacman could be facing.
100:
645:
308:
301:
294:
287:
280:
273:
266:
259:
253:
444:
For example, the Vacuum World has a branching factor of 4, as the vacuum cleaner can end up in 1 of 4 adjacent squares after moving (assuming it cannot stay in the same square nor move diagonally). The arcs of Vacuum World are bidirectional, since any square can be reached from any adjacent square,
592:
A search state is a compressed representation of a world state in a state space, and is used for exploration. Search states are used because a state space often encodes more information than is necessary to explore the space. Compressing each world state to only information needed for exploration
546:, where the effective state space is the set of positions that can be reached by game-legal moves. This is far smaller than the set of positions that can be achieved by placing combinations of the available chess pieces directly on the board.
541:
This is significantly greater than the number of legal configurations of the queens, 92. In many games the effective state space is small compared to all reachable/legal states. This property is also observed in
536:
472:, the state space can be calculated by counting all possible ways to place 8 pieces on an 8x8 chessboard. This is the same as choosing 8 positions without replacement from a set of 64, or
625:
These methods do not extend naturally to exploring continuous state spaces. Exploring a continuous state space in search of a given goal state is equivalent to optimizing an arbitrary
123:
representing the set of all possible configurations of a "system". It is a useful abstraction for reasoning about the behavior of a given system and is widely used in the fields of
138:
Vacuum World has a discrete finite state space in which there are a limited set of configurations that the vacuum and dirt can be in. A "counter" system, where states are the
890:
864:
842:
57:
703:
79:
584:, for example, contains a goal state whenever all food pellets have been eaten, and is explored by moving Pacman around the board.
920:
778:
93:
650:
142:
starting at 1 and are incremented over time has an infinite discrete state space. The angular position of an undamped
50:
44:
580:
Exploring a state space is the process of enumerating possible states in search of a goal state. The state space of
478:
925:
601:
Standard search algorithms are effective in exploring discrete state spaces. The following algorithms exhibit both
713:
630:
465:
445:
and the state space is not a tree since it is possible to enter a loop by moving between any 4 adjacent squares.
61:
930:
688:
693:
124:
562:) infinite size, such as the state space of the time-dependent "counter" system, similar to the system in
104:
456:
The size of the state space for a given system is the number of possible configurations of the space.
683:
609:
602:
626:
619:
614:
555:
469:
718:
575:
838:
698:
665:
170:
17:
708:
566:
defining the number of customers in a line, which would have state space {0, 1, 2, 3, ...}.
417:
155:
112:
662:
for information about phase state (like continuous state space) in physics and mathematics.
677:
671:
563:
139:
464:
If the size of the state space is finite, calculating the size of the state space is a
120:
914:
728:
559:
436:
424:
832:
749:
806:
723:
659:
644:
135:
128:
680:
for information about state space with a dynamical systems model of cognition.
640:
448:
State spaces can be either infinite or finite, and discrete or continuous.
158:
as a simple model of machines. Formally, a state space can be defined as a
99:
143:
834:
State-space search: algorithms, complexity, extensions, and applications
581:
186:
543:
159:
98:
558:
and are therefore infinite. Discrete state spaces can also have (
554:
All continuous state spaces can be described by a corresponding
29:
407:
A valid state in the state space of the eight queens puzzle
674:
theory, which relies on the state space of game outcomes
146:
is a continuous (and therefore infinite) state space.
481:
530:
92:"State space" redirects here. For other uses, see
668:for information about state space in probability.
498:
485:
779:"Infinite States and Infinite State Transitions"
213:
531:{\displaystyle {\binom {64}{8}}=4,426,165,368}
8:
605:and optimality in searching a state space.
412:A state space has some common properties:
497:
484:
482:
480:
80:Learn how and when to remove this message
800:
798:
796:
772:
770:
43:This article includes a list of general
858:
856:
854:
740:
307:
300:
293:
286:
279:
272:
265:
258:
179:is a set of arcs connecting the states
27:Set of all possible values of a system
249:
7:
704:Glossary of artificial intelligence
629:which is not always possible, see
489:
49:it lacks sufficient corresponding
25:
678:Cognitive Model#Dynamical systems
423:structure of the space, see also
807:"The idea of a dynamical system"
643:
306:
299:
292:
285:
278:
271:
264:
257:
251:
34:
865:"Lecture 2: Uninformed Search"
203:that contains the goal states.
18:State space (dynamical system)
1:
895:UC Berkeley CS188 Intro to AI
869:UC Berkeley CS188 Intro to AI
468:problem. For example, in the
891:"Lecture 3: Informed Search"
781:. Carnegie Mellon University
94:State space (disambiguation)
651:Computer programming portal
154:State spaces are useful in
947:
573:
193:that contains start states
91:
714:Mathematical optimization
631:mathematical optimization
107:with a finite state space
750:"State space definition"
689:State (computer science)
199:is a nonempty subset of
831:Zhang, Weixong (1999).
694:Artificial intelligence
125:artificial intelligence
64:more precise citations.
532:
430:directionality of arcs
108:
921:Models of computation
533:
105:shortest path problem
102:
684:State space planning
610:Breadth-First Search
479:
777:Papernick, Norman.
627:continuous function
620:Uniform Cost Search
556:continuous function
470:Eight queens puzzle
719:Multi-agent system
576:state space search
528:
416:complexity, where
134:For instance, the
109:
926:Dynamical systems
844:978-0-387-98832-0
699:Dynamical systems
666:Probability space
496:
405:
404:
90:
89:
82:
16:(Redirected from
938:
906:
905:
903:
901:
889:Abbeel, Pieter.
886:
880:
879:
877:
875:
863:Abbeel, Pieter.
860:
849:
848:
828:
822:
821:
819:
817:
802:
791:
790:
788:
786:
774:
765:
764:
762:
760:
745:
709:Machine learning
653:
648:
647:
537:
535:
534:
529:
503:
502:
501:
488:
418:branching factor
310:
309:
303:
302:
296:
295:
289:
288:
282:
281:
275:
274:
268:
267:
261:
260:
255:
254:
214:
156:computer science
113:computer science
103:Vacuum World, a
85:
78:
74:
71:
65:
60:this article by
51:inline citations
38:
37:
30:
21:
946:
945:
941:
940:
939:
937:
936:
935:
931:Reconfiguration
911:
910:
909:
899:
897:
888:
887:
883:
873:
871:
862:
861:
852:
845:
830:
829:
825:
815:
813:
805:Nykamp, Duane.
804:
803:
794:
784:
782:
776:
775:
768:
758:
756:
748:Nykamp, Duane.
747:
746:
742:
738:
733:
672:Game complexity
649:
642:
639:
599:
590:
578:
572:
564:queueing theory
552:
483:
477:
476:
462:
454:
410:
409:
408:
312:
311:
304:
297:
290:
283:
276:
269:
262:
252:
210:
152:
140:natural numbers
97:
86:
75:
69:
66:
56:Please help to
55:
39:
35:
28:
23:
22:
15:
12:
11:
5:
944:
942:
934:
933:
928:
923:
913:
912:
908:
907:
881:
850:
843:
823:
792:
766:
739:
737:
734:
732:
731:
726:
721:
716:
711:
706:
701:
696:
691:
686:
681:
675:
669:
663:
656:
655:
654:
638:
635:
623:
622:
617:
612:
598:
595:
589:
586:
574:Main article:
571:
568:
551:
548:
539:
538:
527:
524:
521:
518:
515:
512:
509:
506:
500:
495:
492:
487:
461:
458:
453:
450:
442:
441:
440:
439:
434:
431:
421:
406:
403:
402:
400:
397:
394:
391:
388:
385:
382:
379:
376:
373:
372:
369:
365:
364:
361:
357:
356:
353:
349:
348:
345:
341:
340:
337:
333:
332:
329:
325:
324:
321:
317:
316:
313:
305:
298:
291:
284:
277:
270:
263:
256:
250:
248:
244:
243:
241:
238:
235:
232:
229:
226:
223:
220:
217:
212:
211:
209:
206:
205:
204:
194:
185:is a nonempty
180:
174:
151:
148:
121:discrete space
88:
87:
42:
40:
33:
26:
24:
14:
13:
10:
9:
6:
4:
3:
2:
943:
932:
929:
927:
924:
922:
919:
918:
916:
896:
892:
885:
882:
870:
866:
859:
857:
855:
851:
846:
840:
836:
835:
827:
824:
812:
811:Math Insights
808:
801:
799:
797:
793:
780:
773:
771:
767:
755:
754:Math Insights
751:
744:
741:
735:
730:
729:Combinatorics
727:
725:
722:
720:
717:
715:
712:
710:
707:
705:
702:
700:
697:
695:
692:
690:
687:
685:
682:
679:
676:
673:
670:
667:
664:
661:
658:
657:
652:
646:
641:
636:
634:
632:
628:
621:
618:
616:
613:
611:
608:
607:
606:
604:
596:
594:
588:Search States
587:
585:
583:
577:
569:
567:
565:
561:
557:
549:
547:
545:
525:
522:
519:
516:
513:
510:
507:
504:
493:
490:
475:
474:
473:
471:
467:
466:combinatorial
459:
457:
451:
449:
446:
438:
435:
432:
429:
428:
426:
422:
419:
415:
414:
413:
401:
398:
395:
392:
389:
386:
383:
380:
377:
375:
374:
370:
367:
366:
362:
359:
358:
354:
351:
350:
346:
343:
342:
338:
335:
334:
330:
327:
326:
322:
319:
318:
314:
246:
245:
242:
239:
236:
233:
230:
227:
224:
221:
218:
216:
215:
207:
202:
198:
195:
192:
188:
184:
181:
178:
175:
172:
168:
165:
164:
163:
161:
157:
149:
147:
145:
141:
137:
132:
130:
126:
122:
118:
114:
106:
101:
95:
84:
81:
73:
70:February 2012
63:
59:
53:
52:
46:
41:
32:
31:
19:
898:. Retrieved
894:
884:
872:. Retrieved
868:
837:. Springer.
833:
826:
814:. Retrieved
810:
783:. Retrieved
757:. Retrieved
753:
743:
624:
603:completeness
600:
591:
579:
553:
540:
463:
455:
447:
443:
437:rooted graph
425:graph theory
420:is important
411:
200:
196:
190:
182:
176:
166:
153:
133:
116:
110:
76:
67:
48:
900:12 November
816:12 November
785:12 November
759:17 November
724:Game theory
660:Phase space
570:Exploration
136:toy problem
129:game theory
117:state space
62:introducing
915:Categories
874:30 October
736:References
208:Properties
150:Definition
45:references
615:A* Search
560:countably
173:of states
637:See also
550:Infinite
144:pendulum
597:Methods
162:where:
58:improve
841:
582:Pacman
460:Finite
187:subset
47:, but
544:Chess
169:is a
160:tuple
119:is a
902:2019
876:2019
839:ISBN
818:2019
787:2019
761:2019
452:Size
433:tree
127:and
115:, a
526:368
520:165
514:426
189:of
171:set
111:In
917::
893:.
867:.
853:^
809:.
795:^
769:^
752:.
633:.
491:64
427::
131:.
904:.
878:.
847:.
820:.
789:.
763:.
523:,
517:,
511:,
508:4
505:=
499:)
494:8
486:(
399:h
396:g
393:f
390:e
387:d
384:c
381:b
378:a
371:1
368:1
363:2
360:2
355:3
352:3
347:4
344:4
339:5
336:5
331:6
328:6
323:7
320:7
315:8
247:8
240:h
237:g
234:f
231:e
228:d
225:c
222:b
219:a
201:N
197:G
191:N
183:S
177:A
167:N
96:.
83:)
77:(
72:)
68:(
54:.
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
