Главная arrow книги arrow Копия Глава 3. Решение проблем посредством поиска arrow Реальные задачи
Реальные задачи

Задача управления навигацией робота представляет собой обобщение описанной выше задачи поиска маршрута. В этой задаче вместо дискретного множества маршрутов рассматривается ситуация, в которой робот может перемещаться в непрерывном пространстве с бесконечным (в принципе) множеством возможных действий и состояний. Если требуется обеспечить циклическое перемещение робота по плоской поверхности, то пространство фактически может рассматриваться как двухмерное, а если робот оборудован верхними и нижними конечностями или колесами, которыми также необходимо управлять, то пространство поиска становится многомерным. Даже для того чтобы сделать это пространство поиска конечным, требуются весьма развитые методы. Некоторые из этих методов рассматриваются в главе 25. Изначальная сложность задачи усугубляется тем, что при управлении реальными роботами необходимо учитывать ошибки в показаниях датчиков, а также отклонения в работе двигательных средств управления.

Решение задачи автоматического упорядочения сборки сложных объектов роботом было впервые продемонстрировано на примере робота Freddy [1044]. С тех пор прогресс в этой области происходил медленно, но уверенно, и в настоящее время достигнуто такое положение, что стала экономически выгодной сборка таких неординарных объектов, как электродвигатели. В задачах сборки цель состоит в определении последовательности, в которой должны быть собраны детали некоторого объекта. Если выбрана неправильная последовательность, то в дальнейшем нельзя будет найти способ добавления некоторой детали к этой последовательности без отменены определенной части уже выполненной работы. Проверка возможности выполнения некоторого этапа в последовательности представляет собой сложную геометрическую задачу поиска, тесно связанную с задачей навигации робота. Поэтому одним из дорогостоящих этапов решения задачи упорядочения сборки является

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

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