Searching Continuous State Spaces E ectively Using Critical Points.pdfVIP

Searching Continuous State Spaces Eectively Using Critical Points Keywords: search or optimization, multi-agent simulation Tracking Numb er: A396 Abstract and corresp ondingly the state space large, the solution to a given problem will involve a deep er search through Many arti cial intelligence techniques rely on the no- the space than if the state space were smaller. If the tion of a \state as an abstraction of the actual state of op erators b ecome to o abstract, however, they start to the world, and an \op erator as an abstraction of the actions that take you from one state to the next. Much gloss over all the interactions b etween op erators and of the art of problem solving dep ends on cho osing the the world that made the problem worth solving in the appropriate set of states and op erators. However, in rst place. realistic, and therefore dynamic and continuous search Consider path planning as an example: Assume a spaces, nding the right level of abstraction can b e dif- rob ot on a 2D plane has a move op erator that will cult. If to o many states are chosen, the search space allow it to move a certain distance d . If d is chosen to o b ecomes intractable; if to o few are chosen, imp ortant small, the problem quickly b ecomes intractable b ecause interactions b etween op erators might b e missed. If the there are to o many p ossible paths to b e considered. If state b oundaries are not at the right place, the results d is to o large|larger than some of the obstacles on the