Материал: Элементы искусственного интеллекта в робототехнике. Ефремов Д.А

X₁₁ X₁₂ X₁₃ X₁₄ X₁₅

X₂₁

X_y1 X_y2 X_т1 X_y3 X_т3

X_т2

Рис. 5. Представление поиска в пространстве состояний в виде графа

При поиске в глубину раскрытие начинается от одной из вершин нулевого слоя и далее по одному из направления графа (например, (1), (2), (3)). По достижении нижнего слоя осуществляется возврат до вершины, к которой можно приме­нить несколько операторов. Далее раскрытие выполняется по новому направлению (возврат с (3) на (2) и на (4)). После раскрытия всех дочерних вершин одного направления выполня­е­тся возврат в нулевой слой и реализуется поиск по другому направлению, исходящему из начальной вершины ((1) – (5)). Может применяться смена направлений, т.е. по ходу поиска поиск в глубину может сменяться поиском в ширину.

2.6. Поиск решения методом редукции

Этот метод применяется в тех случаях, когда простран­ство признаков можно представить в виде подзадач.

Подзадача – часть графа, итоговые вершины которого можно считать частными решениями.

18

Частные решения могут быть очевидными, тупиковыми, или решаемыми. I вид соответствует солевым вершинам гра­фа; II – терминальным; III – совокупности вершин, к которым можно применять операторы. При редукции граф простран­ства состояний заменяется графом подзадач, имеющих очевид­ное решение. При построении графа подзадач применяются понятия конъюнктивных и дизъюнктивных вершин. Эти поня­тия применяются к вершинам, из которых исходят не менее двух на­пра­влений поиска. Конъюнктивной вершиной является

такая, для разрешения которой необходимо разрешение (поиск оче­видного решения) по всем направлениям. Для дизъюнктивных вершин достаточно одного очевидного решения по одному из направлений.

При редукции могут применяться поиск в глубину и ширину, как и в пространстве состояний.

1(!) 2(7)

3(2) 4(5) 5(8)

6(3) 7(4) 8(6) 9(9) 10(10)

Рис. 6. Варианты направлений поиска в пространстве состояний

Рассмотренные выше методы поиска являются “слепы­ми”, т.к. они не отдают приоритета ни одной вершине нулево-

19­

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

Рис. 7. Факторизованные подпространства в пространстве состояний

ПП – полное пространство (пространство признаков);

ПП1-ПП3 – факторизованное подпространство;

ЧР1-ЧР3 – частные решения;

ПР – полное решение.

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

20

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

2.8. Поиск в фиксированном множестве пространств

Рис.8. Фиксированное множество пространств

2.9. Поиск в изменяющемся множестве пространств (метод нисходящего уточнения)

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

На рисунке 9 представлена рабочая зона промышленного робота ПР, задачей которого является достижение целевого по­ло­жения Ц.

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

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

ности исходных признаков могут использоваться только осно-

вные, а часть может отбрасываться по определенному крите-

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

22

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

Р ис. 9. Рабочая зона робота для иллюстрации метода нисходящего уточнения.

//// - препятствия, линии – пере­городки

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

2.7. Поиск решения во множестве факторизованных пространств

Факторизованным пространством называется подпро- странство во множестве признаков, которые имеют частные решения (Рис. 7). Это означает, что во множестве промежуточных вершин графа поиска можно выделить вершины, кото-

рые можно квалифицировать как ре­ше­ния.