Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Робототехніка, системи штучного інтелекту
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
ІКТА
Факультет:
Не вказано
Кафедра:
Кафедра ЕОМ
Інформація про роботу
Рік:
2006
Тип роботи:
Курсовий проект
Предмет:
Методи, алгоритми та засоби цифрової обробки сигналів та зображень
Група:
СКС
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти і науки України
Національний університет «Львівська політехніка»
ІКТА
Кафедра ЕОМ
Курсовий проект
з дисципліни
«Методи, алгоритми та засоби цифрової обробки сигналів та зображень»
на тему:
«Робототехніка, системи штучного інтелекту»
Зміст
Вступ
3
1. Теоретичний розділ
4
1.1. Основні поняття і визначення
4
1.2 Область застосування
4
1.3. Історія розвитку систем штучного інтелекту
5
2. Методи вирішення задач
9
3. Перспективи і тенденції розвитку штучного інтелекту
16
Висновки
22
Література
23
Вступ
В останні роки цифрова обробка сигналів та зображень (ЦОСЗ) суттєво впливає на такі ключові технологічні галузі, як телекомунікації, цифрове телебачення і засоби інформації, біомедицина і цифровий звукозапис. Сьогодні ЦОСЗ є основою багатьох новітніх видів цифрових розробок і різних застосувань в інформаційному середовищі (наприклад. цифровий мобільний зв'язок, цифрові відеокамери, телебачення і системи звукозапису). Поряд з тим ЦОСЗ ширше впроваджується і в класичні галузі застосування (радіолокація, геофізика, опрацювання мовних сигналів, сейсмологія, системи зв'язку і передачі даних, медична і технічна діагностика, системи керування). Такому широкому застосуванню сприяли успіхи в розробці швидких алгоритмів і методів ЦОСЗ (наприклад, хвилькові перетворення), досягнення в технології конструювання інтегральних схем (архітектура нових процесорів ЦОС, програмовані логічні інтегральні схеми – ПЛІС, системи на кристалі), використання програмних пакетів (MATLAB, база програм на мові С).
Суть ЦОСЗ як області науки пролягає у розв'язку на обчислювальній машині чотирьох основних задач:
- представлення сигналів та зображень в зручній для сприйняття формі;
- виділення із сигналів та зображень корисної інформації;
- внесення в сигнали та зображення корисної інформації;
- формування сигналів та зображень із заданими параметрами.
Основні переваги ЦОСЗ полягають в: можливості реалізації складних методів та алгоритмів обробки сигналів та зображень, недоступних для аналогових пристроїв; забезпеченні високої точності обробки; гнучкості і універсальності засобів, розвиненому користувацькому інтерфейсові тощо.
Головна проблема ЦОСЗ полягає у підвищенні швидкодії при реалізації певного набору математичних операцій над сигналами та зображеннями. Цей набір, як правило, визначається проблемною орієнтацією засобів ЦОСЗ. Для розв'язання цієї задачі комплексно застосовуються два напрямки - підвищення ефективності обчислювальних алгоритмів і вдосконалення архітектури комп'ютерних засобів.
1.Теоретичний розділ
Основні поняття і визначення.
Штучний інтелект (ШІ) - це наука про концепції, що дозволяє ЕОМ робити такі речі, які у людей виглядають розумними. Але що ж є інтелектом людини? Чи є ця здатність роздумувати? Чи є ця здатність засвоювати і використовувати знання? Чи є ця здатність оперувати і обмінюватися ідеями? Поза сумнівом, всі ці здібності є частиною того, що є інтелектом. Насправді дати визначення в звичайному сенсі цього слова, мабуть, неможливо, тому що інтелект - це сплав багатьох навиків в області обробки і представлення інформації.
Центральні завдання ШІ полягають в тому, що б зробити ЕОМ кориснішими і щоб зрозуміти принципи, лежачі в основі інтелекту. Оскільки одне із завдань полягає в тому, щоб зробити ЕОМ кориснішими, ученим і інженерам, що спеціалізуються в обчислювальній техніці, необхідно знати, яким чином ШІ може допомогти їм у вирішення важких проблем.
Область застосування.
Докази теорем;
Ігри;
Розпізнавання образів;
Ухвалення рішень;
Адаптивне програмування;
Твір машинної музики;
Обробка даних на природній мові;
Вербальні концептуальні навчання.
Плани на майбутнє в області застосування ШІ: У сільському господарстві комп'ютери повинні оберігати посіви від шкідників, підрізати дерева і забезпечувати виборчий відхід. У гірській промисловості комп'ютери покликані працювати там, де виникають дуже небезпечні умови для людей. У сфері виробництва ВМ повинні виконувати різного виду завдання після збірки і технічного контролю. У установах ЕОМ зобов'язані займатися складанням розкладів для колективів і окремих людей, робити коротке зведення новин. У учбових закладах ЕОМ повинні розглядати завдання, які вирішують студенти, у пошуках помилок, подібно до того як шукаються помилки в програмі, і усувати їх. Вони повинні забезпечувати студентів суперкнигами, що зберігаються в пам'яті обчислювальних систем. У лікарнях ЕОМ повинні допомагати ставити діагноз, направляти хворих у відповідні відділення, контролювати хід лікування. У домашньому господарстві ЕОМ повинні допомагати радими з готування пищи, закупівлі продуктів, стежити за поляганням підлоги в квартирі і газону в саду. Звичайно, в даний час жодна з цих речей не представляється можливою, але дослідження в області ІЇ можуть сприяти їх реалізації.
Історія розвитку систем штучного інтелекту
Історично склалися три основні напрями в моделюванні ШІ.
В рамках першого підходу об'єктом досліджень є структура і механізми роботи мозку людини, а кінцева мета полягає в розкритті таємниць мислення. Необхідними етапами досліджень в цьому напрямі є побудова моделей на основі психофізіологічних даних, проведення експериментів з ними, висунення нових гіпотез щодо механізмів інтелектуальної діяльності, вдосконалення моделей і т.д.
Другий підхід як об'єкт дослідження розглядає ШІ. Тут мова йде про моделювання інтелектуальної діяльності за допомогою обчислювальних машин. Метою робіт в цьому напрямі є створення алгоритмічного і программн ого забезпечення обчислювальних машин, що дозволяє вирішувати інтелектуальні завдання не гірші за людину.
Нарешті, третій підхід орієнтований на створення змішаних людино-машинних, або, як ще говорять, інтерактивних інтелектуальних систем, на симбіоз можливостей природного і штучного інтелекту. Найважливішими проблемами в цих і сследованіях є оптимальний розподіл функцій між природним і штучним інтелектом і організація діалогу між людиною і машиною.
Найпершими інтелектуальними завданнями, які стали вирішуватися за допомогою ЕОМ були логічні ігри (шашки, шахи), доказ теорем. Хоча, правда тут треба відзначити ще кібернетичні іграшки типу "електронної миші" Клода Ш еннона, яка управлялася складною релейною схемою. Ця мишка могла "досліджувати" лабіринт, і знаходити вихід з нього. А крім того, поміщена у вже відомий нею лабіринт, вона не шукала вихід, а відразу ж, не заглядаючи в тупикові ходи, виходила з лабіринту.
Американський кібернетик А. Самуэль склав для обчислювальної машини програму, яка дозволяє їй грати в шашки, причому в ході гри машина навчається або, принаймні, створює враження, що навчається, покращуючи свою гру на ос нове накопиченого досвіду. У 1962 р. ця програма билася з Р. Нілі, сильним шашкістом в США і перемогла. Яким чином машині вдалося досягти такого високого класу гри? Природно, що в машину були програмно закладені правила гри так, що вибір чергового ходу був підпорядкований цим правилам. На кожній стадії гри машина вибирала черговий хід з безлічі можливих ходів згідно деякому критерію но чества ігри. У шашках (як і в шахах) зазвичай невигідно втрачати свої фігури, і, навпаки, вигідно брати фігури супротивника. Гравець (будь він людина або машина), який зберігає рухливість своїх фігур і право вибору ходів і в той же час тримає під боєм велике число полий на дошці, зазвичай грає краще за свого супротивника, що не надає значення цим елементам гри. Описані критерії хорошої гри зберігають свою силу впродовж всієї гри, але є і інші критерії, які відносяться до окремих її стадій - дебюту, міттендшпілю, ендшпілю.
Розумно поєднуючи такі критерії (наприклад у вигляді лінійної комбінації з експериментально підбираними коефіцієнтами або складнішим чином), можна для оцінки чергового ходу машини отримати деякий числовий показник ефективності - оцінну функцію. Тоді машина, порівнявши між собою показники ефективності чергових ходів, вибере хід, відповідний найбільшому показнику. Подібна автоматизація вибору чергового ходу не обов'язково забезпечує оптимальний вибір, але все таки це якийсь вибір, і на його основі машина може продовжувати гру, удосконалюючи свою стратегію (образ дії) в процесі навчання на минулому досвіді. Формальне навчання полягає в підстроюванні параметрів (коефіцієнтів) про ценочной функцію на основі аналізу проведених ходів і ігор з урахуванням їх результату.
На думку А. Самуеля, машина, що використовує цей вид навчання, може навчитися грати краще, ніж середній гравець, за відносно короткий період часу. Можна сказати, що всі ці елементи інтелекту, продемонстровані машиною в процесі гри в шашки, повідомлені їй автором програми. Частково це так. Але не слід забувати, що програма ця не є "жорсткою", заздалегідь продуманою у всіх деталях. Вона удосконалює свою стратегію гри в процесі самонавчання. І хоча процес "мислення" у машини істотно відмінний тому, що відбувається в мозку що грає в шашки людини, вона здатна у нього виграти. Яскравим прикладом складної інтелектуальної гри до недавнього часу були шахи. У 1974 р. відбувся міжнародний шаховий турнір машин, забезпечених відповідними програмами. Як відомо, перемогу на цьому турнірі отримала советская машина з шаховою програмою "Каїсса". Чому тут спожито "до недавнього часу"? Річ у тому, що недавні події показали, що не дивлячись на досить велику складність шахів, і неможливість, у зв'язку з цим провести повний перебір ходів, можливість перебору їх на велику глибину, чим зазвичай, дуже збільшує шанси на перемогу. Наприклад, за повідомленнями у пресі, комп'ютер фірми IBM, Каспарова, що переміг, мав 256 процесорів, кожен з яких мав 4 Гб дискової пам'яті і 128 Мб про ператівной. Важ цей комплекс міг прораховувати більше 100'000'000 ходів в секунду. До недавнього часу рідкістю був комп'ютер, що може робити таку кількість цілочисельних операцій в секунду, а тут ми говоримо про хо дах, які повинні згенерувати і для яких прораховані оцінні функції. Хоча з іншого боку, цей приклад говорить про могутність і універсальність переборних алгоритмів.
В даний час існують і успішно застосовуються програми, що дозволяють машинам грати в ділові або військові ігри, що мають велике прикладне значення. Тут також надзвичайно важливо додати програмам властиві людині здібність до навчання і адаптації. Одному з найцікавіших інтелектуальних завдань, що також має величезне прикладне значення, є завдання навчання розпізнавання образів і ситуацій. Рішенням її займалися і продовжують займатися представники різних наук - фізіологи, психологи, математики, інженери. Такий інтерес до завдання стимулювався фантастичними перспективами широкого практичного використання результатів теоретичних досліджень: автомати, що читають, системи ІЇ, що ставлять медичні діагнози, п роводящие криміналістську експертизу і т. п., а також роботи, здатні розпізнавати і аналізувати складні сенсорні ситуації.
У 1957 р. американський фізіолог Ф. Розенблатт запропонував модель зорового сприйняття і розпізнавання - перцептрон. Поява машини, здатної навчатися поняттям і розпізнавати об'єкти, що пред'являються, виявилася надзвичайно цікавою н е тільки фізіологам, але і представникам інших областей знання і породило великий потік теоретичних і експериментальних досліджень.
Перцептрон або будь-яка програма, що імітує процес розпізнавання, працюють в двох режимах: у режимі навчання і в режимі розпізнавання. У режимі навчання хтось (людина, машина, робот або природа), що грає роль вчителя, пред'являє ма шині об'єкти і про кожне їх їх повідомляє, до якого поняття (класу) він належить. За цими даними будується вирішальне правило, що є, по суті, формальним описом понять. У режимі розпізнавання машині пред'являються нові об'єкти (взагалі кажучи, відмінні від раніше пред'явлених), і вона повинна їх класифікувати, по можливості, правильно.
Проблема навчання розпізнаванню тісно пов'язана з іншим інтелектуальним завданням - проблемою перекладу з однієї мови на іншій, а також навчання машини мові. При достатньо формальній обробці і класифікації основних граматичних п равіл і прийомів користування словником можна створити цілком задовільний алгоритм для перекладу, скажемо наукового або ділового тексту. Для деяких мов такі системи були створені ще в кінці 60-г. Проте для того, щоб зв'язно перекласти чималий розмовний текст, необхідно розуміти його сенс. Роботи над такими програмами ведуться вже давно, але до повного успіху ще далеко. Є також програми, що забезпечують діалог між людиною і машиною на урізаній природній мові.
Що ж до моделювання логічного мислення, то хорошим модельним завданням тут може служити завдання автоматизації доказу теорем. Починаючи з 1960 р., були розроблені ряд програм, здатних знаходити докази теорем в численні предикатів першого порядку. Ці програми володіють, за словами американського фахівця в області ІЇ Дж. Маккатті, "здоровим глуздом", тобто здатністю робити дедуктивні висновки.
У програмі К. Грина і ін., що реалізовує питання-у відповідь систему, знання записуються на мові логіки предикатів у вигляді набору аксіом, а питання, що задаються машині, формулюються як що підлягають доведенню теореми. Великий інтерес представляє "інтелектуальна" програма американського математика Хао Ванга. Ця програма за 3 хвилини роботи IBM-704 вивела 220 щодо простих лем і теорем з фундаментальної математичної монографії, а потім за 8.5 мін видала докази ще 130 складніших теорем, частина їх яких ще не була виведена математиками. Правда, до цих пір жодна програма не вивела і не довела жодної теореми, яка б, що називається "до зарізу" була б потрібна математі кам і була б принципово новою.
Дуже великим напрямом систем ШІ є роботехніка. У чому основна відмінність інтелекту робота від інтелекту універсальних обчислювальних машин? Для відповіді на це питання доречно пригадати що належить великому російському фізіологові И. М. Сеченову вислів: ". вся нескінченна різноманітність зовнішніх проявів мозкової діяльності зводиться остаточно лише до одного явища - м ишечному руху". Іншими словами, вся інтелектуальна діяльність людини направлена кінець кінцем на активну взаємодію із зовнішнім світом за допомогою рухів. Так само елементи інтелекту робота служать перш за все для організації його ц еленаправленних рухів. В той же час основне призначення чисте комп'ютерних систем ІЇ полягає у вирішенні інтелектуальних задач, що носять абстрактний або допоміжний характер, які зазвичай не пов'язані ні із сприйняттям навколишнього середовища з допомогою позов усственних органів чуття, ні з організацією рухів виконавчих механізмів.
Перших роботів важко назвати інтелектуальними. Тільки у 60-х роках з'явилися очуствленниє роботи, які управлялися універсальними комп'ютерами. Наприклад в 1969 р. в Електротехнічній лабораторії (Японія) почалася розробка проє кта "промисловий інтелектуальний робот". Мета цієї розробки - створення очуствленного маніпуляційного робота з елементами штучного інтелекту для виконання складальний-монтажних робіт з візуальним контролем.
Маніпулятор робота має шість мір свободи і управляється МІНІ-ЕОМ NEAC-3100 (об'єм оперативної пам'яті 32000 слів, об'єм зовнішньої пам'яті на магнітних дисках 273000 слів), що формує потрібне про граммноє рух, який відпрацьовується стежачою електрогідравлічною системою. Схват маніпулятора оснащений тактільнимі датчиками.
Як система зорового сприйняття використовуються дві телевізійні камери, забезпечені червоний-зелено-синіми фільтрами для розпізнавання кольору предметів. Поле зору телевізійної камери розбите на 64*64 осередки. В результаті обработ ки отриманої інформації грубо визначається область, займана предметом, що цікавить робота. Далі, з метою детального вивчення цього предмету виявлена область знов ділиться на 4096 осередків. У тому випадку, коли предмет не поміщається у вибране "віконце ", воно автоматично переміщається, подібно до того, як людина ковзає поглядом по предмету. Робот Електротехнічної лабораторії був здатний розпізнавати прості предмети, обмежені площинами і циліндровими поверхнями при спеціальному освещені і. Вартість даного експериментального зразка складала приблизно 400000 доларів. Поступово характеристики роботів монотонно поліпшувалися, Але до цих пір вони ще далекі по тямущості від людини, хоча деякі операції вже виконують на рівні кращих жонглерів. Наприклад утримують на лезі ножа кульку від настольног про тенісу.
Ще подаруй тут можна виділити роботи київського Інституту кібернетики, де під керівництвом Н. М. Амосова и В. М. Глушкова (нині покійного) ведеться комплекс досліджень, направлених на розробку елементів інтелекту роботів. Особливо е увага в цих дослідженнях приділяється проблемам розпізнавання зображень і мови, логічного виводу (автоматичного доказу теорем) і управління за допомогою нейроподібних мереж.
Наприклад можна розглянути створений ще в 70-х роках макет транспортного автономного інтегрального робота (ТАЇР). Конструктивно ТАЇР є триколісним шасі, на якому змонтована сенсорна система і блок управління. Сенсорна система включає наступні засоби очуствленія: оптичний далекомір, навігаційна система з двома радіомаяками і компасом, контактні датчики, датчики кутів нахилу візка, таймер і ін. І особливість, яка відрізняє ТАЇР від багатьох інших систем, створених у нас і за кордоном, це те, що в його складі немає комп'ютера в тому вигляді, до якого ми звикли. Основу системи управління складає бортова нейроподібна мережа, на якій реалізуються різні алгоритми обробки сенсорної інф ормациі, планування поведінки і управління рухом робота.
В кінці даного дуже короткого огляду розглянемо приклади великомасштабних експертних систем.
MICIN - експертна система для медичної діагностики. Розроблена групою по інфекційних захворюваннях Стенфордського університету. Ставить відповідний діагноз, виходячи з представлених їй симпт омів, і рекомендує курс медикаментозного лікування будь-якій з діагностованих інфекцій. База даних складається з 450 правив.
PUFF - аналіз порушення дихання. Дана система є MICIN, з якої видалили дані по інфекціях і вставили дані про легеневі захворювання.
DENDRAL - розпізнавання хімічних структур. Дана система стара, з тих, що мають звання експертних. Перші версії даної системи з'явилися ще в 1965 році у все том же Стенфордськом університеті. По льзователь дає системі DENDRAL деяку інформацію про речовину, а також дані спектрометрії (інфрачервоною, ядерного магнітного резонансу і мас-спектрометрії), і та у свою чергу видає діагноз у вигляді відповідно й хімічної структури.
PROSPECTOR - експертна система, створена для сприяння пошуку комерційно виправданих родовищ корисних копалини.
Методи вирішення задач.
Функціонування багатьох ІС носить цілеспрямований характер (прикладом можуть служити автономні інтелектуальні роботи). Типовим актом такого функціонування є рішення задачі планування шляху досягнення потрібної мети з деякої фіксованої початкової ситуації. Результатом рішення задачі повинні бути план дій - частково-впорядкована сукупність дій. Такий план нагадує сценарій, в якому як відношення між вершинамі виступають відносини типу: "мета-подцель" "мета-дія", "дія-результат" і т.п. Будь-який шлях в цьому сценарії, ведучий від вершини, відповідної поточної ситуації, в будь-яку з цільових вершин, визначає план дій. Пошук плану дій виникає в ІС лише тоді, коли вона стикається з нестандартною ситуацією, для якої немає заздалегідь відомого набору дій, що приводять до потрібної мети. Всі завдання побудови плану дій можна розбити на два типи, якими відповідають різні моделі: планування в просторі станів (SS-проблема) і планування в просторі завдань (PR-проблема). У першому випадку вважається заданим деякий простір ситуацій. Опис ситуацій включає стан зовнішнього світу і стан ІС, що характеризуються поряд параметрів. Ситуації утворюють деякі узагальнені стани, а дії ІС або зміни в зовнішньому середовищі приводять до зміни актуалізованих в даний момент станів. Серед узагальнених станів виділені початкові стани (звичайне одне) і кінцеві (цільові) стани. SS-проблема полягає в пошуку шляху, ведучого з початкового стану в одне з кінцевих. Якщо, наприклад, ІС призначена для гри в шахи, то узагальненими станами будуть позиції, що складаються на шахівниці. Як початковий стан може розглядатися позиція, яка зафіксована в даний момент ігри, а як цільові позиції - безліч нічийних позицій. Відзначимо, що у разі шахів пряме перерахування цільових позицій неможливе. Матові і нічийні позиції описані на мові, відмінній від мови опису станів, фігур, що характеризуються розташуванням, на полях дошки. Саме це утрудняє пошук плану дій в шаховій грі.
При плануванні в просторі завдань ситуація декілька інша. Простір утворюється в результаті введення на множині завдань відношення типу: "частина - ціле", "завдання - підзадача", "загальний випадок - окремий випадок" і т.п. Іншими словами, простір завдань відображає декомпозицію завдань на підзадачі (цілі на подцелі). PR-проблема полягає в пошуку декомпозиції початкового завдання на підзадачі, що приводить до завдань, рішення яких системі відоме. Наприклад, ІС відомо, як обчислюються значення sin x і cos x для будь-якого значення аргументу і як проводиться операція ділення. Якщо ІС необхідно обчислити tg x, то рішенням PR-проблеми буде представлення цього завдання у вигляді декомпозиції tgx=sin x/cos x (окрім х=p /2+kp ).
Вирішення задач методом пошуку в просторі станів.
Представлення завдань в просторі станів припускає завдання ряду описів: станів, безліч операторів і їх дій на переходи між станами, цільових станів. Описи станів можуть бути рядки символів, вектори, двомірні масиви, дерева, списки і т.п. Оператори переводять один стан в інше. Іноді вони представляються у вигляді продукций A=>B, що означають, що стан А перетвориться в полягання В. Простір станів можна представити як граф, вершини якого помічені станами, а дуги - операторами. Таким чином, проблема пошуку рішення задачі <А,В> при плануванні по станах представляється як проблема пошуку на графі шляху з А у В. Обычно графи не задаються, а генеруються у міру потреби.
Розрізняються сліпі і направлені методи пошуку шляху. Сліпий метод має два види: пошук углиб і пошук вшир. При пошуку углиб кожна альтернатива досліджується до кінця, без урахування решти альтернатив. Метод поганий для "високих" дерев, оскільки легко можна прослизнути мимо потрібної гілки і витратити багато зусиль на дослідження "порожніх" альтернатив. При пошуку вшир на фіксованому рівні досліджуються всі альтернативи і лише після цього здійснюється перехід на наступний рівень. Метод може опинитися гірше за метод пошуку углиб, якщо в графі всі шляхи, що ведуть до цільової вершине, розташовані приблизно на одній і тій же глибині. Обидва сліпі методи вимагають великої витрати часу і тому необхідні направлені методи пошуку.
Метод гілок і меж. З нескінчених шляхів, що формуються в процесі пошуку, вибирається найкоротший і продовжується на один крок. Отримані нові нескінчені шляхи (їх стільки, скільки гілок в даній вершине) розглядаються разом із старими, і знов продовжується на один крок найкоротший з них. Процес повторюється до першого досягнення цільової вершини, рішення запам'ятовується. Потім з нескінчених шляхів, що залишилися, виключаються довші, ніж закінчений шлях, або рівні йому, а ті, що залишилися продовжуються по такому ж алгоритму до тих пір, поки їх довжина менше закінченого шляху. У результаті або всі нескінчені шляхи виключаються, або серед них формується закінчений шлях, коротший, ніж раніше отриманий. Остання дорога починає грати роль еталону і т.д.
Алгоритм найкоротших шляхів Мура. Початкова вершина X0 позначається числом 0. Хай в ході роботи алгоритму на поточному кроці отримана безліч дочірніх вершин X(xi) вершини xi. Тоді з нього викреслюються всі раніше отримані вершини, що залишилися позначаються влучною, збільшеною на одиницю в порівнянні з влучної вершини xi, і від них проводяться покажчики до Xi. Далі на безлічі помічених вершин, що ще не фігурують як адреси покажчиків, вибирається вершина з найменшою міткою і для неї будуються дочірні вершини. Розмітка вершин повторюється до тих пір, поки не буде отримана цільова вершина.
Алгоритм Дейкстри визначення шляхів з мінімальною вартістю є узагальненням алгоритму Мура за рахунок введення дуг змінної довжини.
Алгоритм Дорана і Мічи пошуку з низькою вартістю. Використовується, коли вартість пошуку велика в порівнянні з вартістю оптимального рішення. В цьому випадку замість вибору вершин, найменше видалених від початку, як в алгоритмах Мура і Дійкстри, вибирається вершина, для якої евристична оцінка відстані до мети найменша. При гарній оцінці можна швидко отримати рішення, але немає гарантії, що шлях будемо мінімальними.
Алгоритм Харта, Нільсона і Рафаеля. У алгоритмі об'єднано обидва критерії: вартість шляху до вершини g[x) і вартість шляху від вершини h(x) - в аддитивній оцінній функції f{x) =g(x}-h(x). За умови h(x) <hp(x), де hp(x) -действительное відстань до мети, алгоритм гарантує знаходження оптимального шляху.
Алгоритми пошуку шляху на графі розрізняються також напрямом пошуку. Існують прямі, зворотні і двонаправлені методи пошуку. Прямий пошук йде від початкового стану і, як правило, використовується тоді, коли цільовий стан заданий неявно. Зворотний пошук йде від цільового стану і використовується тоді, коли початковий стан заданий неявно, а цільове явно. Двонаправлений пошук вимагає задовільного рішення двох проблем: зміни напряму пошуку і оптимізації "точки зустрічі". Одним з критеріїв для вирішення першої проблеми є порівняння "ширини" пошуку в обох напрямах - вибирається той напрям, який звужує пошук. Друга проблема викликана тим, що прямий і зворотний шляхи можуть розійтися і чим вужчий пошук, тим це ймовірніше.
Вирішення задач методом редукції.
Цей метод приводить до добрих результатів тому, що часто вирішення задач має ієрархічну структуру. Проте не обов'язково вимагати, щоб основне завдання і всі її підзадачі вирішувалися однаковими методами. Редукція корисна для представлення глобальних аспектів завдання, а при вирішенні більш специфічних задач переважний метод планування по станах. Метод планування по станах можна розглядати як окремий випадок методу планування за допомогою редукцій, бо кожне застосування оператора в просторі станів означає зведення початкового завдання до двох простішим, з яких одна є елементарною. У загальному випадку редукція початкового завдання не зводиться до формування таких двох підзадач, з яких хоч би одна була елементарною.
Пошук планування в просторі завдань полягає в послідовному зведенні початкового завдання до все більш простим до тих пір, поки не будуть отримані тільки елементарні завдання. Частково впорядкована сукупність таких завдань складе рішення початкової задачі. Розчленовування завдання на альтернативну безліч підзадач зручно представляти у вигляді И/ИЛИ-графа. У такому графові всяка вершина, окрім кінцевої, має або кон'юнктивний зв'язані дочірні вершини (І-вершина), або диз'юнктивний зв'язані (ІЛІ-ВЕРШИНА). У окремому випадку, за відсутності І-вершин, має місце граф простору станів. Кінцеві вершини є або завершальними (їм відповідають елементарні завдання), або тупиковими. Початкова вершина (корінь И/ИЛИ-графа) представляє початкове завдання. Мета пошуку на И/ИЛИ-графе-показать, що початкова вершина вирішувана. Вирішуваними є завершальні вершини (І-вершини), у яких вирішувані всі дочірні вершини, і ІЛІ-ВЕРШИНИ, у яких вирішувана хоч би одна дочірня вершина. Вирішуючий граф складається з вирішуваних вершин і указує спосіб вирішуваної початкової вершини. Наявність тупикових вершин приводить до нерозв'язних вершинам. Нерозв'язними є тупикові вершини, І-вершини, у яких нерозв'язна хоч би одна дочірня вершина, і ІЛІ-ВЕРШИНИ, у яких нерозв'язна кожна дочірня вершина.
Алгоритм Ченга і Слейгла. Заснований на перетворенні довільного И/ИЛИ-графа в спеціальний ІЛІ-ГРАФ, кожна ІЛІ-ВЕТВЬ якого має І-вершини тільки в кінці. Перетворення використовує представлення довільного И/ИЛИ-графа як довільної формули логіки висловів з подальшим перетворенням цієї довільної формули в диз'юнктивну нормальну форму. Подібне перетворення дозволяє далі використовувати алгоритм Харта, Нільсона і Рафаеля.
Метод ключових операторів. Хай задано завдання <A, B> і відомо, що оператор f обов'язково повинен входити в рішення цієї задачі. Такий оператор називається ключовим. Хай для застосування f необхідний стан C, а результат його застосування є I(c). Тоді І-вершина <A,В> породжує три дочірні вершини: <A, C>, <C, f{c)> і <f(c), B>, з яких середня є елементарним завданням. До завдань <A, З> і <f(c), B> також підбираються ключові оператори, і вказана процедура редукування повторюється до тих пір, поки це можливо. У результаті початкове завдання <A, B> розбивається на впорядковану сукупність підзадач, кожна з яких вирішується методом планування в просторі станів.
Можливі альтернативи по вибору ключових операторів, так що в загальному випадку матиме місце И/ИЛИ-граф. У більшості завдань вдається не виділити ключового оператора, а тільки вказати множину, що його містить. В цьому випадку для завдання <A, B> обчислюється відмінність між A і B, якому ставиться у відповідність оператор, що знімає це відмінність. Останній і є ключовим.
Метод планування загального вирішувача завдань (ОРЗ). ОРЗ з'явився першою найбільш відомою моделлю планувальника. Він використовувався для вирішення завдань інтегрального числення, логічного виводу, граматичного розбору і ін. ОРЗ об'єднує два основні принципи пошуку:аналіз цілей і засобів і рекурсивне рішення завдань. У кожному циклі пошуку ОРЗ вирішує в жорсткій послідовності три типи стандартних завдань: перетворити об'єкт А в об'єкт В, зменшити відмінність D А і В, застосувати оператора f до об'єкту А. Решение першого завдання визначає відмінність D другий - відповідний оператор f, третьою, - необхідна умова застосування С. Если З не відрізняється від A, то оператор f застосовується, інакше З представляється як чергова мета і цикл повторюється, починаючи із завдання "перетворити A". В цілому стратегія ОРЗ здійснює зворотний поїськ-от заданої мети В до необхідного засобу її досягнення З, використовуючи редукцію початкового завдання <A, В> до завдань <A, C> і <З, В>.
Відмітимо, що в ОРЗ мовчазно передбачається незалежність відмінностей Один від одного, звідки слідує гарантія, що зменшення одних відмінностей не приведе до збільшення інших.
Планування за допомогою логічного виводу. Таке планування припускає: опис станів у вигляді правильних побудованих формул (ППФ) деякого логічного числення, опис операторів у вигляді або ППФ, або правил перекладу одних ППФ в інших. Представлення операторів у вигляді ППФ дозволяє створювати дедуктивні методи планування, представлення операторів у вигляді правил перекладу - методи планування з елементами дедуктивного виводу.
Дедуктивний метод планування системи QA3, ОРЗ не виправдав надій, що покладалися на нього, в основному із-за незадовільного представлення завдань. Спроба виправити положення привела до створення питання-у відповідь системи QA3. Система розрахована на довільну наочну область і здатна шляхом логічного виводу відповісти на питання: чи можливе досягнення полягання В з A? Як метод автоматичного виводу використовується принцип резолюцій. Для напряму логічного виводу QA3 застосовує різні стратегії, в основному синтаксичного характеру, особливості формалізму принципу резолюцій, що враховують. Експлуатація QA3 показала, що вивід в такій системі виходить повільним, детальним, що невластиве міркуванням людини.
Метод продукций системи STRIPS. У цьому методі оператор представляє продукцію Р, А=>В, де Р, А і В - безліч ППФ числення предикатів першого порядку, Р виражає умови застосування ядра продукції А=>В, де В містить список ППФ, що додаються, і список ППФ, що виключаються, тобто умови поста. Метод повторює метод ОРЗ з тією відмінністю, що стандартні завдання визначення відмінностей і застосування відповідних операторів вирішуються на основі принципу резолюцій. Відповідний оператор вибирається так само, як в ОРЗ, на основі принципу "аналіз засобів і цілей". Наявність комбінованого методу планування дозволила обмежити процес логічного виводу описом стану миру, а процес породження нових таких описів залишити за евристикою "від мети до засобу її досягнення".
Метод продукций, що використовує макрооператори [Файкс і ін., 1973]. Макрооператори-ето узагальнені рішення завдань, що отримуються методом STRIPS. Застосування макрооператорів дозволяє скоротити пошук рішення, проте при цьому виникає проблема спрощення вживаного макрооператора, суть якої полягає у виділенні по заданій відмінності його необхідної частини і виключенні з останньої непотрібних операторів.
Вирішення задач дедуктивного вибору
У дедуктивних моделях уявлення і обробки знанні вирішувана проблема записується у вигляді затвердженні формальної системи, цель-у виді твердження, справедливість якого слід встановити або спростувати на підставі аксіом (загальних законів) і правил виведення формальної системи. Як формальна система використовують числення предикатів першого порядку.
Відповідно до правил, встановлених у формальній системі, завершальному твердженню-теоремі, отриманою з початкової системи тверджень (аксіом, посилок), приписується значення ІСТИНА, якщо кожній посилці, аксіомі також приписано значення ІСТИНА. Процедура виводу є процедурою, яка із заданої групи виразів виводить відмінне від заданих вираз.
Зазвичай в логіці предикатів використовується формальний метод доказу теорем, що допускає можливість його машинної реалізації, але існує також можливість доказу неаксіоматичним шляхом : прямим виводом, зворотним виводом.
Метод резолюції використовується як повноцінний (формального) метод доказу теорем.
Для застосування цього методу початкову групу заданих логічних формул потрібний преаобразовать в деяку нормальну форму. Це перетворення проводиться в декілька стадій, складових машину виводу.
Вирішення задач, що використовують немонотонних логіків, імовірнісних логіків.
Дані і знання, з якими доводиться мати справу ІС, рідко бувають абсолютно точними і достовірними. Властива знанням невизначеність може мати різноманітний характер, і для її опису використовується широкий спектр формалізмов. Розглянемо один з типів невизначеності в даних і знаннях - їх неточність. Називатимемо вислів неточним, якщо його істинність (або помилковість) не може бути встановлена з визначеністю. Основоположним поняттям при побудові моделей неточного виводу є поняття вірогідності, тому всі описувані далі методи пов'язані з імовірнісною концепцією.
Модель операції з неточними даними і знаннями включає дві складові: мова представлення неточності і механізм виводу на неточних знаннях. Для побудови мови необхідно вибрати форму представлення неточності (наприклад, скаляр, інтервал, розподіл, лінгвістичний вираз, множина) і передбачити можливість приписування міри неточності всім висловам.
Механізми операції з неточними висловами можна розділити на два типи. До першого відносяться механізми, що носять "приєднаний" характер: перерахунок заходів неточності як би супроводжує процес виводу, що ведеться на точних висловах. Для розробки приєднаної моделі неточного виводу в заснованій на правилах виводу системі необхідно задати функції перерахунку, що дозволяють обчислювати: а) міру неточності антецедента правила (його лівій частині) по заходах неточності складових його висловів; би) міру неточності консеквента правила (його правій частині) по заходах неточності правила і посилки правила; у) об'єднану міру неточності вислову по заходах, отриманих з правил.
Введення міри неточності дозволить привнести в процес виводу щось принципово нове - можливість об'єднання сили декількох свідоцтв, підтверджуючих або спростувальних одну і ту ж гіпотезу. Іншими словами, при використанні заходів неточності доцільно виводити одне і те ж твердження різними шляхами (з подальшим об'єднанням значень неточності), що абсолютно безглуздо в традиційній дедуктивній логіці. Для об'єднання свідоцтв потрібна функція перерахунку, що займає центральне місце в перерахунку. Відмітимо, що, не дивлячись на "прісоєдіненность" механізмів виведення цього типу, їх реалізація в базах знань робить вплив на загальну стратегію виводу: з одного боку, необхідно виводити гіпотезу всіма можливими шляхами для того, щоб врахувати всі релевантні цій гіпотезі свідоцтва, з другой-предотвратіть багатократний вплив сили одних і тих же свідоцтв.
Для механізмів операції з неточними висловами другого типу характерна наявність схем виводу, спеціально орієнтованих на використовувану мову представлення неточності. Як правило, кожному кроку виводу відповідає перерахунок заходів неточності, обумовлений співвідношенням на безлічі висловів (співвідношенням може бути елементарний логічний зв'язок, безвідносно до того, чи є це відношення фрагментом якого-небудь правила). Таким чином, механізми другого типу застосовні не тільки до знань, виражених у формі правил
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора