Методы поиска решений в больших пространствах состояний

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

Реальная проблемная область характеризуется зачастую нас­только большим пространством состояний, что бывает очень труд­но практически организовать поиск методами перебора. Однако часто требуется найти все возможные решения в проблемной об­ласти. Выходом в таких случаях является использование метода порождения и проверки. Этот метод можно применять, если про­странство является факторизуемым, т. е. возможно разбиение его на достаточно независимые подпространства с характерными не­полными решениями. Характерное неполное решение позволяет судить о перспективности поиска полных решений в этом подпро­странстве.

Сущность метода заключается в том, что генератор, настроен­ный на проблемную область, порождает ряд характерных непол­ных решений, соответствующих описаниям различных подпрост­ранств. Осуществляется проверка неполных решений с помощью специальных оценочных процедур, и если решение признается не­допустимым, то из дальнейшего рассмотрения исключается целый класс порождаемых им полных решений данного подпространст­ва. В результате отсечения на ранней стадии поиска определен­ных ветвей поиска без порождения и проверки узлов состояний значительно сокращается число состояний, подлежащих анализу. Если неполное решение признается перспективным, то на его ос­нове в соответствующем подпространстве вырабатываются пол­ные решения на более глубоких уровнях иерархии описания пространства и определяется, являются ли получаемые решения це­левыми.

Иерархическая процедура реализации метода порождения и проверки позволяет применять правила отсечения вариантов на ранних этапах порождения. Использование метода порождения и проверки в факторизованном пространстве бывает затруднено из-за того, что часто отсутствуют достоверные способы оценки характерных неполных решений, т. е. не удается на основе не­полных решений делать выводы о реализуемости полных решений. Здесь невозможно с большой степенью уверенности отсечь неперс­пективные ветви на начальной стадии поиска. Всегда есть риск исключить часть пространства состояний, представившегося бес­перспективным, но вполне способным в дальнейшей обработке при появлении дополнительной информации обеспечить решение. Такие ситуации характерны для задач перспективного планирова­ния и проектирования. Кроме того, не всегда необходимо искать все возможные решения, а достаточно иметь какое-либо приемле­мое.

В этих случаях производят абстрагирование пространства ре­шений. Решение задачи осуществляется на разных уровнях абст­ракции путем последовательного уточнения его на этих уровнях описания пространства. Абстракция дополнительно выявляет важ­ные детали, характеризующие задачу. Основная задача редуциру­ется на фиксированную совокупность описаний подзадач. В прос­тых случаях в абстрактном пространстве достаточно одного раз­биения, используемого для разных задач данной проблемной об­ласти.

Если проблемная область содержит большое число задач, то не удается все задачи решить на определенном варианте редук­ции пространства поиска. В качестве примера можно привести задачу планирования действий робота по перемещению в прост­ранстве и манипулированию объектами. В этих случаях абстрак­ция должна отразить переменную структуру плана действий.

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

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

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

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

Выше были рассмотрены лишь основные методы поиска в боль­ших пространствах. При практической реализации систем ИИ возможно появление новых методов поиска решений и построения рассуждений, часто ориентированных на определенные классы реальных проблемных областей с учетом их специфики.