Изкуствен интелект

[Mozo]

1Основни понятия и история на Изкустевения Интелект /ИИ/
Изкуствен интелект (ИИ) е наука за концепциите, които позволяват на компютрите да правят такива неща, които за хората изглеждат разумни (дефиниция на П. Уинстън).
ИИ е наука за възгледите, принципите, методите и средствата за създаване на интелигентни компютърни и програмни системи, и за изследване на естествения интелект чрез компютърни системи.
Системите с ИИ(от гледна точка на теория на системите), системите с ИИ не мдб отнесени към най-сложните системи, каквито са биологическите, социалните и икономическите системи, но те се приравняват към слойните системи, които се опитват да моделират или имитират човешко мислене. Системите за ИИ имат свойството на компютърни системи, които да получават резултати, които са равносилни на такива, породени в процеса на творческа дейност на човека.
ИИ обединява различни области освен комп наука и математика, също така философия, психология, биология, физиология, лингвистика и логика;
Терминът ИИ е бил приет на първата международна конференция по Изкуствен интелект във Вашингтон през 1960г.

2. Направления в ИИ
Изследванията в ИИ се разделят в 3 направления:
• Информационно – основава се на методите за създаване на комп.програми, които автоматизират такива видове човешка дйност, традиционно смятани за интелектуални;
• Биофизично – отчита процесите в нервната с-ма, при съазаването на комп. програми;
• Еволюционно – използва съвремено знанията от информационното и физическото направление като отчита техните особености;
Цели на ИИ:
1. Адекватно моделиране на възможностите на човешкия интелект при създаване на комп.програмно среди;
2. Изследване на естествения интелект виз основа на създадените мопдели;
Традиционни направления на ИИ:
• търсене в пространството на състоянията;
• логически изводи;
• представяне и използване на знания;
• общуване на комп с-ма на ограничен естествен език;
• машинен превод;
• пазпознаване на образи;
• машинно обучение;
• експертни с-ми;
• невронни мреви;
• планиране на действията/роботика;

3. Характеристики на Системи с Изкуствен интелект /СИИ/
1. Използване на знания;
2. Използване на извод;
3. интерфейс на ограничен естествен език;
4. планиране на действия;
5. обяснение на решението;
6. обучение и самообучение;
Трите основни ограничения на ИИ:
1. за интелект може да се говори, само когато материята се намира в живо състояние;
2. може да смятаме, че една с-ма е интелектуална, ако се намира в съзнателно състояние;
3. само високо организирана жива материя има съзнание;


4. Обща постановка и основни задачи на търсене в пртостранство на състоянията.
Обща постановка – решаването на много задачи, смятани за интелектуални може да бъде сведено до последователно преминаване от едно описание на задачата към еквивалентно друго, докато се стигне до това, което се смята за решение на задачата / например задччи от теория на игрите/.
Основни дефиниции:
• състояние – едно описание на задачата, в процеса на нейното решаване. Видовете състояния са: начално, междинно и крайно (целево);
• оператор- начина (правило, алгоритъм, функция), по който едно състояние се получава от друго;
• пространство на състоянието – съвкупност от всички възможни състояния, коитомогат да се получат от дадено начално състояние. Целта е да достигнем крайно състояние по най-кратък път. За представянето на пространството на състоянието, най-естествения начин е ч/з ориентиран граф, където възлите представляват състоянията, а ориентираните дъги операторите.
Основни типове задачи - три са основните типове задачи за търсене в пространство на състоянията:
• първи тип задачи са : търсене на път до определена цел, което предполага търсене на път от някакво начално състояние до определено целево състояние (path finding). Може да има критерии за този път (най-къс,най-икономичен и др);
• втори основен тип е търсене на печеливша стратегия. Характерен при теорията на игрите (шах, морски шах).
• Третия тип задача е търсене на цел при ограничителни условия (constraint satisfaction problem). Силно ограничени критични условия. Например задачата за криптограмите.


6. Методи за търсене на път до цел
За решаване на този тип задачи се използват два основни метода:
1. пълно изпълнение – обхожданбе на всички; пълното изчерпване се използва, когато: нямаме никаква информация за задачата. Характерно за този туп методие, че е крайно неефективно; може да се получи практически невъзможно намирането на решения, поради т.хап.комбинаторен взрив (много подзадачи, с които изчислителната логика не може да се справи)/
2. евристично/информирано търсене – характеристики:
• използват се експертни зания;
• по-голяма ефективност;
• преценен риск;
Основни стратегии за търсене на път до цел са:
1) обхождане в дълбочина;
2) обхождане в широчина;
3) комбинирана стратегия;
7. Търсене в дълбочина depth first:
a->b; b->d; b->e; e->f; e->h; a->c (да);



8. Търсене в ширина breadth first :
a->b; b->c; c->d; d->e; e->f; f->h (да);

9. Обобщен алгоритъм на пълното изчерпване
Обобщен алгоритъм на пълното изчерпване (generate - test) – прво се генерира състояние, тества се и после други и т.н.
Алгоритъм:
Стъпка 1: Генериране на следващо вузможно състояние (възел от граф), съгласно избраната стратегия, като се записва в специален списък;
Стъпка 2: Сравняване на това състояние с целевото състояние;
Стъпка 3: Ако съвпада, то – намерено решение и работата се прекратява, като се представя намереното състояние и списъка от генерираните последователно възли (показва пътя). В противен случай (ако е „не”), преминаваме към Стъпка 1.

10. Метод на изчакването
При този метод се използва функция, която оценява степента на близост на даденото състояние до търсената цел. В много задачи хе е трудно да се формулира (състави) такава функция, която дава приближени резултати. Метода се нарича ‘ на изчакването’, защото оценяващата функция нараства при приближаване към целевото състояние.
Опростен алгоритъм на изкачване:
Стъпка 1: Оценява се началното състояние. Ако то е целево, имаме край. В противен случай, текущото състояние се приема за начално състояние;
Стъпка 2: Генерира се нов наследник на текущото състояние;
Стъпка 3: Оценява се новото състояние, като ако то не е по-добро от текущото, се връщаме стъпка назад към предишното, съобразно оценяващата функция. Ако е по-добро от текущото, новото състояние става текущо и преминаваме към стъпка 1.
Характерното при този метод е, че имаме т.нар локални максимуми, т.е. състояния, които са добри, но не са целеви. Тези проблеми се решават чрез подхода за връщане назад и подбор на подходяща оценъчна функция.
Пример: Задача от света на кубовете:
- начално състояние - целево състояние


Допустимите действия/оператори са два:
1) вземане на блок със свободна горна повърхност и поставянето му на масата;
2) вземане на блок със свободна горна повърхност и поставянето му върху друг блок със свободна горна повърхност;
Оценяващата функция е следната: - добавя се една точка за всеки блок, който се поставя върху правилна непосредставена опора ; - изважда се една точка за всеки блок, който се поставя вурху неправилна непосрествена опора;
Правилната непосредствена опора се определя от целевото състояние.


11. Метод за най-доброто спускане
Това е евристичен метод по своя характер, но и вариант на пълното изчерпване. Представлява комбинация на търсене в дълбочина и ширина, като се следва път, който се окаже по-перспективен. Тук евристиката е избора на посока. Методът се нарича най-доброто спускане, поради намаляване на стойността на оценяващата функция при приближаване към целевото състояние. На всяка стъпка от изпълнението на алгоритъма, се избира възела с най-добра оценка от генерираните до момента, след това се генерират наследниците на избрание възел. Ако някой от тях е целевото състояние, то алгоритъма се прекратява, т.е.край. В противен случай се добавят генерираните възли към общия списък на възлите и отново се оценяват, като се избира възел с най-малка оценка. Характерно за този алгоритъм е, че има преоценяване на перспективата на даден клон, и ако се открие по-перспективен нов клок имаме връщане назад, като се изоставя текущия клон, и така докато се намери целевото състояние /процеса е итеративен/.
Пример: Нека имам дърво на решенията, което има разходите до достигабне на дадена цел. Етап 1: избира се възелът с най-ниска стойност и се генерират и неговите наследници. След това се оценяват всички възли, избира се този с най-малка стийност и се генерират и неговите наследници.

Целият материал: