INFO283 Kunstig Intelligens k.1-3

Home > Preview

The flashcards below were created by user burntoutmatch on FreezingBlue Flashcards.


  1. Hvilke fire element blant disse inngår i definisjonen av et tilstandsrom
    Mål-tilstander, Handlinger, Tilstander, Start-tilstander, Overganger
  2. definisjonen av et tilstandsrom (state-space problem )
    representasjon av tilstander, overganger, start og mål for problemløsning. rom for tilstander, start tilstander, sett av mulig handlinger i hver tilstand - handling funksjon som returnerer
  3. KVA ER KUNSTIG INTELLIGENS?
    Kunstig intelligens er syntese og analyse av beregningsagenter som oppfører seg på et intelligent vis

    Kunstig intelligens er forsknings- og utviklingsfelt innenfor datateknologien som benytter teoretiske og eksperimentelle dataverktøy til å studere intelligent atferd, og som bruker resultatene til å konstruere datasystemer som er «intelligente» i den forstand at de er i stand til å løse problemer og lære av egne erfaringer.
  4. agent kart
    Evner, mål, forkunnskap (regler, initiell kunnskap), observasjoner -> Gjør en "ny" handling basert på disse -> som endrer omgivelsene...

    så skaper agenten erfaringer, og basert på de første 4 og tidligere erfaring -> handling
  5. agent med bil eksempel
    Agenter kan virke i fysiske omgivelser (roboter) eller i virtuelle omgivelser (f. eks. Internett). En intelligent agent mottar signaler fra omgivelsen (f.eks. sensorinntrykk i en selvstyrt bil) og reagerer tilbake med aksjoner som kan påvirke omgivelsen (ratt, gass og brems).
  6. verden
    består av omgivelsene og agenter.
  7. et sjakkprogram som agent
    • Evner: Velge gode sjakktrekk, vise trekka, la brukarenvelge trekk
    • Mål: Slå brukar i sjakk, Vise gode trekk, forklare
    • Initiellkunnskap: sjakkreglane, brukarensnivå
    • Observasjonar: Brukarenstrekk, brukarensnivå
    • Tidlegareerfaringar: Tidligere sjakkparti og deres resultat
  8. symbolsystemhypotesen
    et symbol er et meningsfylt mønster. symbolsystemet endrer på mønster, manipulerer symbolene. et fysisk symbolsystem har de nødvendige og tilstrekkelige virkemidler for generell intelligent handling. agent er et fysisk symbolsystem. to nivå - kunnskapsnivå og symbolnivå.
  9. komleksitet
    avgrenser og muliggjør løsninger. modulariet, representasjon, planlegging, usikkerhet, preferanser, tal på agenter, læring, utrekning
  10. hierarkisk kontroll
    erfaringer for å tilpasse seg for omgivelsene
  11. State-space searching assumes:
    • The agent has perfect knowledge of the state space and is planning for the case where it observes what state it is in: there is full observability.• The agent has a set of actions that have known deterministic effects.• The agent can determine whether a state satisfies the goal.A solution is a sequence of actions that will get the agent from its current state to a state that satisfies the goal.
  12. frontier
    sets of paths from the start node
  13. A directed graph consists of
    set of N nodes, A arcs (ordered pair of nodes)
  14. A path from node s to node g
    is a sequence of nodes, s=n0 and g=nk
  15. kostnader
    positivt tall. cost of arc <ni,nj> is written cost (<ni,nj>). stier har kostnad lik summen av kantene i stien.
  16. optimal løsning
    billigst sti
  17. example how to write N and A graph data with mail
    • N = {mail, ts, o103,b3,o109,...}
    • A = {<ts,mail>, <o103,ts>,...}
  18. sykel
    is a nonempty path where the end node is the same as the start node (starter / ender node på samme plassen)
  19. directed acyclic graph (DAG) / retta asyklisk graf
    graf uten sykler
  20. A tree
    A tree is a DAG where there is one node with no incoming arcs and every other node has exactly one incoming arc. maks 1 mellom 2 noder.
  21. root / rot. leaf / blad node.
    Root is the node with no incoming arcs. Leaf is a node with no outgoing arcs.
  22. forward branching factor and backward branching factor
    forward branching factor of a node is the number of outgoing arcs from the node. backward branching factor of a node is the number of incoming arcs to the node.
  23. Skriv en generell, overordnet algoritme for søk i et tilstandsrom (bruk Java eller
    pseudokode)
    • procedure Search(G,S,goal)
    • inputs
    • g: graph, set of nodes N, arcs A
    • s: start node
    • goal: boolean function of nodes

    • output
    • path from s to a node for which goal is true 
    • or null if no solution

    • local
    • Frontier: set of paths from start node
    • Frontier <- {<s>}

    • while Frontier !== { } do
    • select and remove <n0,...,nk> from Frontier
    • if goal (nk) then
    • return <n0,...,nk>
    • Frontier <- Frontier U {<n0,...,nk,n> : <nk,n> E A}
    • return null
  24. bredde-først-søk
    • Algoritmen går systematisk gjennom grafen ved å undersøke om noden som kontrolleres har barn. Dersom dette er tilfellet, blir de lagt til i en kø. Alle søskennodene (nodene på samme nivå) blir søkt gjennom før traverseringen fortsetter ned på neste nivå.
    • KØ - First In First Out

    Image Upload
  25. bredde-først-søk algorithme
    • 1. Legg rotnoden til i køen
    • 2. Hent en node ut av køen og undersøk den
    • a. Hvis noden stemmer overens med ønsket resultat, avslutt algoritmen og returner resultatet
    • b. Hvis ikke, legg nodens barn til i køen
    • 3. Hvis køen er tom, er alle nodene i grafen undersøkt og søket må avsluttes uten resultat
    • 4. Gjenta fra steg 2

    Legg alle nye stier bak alle de andre stiene i Frontier.
  26. Dybde-først-søk (DFS)
    en søkealgoritme for grafer som prioriterer å gå nedover i grafen så langt råden er før den prøver andre stier. Når en kommer til en løvnode eller det ikke finns flere etterkommere å prøve, går en tilbake til forrige node for å prøve og finne neste etterkommere. Dette gjentas til løsningen er nådd eller når det er ingen flere stier å prøve.

    I et dybde-først-søk, fungerer søkefronten som en LIFO (last-in first-out) stabel (stack) av stier. I en stabel blir elementene lagt til og fjernet fra toppen av stabelen.

    • Legg alle nye stier fremfor alle de andre stiene i Frontier.
    • Image Upload
  27. Best-Først-Søk
    Prioritere å undersøke de stiene som er billigst. Kostnad å gå på et punkt til et annet, fra node til node. Prioritetskø. Legg alle nye stier sortert blant alle de andre stiene i Frontier.

    når en velger en sti, legg til alle barne sortert etter hvor dyre stien til barna er
  28. greedy best-first search
    to always select a path on the frontier with the lowest heuristic value.
  29. A* Search
    En søkestrategi der h(n) alltid underestimerer den faktiske kostnaden til målet vil alltid finne en optimal løsning. 

    en estimert kostnad for å komme til målet fra node h(n)
  30. heuristisk søk
    • noder som vi beskøder under et søk har:
    • en kostnad for å komme til noden cost(n)
    • en estimert kostnad for å komme til målet fra noden h(n)
    • en estimert totalkostnad f(n) = cost(n)+h(n) eller f = g+h

    bruk best-først med prioriteringskø der stier er rangert etter f(n) istedenfor etter cost(n)

    • f = g + h
    • f cost of a node
    • g cost taken to get to this node
    • h guess as to how much it will cost to reach the goal from that node
  31. noen eksemper for hvordan man finner h i en heuristisk søk?
    • non-negative function h of nodes.
    • heauristisk verdi:
    • hamming distance, Manhattan distance, euclidean
  32. Hamming Distance
    regner ut tallet på feilplasserte brikker. forskjellen mellom 2 strenger... regnes ut de minste antall utskriftninger som er nødvendig for å transformere den ene strengen til den andre.
  33. Manhattan Distance
    • regner ut hvor mange ganger en brikke må flytte for å komme på rett plass, og summerer dette for alle brikker. take the sum of the absolute values of the differences of the coordinates.
    • if x=a,b and y=c,d
    • Manhattan distance btw x and y is a-c + b-d
  34. er estimat for h(n) i A* søk brukelig(admissible)?
    skrives h*(n). For optimalt søk, - verify that h(n) are indeed underestimates of the shortest path to a goal state from those states.
  35. hvordan undersøker best-, dybde-, og bredde-først noder?
    • best-først: prioritetskø, flere stier pruning, eksponentiell plass
    • dybde-først: stabel, sykler pruning, linear plass
    • bredde-først: kø, flere stier pruning, eksponentiell plass
  36. sykler og flere/multiple stier
    • multiple stier (multiple path pruning): ofte mer enn 1 vei til en node.
    • sykler: problem rom kan gå fra en node tilbake til en annen node på stien til denne noden

    løsning: merk noder når de vært besøkt
  37. iterativ dybde-først søk
    • optimal løsning med dybde-først
    • iterasjon n - stopper søket når stiene vært n lang/lenge
    • besøker nodene i problemrommet flere ganger, koster mer tid
    • nesten samme som bredde-først, men trenger mindre plass
  38. grein-og-grense (branch and border)
    • for å finne optimale løsninger med dybde-først
    • 1. start med en kjent makskostnad b på beste løsning
    • 2. avbryt dybde-først søk når sti koster mer enn b
    • 3. som løsning p er bedre enn b, oppdater b verdien til cost(p)
    • 4. fortsett

    kan ikke bruke merking av noder. bruk når flere sti til goal. kombinerer plass sparing fra dybde-først med heuristisk info.

    f.eks subtree has nothing under 5, but the ninth node has a goal value, path cost is 5, so bound is set to 5, only paths with a cost of less than 5 are checked for being a solution. 15th node checked is also a goal with path cost 3, bound reduced to 3. If no other paths found, 15 is returned. Checks then anything less than 3. Even though 1->16->18->goal, is also 3, that is not less than 3, rest is pruned after 2, only one path is returned, the first one with lowest-cost path.
  39. retningsstyte søk
    • søk fra enten en vei eller begge mål-node og start-node samtidig. når en node er med i begge søkefrontene har vi en løsning.
    • søk via en eller flere nodeøyer: spesifiser nodemengder der du vet løsninger må innom (heis 2 etasjer), søk start til øy, øy til mål.
    • søk på ulike abstraksjonsnivå

    søk begge: a depth-first search in both directions is not likely to work at all unless one is extremely lucky because its small search frontiers are likely to pass each other by. Breadth-first search in both directions would be guaranteed to meet.
  40. dynamisk programmering
    • Finn raskeste stier fra alle noder ved å søke baklengs fra målnoden oppretting de laveste kostnadene til målet fra hver node i grafen. Må vite eksakt hvordan målnoden ser ut.
    • Allerede funnet løsninger kan hentes ut istedenfor å finne de på nytt.
    • kost = sum av kant til etterkommer + kost for etterkommer
    • kan brukes i enkelte avgrenset problemrom.

Card Set Information

Author:
burntoutmatch
ID:
336492
Filename:
INFO283 Kunstig Intelligens k.1-3
Updated:
2017-12-07 20:29:14
Tags:
Kunstig Intelligens
Folders:

Description:
Eksamensnotater
Show Answers:

Home > Flashcards > Print Preview