Рис. 4.13. Примеры ситуаций, характеризующихся бесконечным значением коэффициента конкурентоспособности: два пространства состояний, которые способны завести агента, выполняющего поиск в оперативном режиме, в тупик; любой конкретный агент потерпит неудачу, по меньшей мере, в одном из этих пространств (а); двухмерная среда, которая может вынудить агента, выполняющего поиск в оперативном режиме, следовать по маршруту к цели, который может оказаться сколь угодно неэффективным; какой бы выбор ни сделал агент, противник блокирует его маршрут еще одной длинной, тонкой стеной, чтобы путь, по которому следует агент, стал намного длиннее по сравнению с наилучшим возможным путем (б)

Тупики представляют собой одну из реальных сложностей в области исследований, проводимых с помощью робота, поскольку лестницы, пандусы, обрывы и многие другие формы естественного ландшафта создают предпосылки для необратимых действий. Для того чтобы добиться прогресса, мы будем предполагать, что данное пространство состояний является безопасно исследуемым, т.е. что некоторые целевые состояния достижимы из каждого достижимого состояния. Пространства состояний с обратимыми действиями, такие как лабиринты и задачи игры в восемь, могут рассматриваться как неориентированные графы и, вполне очевидно, являются безопасно исследуемыми.

Но даже в безопасно исследуемых вариантах среды нельзя гарантировать достижение какого-либо ограниченного значения коэффициента конкурентоспособности, если в них имеются маршруты с неограниченной стоимостью. Это утверждение легко доказать применительно к вариантам среды с необратимыми действиями, но фактически оно остается истинным также и для обратимого случая (см. рис. 4.13, б). По этой причине обычно принято описывать производительность алгоритмов поиска в оперативном режиме с учетом размеров всего пространства состояний, а не только глубины самой поверхностной цели.