729G10 Artificiell intelligens I

Laboration 3: Sökning

Sammanfattning

Er uppgift i den här laborationen är att köra olika sökalgoritmer på dammsugardomänen. De resultat ni får ska utgöra basen för en diskussion om algortmernas lämplighet i denna domän.

Syfte

Syftet med denna laboration är att ge en inblick i hur olika sökmetoder fungerar. Ni ska förstå de olika sökmetodernas styrkor och svagheter.

Förberedelser

För att kunna utföra laborationen så snabbt och enkelt som möjligt bör ni förbereda er genom att:

1. Läsa kapitel 3 och 4 i boken.
2. Läsa igenom laborationsinstruktionerna noga.

Ni bör ha klart för er hur sökträdet ser ut i dammsugardomänen samt vilken information som finns i varje nod och vilken förgreningsfaktorn är.

Laborationssystemet

Den kod som används i denna laboration ligger i katalogen ~729G10/Kursbibliotek/Lab3/

Om ert login är abcde12 och ni vill kopiera filerna till katalogen Labbar/AI/Lab3/ så kan ni skriva följande i ett skalfönster:

% cd
% cd Labbar/AI/Lab3
% cp ~729G10/Kursbibliotek/Lab3/* .

Sökagenter

Tanken är här att använda en ny slags agent, en så kallad sökagent som tänker först och handlar sen. Vi skall använda oss av samma domän som i föregående laboration det vill säga dammsugarproblemet.

Givet en problembeskrivning, söker en sökbaserad dammsugare fram en sekvens handlingar som beskriver hur den ska röra sig för att städa alla smutsiga rutor och sen åka tillbaka till städskrubben för att där stänga av sig. En förutsättning för detta är att dammsugaren har fullständig kännedom om hur världen ser ut, speciellt var smutsen är. Detta betyder att när den väl har utfört sökningen, behöver den inga percept för att kunna agera. Den vet allt och det finns därmed inget behov av att ta in mer information via percept.

Sökalgoritmer

Nedan följer en uppräkning av alla de sökalgoritmer som ni ska testa och utvärdera. Dessa är definierade i filen ~729G10/Kursbibliotek/Lab3/Search.py

Uninformed (blind) search

breadth_first_search
depth_first_search
depth_limited_search
iterative_deepening_search

Uniformed search with loop detection, Graph search

breadth_first_graph_search
depth_first_graph_search

Informed search

greedy_search
astar_search

Att skapa problem

Sökalgoritmerna tar ett problem som indata och returnerar en sekvens av handlingar som leder till ett fördefinierat mål. Problem kan skapas med hjälp av konstruktorfunktionen som finns för problemdomänen. Funktionen VacuumProblem tar världens storlek i width x height rutor som obligatoriska argument samt en lista dirt med rutor som är smutsiga.

För att göra det hela mer konkret. Om man vill skapa ett dammsugarproblem med namnet vp med 2 x 2 rutor och smuts på ruta (2, 2), så skriver man:

vp = VacuumProblem(2, 2, [(2, 2)])

Detta funktionsanrop returnerar:

<VacuumProblem <VacuumState (1, 1) (1, 0) [(2, 2)] True 2 2>>

<VacuumState (1, 1) (1, 0) [(2, 2)] True 2 2> representerar tillståndet för rotnoden i sökträdet. De olika delarna har följande betydelse:

(1, 1) är agentens position.
(1, 0) är agentens riktning åt öster.
[(2, 2)] representerar rutorna med skräp.
True anger att dammsugaren är på.
2 2 är världens storlek.

Det finns ett antal färdigdefinierade problem i den givna koden. Det räcker att ni testar på dessa problem, men ni får gärna skapa nya problem om ni tycker att det behövs eller är intressant.

Att köra sökalgoritmer på problem

Agenten löser ett problem genom att bygga upp ett sökträd där varje nod anger djupet i sökträdet, handlingen som utfördes för att nå noden, samt tillståndet.

Varje handling överför ett tillstånd till ett nytt tillstånd. Följande är en lista med de möjliga tillstånd som kan följa på rotnodens tillstånd:

För att lösa ett problem med en specifik algoritm använder ni funktionen solve. Denna funktion tar ett problem och en algoritm som argument. Eftersom vi skapat ett problem, vp, kan vi välja att köra sökagenten med strategin breadth_first_search genom att skriva:

solve(vp, breadth_first_search)

Då skrivs följande information ut:

Solution: 4 ['Forward', 'TurnLeft', 'Forward', 'Suck']
Expanded nodes: 210 
Nodes in queue: 1050
Time: 0.1871

Observera! Några av algoritmerna kanske inte finner en lösning inom rimlig tid (ca 2-3 min) och att ni kan bli tvungna att avbryta körningar (Ctrl+c).

Att jämföra olika algoritmer

Ni kan också jämföra olika sökalgoritmer med hjälp av funktionen compare som returnerar en tabell med information om de olika algoritmernas effektivitet: Längden på lösningen, Antalet expanderade noder, Antalet noder i kön, Tiden att hitta lösningen

compare([vp], [breadth_first_search, breadth_first_graph_search])

breadth_first_search         4    210   1050   0.1615  
breadth_first_graph_search   4     24    120   0.0198  

Utförande

1. Kopiera filerna i katalogen ~729G10/Kursbibliotek/Lab3/ till din egen hemkatalog.
2. Öppna filen ~729G10/Kursbibliotek/Lab3/Lab3.py i t.ex. idle
3. Titta på de fördefinierade dammsugarproblemen. Testa alla de olika algoritmerna på några av problemen (genom att kommentera och kommentera bort anropen längst ner i filen). Vilka resultat kan man förvänta sig, stämmer de med era? Förklara varför vissa algoritmer är olämpliga och varför andra fungerar bra.

   Observera! Några av algoritmerna kanske inte finner en lösning inom rimlig tid (ca 2-3 min) och att ni kan bli tvungna att avbryta körningar (C-c C-c).

4. Diskutera hur graf-sökning fungerar och på vilket sätt resultatet förbättras jämfört med träd-sökning för bredden först och djupet först.

5. Välj ut de algoritmer som verkar bäst lämpade och testa dem på ett större problem. Diskutera de resultat ni får.

6. Fundera på och diskutera hur prestandan förändras då världen utvidgas till att bli n gånger n stor, för sökagenter respektive agenterna från laboration 1 och 2.

7. Fundera på och diskutera vilka fördelar och nackdelar det finns med att använda sökning (jämför t.ex. med agenten från laboration 1 eller 2 som ej använde sökning).

8. Fundera på och diskutera i vilka situationer/för vilka typer av problem ni tror att sökning är en lämplig problemlösningsmetod.

9. Den här deluppgiften om heuristik behöver bara utföras för väl godkänt:

   Heuristiken som används av greedy_search och astar_search för att uppskatta avståndet till målet är för dammsugardomänen definierad som antalet dammtussar som återstår att suga upp gånger två minus ett. Kostnaden är 1 för alla handlingar. Ni ska definiera om denna funktion vaccum_heuristics. Funktionen får in en nod som innehåller ett tillstånd som i sin tur innehåller information om agentens position, riktning och vart det finns smuts. Den ska returnera ett numeriskt värde som är en uppskattning av den "billigaste" vägen från ett tillstånd till måltillståndet. Er heuristik ska alltid underskatta kostnaden (för att A*-sökning ska vara komplett och optimal), och den ska vara bättre än den givna heuristiken (dvs ge en uppskattning som ligger närmare den faktiska kostnaden).

   Beskriv er heuristik och motivera varför den är bättre än den befintliga. Diskutera vilken förbättring den leder till för de två olika algoritmerna och om förändringen stämde med era förväntningar.

Redovisning och bedömning

Redovisning enligt nedan skickas till e-post: Labbass.AI@gmail.com, samt lämnas in i labbomslag i Jody Foos fack.

• Lämna in er diskussion av punkterna under utförande.
• För väl godkänt, maila in koden för er heuristik (se nedan), samt lämna in en utskrift av den.

Krav för godkänt

För betyget godkänt krävs att diskussionen är relevant med tydliga kopplingar mellan teori och praktik och visar på att ni verkligen testat och utvärderat alla sökstrategierna.

Krav för väl godkänt

För väl godkänt gäller samma krav som för godkänt, samt att ni utvecklar en egen heuristik som kan användas av exempelvis astar_search. Heuristiken ska vara genomtänkt och bättre än den befintliga.

Sidansvarig: Arne Jönsson