Examen solucionado 2015-2016 (1er parcial) (2017)

Examen Catalán
Universidad Universidad Autónoma de Barcelona (UAB)
Grado Gestión Aeronáutica - 2º curso
Asignatura IA - Inteligencia Artificial
Año del apunte 2017
Páginas 6
Fecha de subida 15/06/2017
Descargas 0
Subido por

Vista previa del texto

INTEL·LIGÈNCIA ARTIFICIAL – GESTIÓ AERONÀUTICA CURS 2015-2016 – 1er Parcial Cognoms i nom: ________________SOLUCIONS________________________ NIU: ______________ IMPORTANT: JUSTIFIQUEU TOTES LES RESPOSTES. LES RESPOSTES HAN DE FER REFERÈNCIA AL PROBLEMA CONCRET PLANTEJAT.
1.- (2 PUNTS) Responeu de forma breu les següents qüestions: a) Donades les següents definicions d'agent racional, indiqueu quina és la correcta des del punt de vista de la intel·ligència artificial actual: a.1) És una màquina que replica exactament tots els comportaments dels humans a partir de modelitzar tots els processos cognitius dels humans.
a.2) És qualsevol programa capaç de solucionar un problema donat a partir de l'avaluació de totes les possibilitats que presenta i de la construcció d'una gran taula d'estats que contempli totes les possibles respostes al problema.
a.3) És un programa/màquina que actua per aconseguir el millor resultat que sigui possible segons un criteri d'èxit en un objectiu concret.
b) Suposeu que volem dissenyar un sistema detector de passatgers amb febre a partir d'una imatge tèrmica del passatger. Quins serien els quatre elements bàsics que definirien aquest agent? Criteri d’èxit: Número de malalts correctament detectats, número de falsos positius (clients sans detectats com a malalts), ...
Entorn: Control de seguretat d'un aeroport a les portes d'arribada Sensors: Càmera tèrmica Actuadors: Pantalles on surten els resultats, alarma sonora, indicador lluminós c) Doneu les característiques de l'entorn de treball de l'agent de l'apartat anterior segons els criteris.
d) Observable (total / parcial) Determinista / Estocàstic Episòdic / Seqüencial Estàtic / Dinàmic Discret / Continu Mono- / MultiAgent Parcialment Estocàstic Episòdic Estàtic Continu Mono-agent Citeu i expliqueu breument tres de les característiques desitjables en una representació del coneixement.
• Ser clara: les relacions i els objectes importants apareixen de forma explícita, és a dir, s'ha de poder entendre el que està dient.
• Ser completa: ha de permetre descriure tot el que necessitem.
• Ser concisa: ha de permetre descriure tot el que necessitem però no més.
• Ser computable: vol dir que existeixi un algorisme que la pugui construir, transformar i eliminar.
• Ser eficient: ha de permetre actualitzar la informació ràpidament.
2.- (2 PUNTS) Responeu de forma breu les següents qüestions: a) Donat el següent arbre de cerca corresponent a un problema, digueu quina solució (estat objectiu) trobaria i quants nodes avaluaria cadascun dels següents algorismes de cerca: a.1) Cerca en amplada Solució trobada: A Núm. nodes avaluats: 18 a.2) Cerca en profunditat Solució trobada: E Núm. nodes avaluats: 11 a.3) Cerca en profunditat limitada Solució trobada: B (prof. màx. = 4) Núm. nodes avaluats: 10 b) Suposeu que apliquem l'algorisme A* a un problema pel qual es disposa de tres heurístiques admissibles: Estats del problema Funció heurística 1 Funció heurística 2 Funció heurística 3 E1 4 5 3 E2 7 5 2 E3 5 4 4 E4 2 2 3 E5 17 10 5 E6 5 6 2 E7 1 1 3 E8 7 6 6 Com es podria crear una heurística millor que qualsevol de les tres donades? Es podria crear una heurística dominant sobre h1, h2 i h3 fent h(n)=max{h1(n), h2(n), h3(n)}, és a dir, triant el màxim valor de les tres heurístiques per cada estat.
Escriviu els valors que donaria la nova heurística per a cada estat del problema: Estats del problema Nova heurística E1 5 E2 7 E3 5 E4 3 E5 17 E6 6 E7 3 E8 7 c) Suposeu un problema de cerca on s'ha de buscar un camí a la solució. En aquest problema, tots els canvis d'un estat a un altre tenen el mateix cost i a més, no és possible definir cap heurística que ajudi a trobar la solució més ràpidament.
Suposeu que, donat el volum del problema, ens trobem que si l'algorisme que apliquem per trobar la solució genera llistes molt llargues tenim problemes amb la quantitat de memòria necessària per trobar la solució (el nostre ordinador no té prou memòria per emmagatzemar aquestes llistes).
Un expert en el tema, ens diu que pot garantir que per arribar a la solució sempre hi haurà un camí que farà 4 canvis d'estat com a màxim.
En aquestes condicions, quin algorisme de cerca dels estudiats en aquest curs seria el més adequat per solucionar el problema? La cerca en profunditat limitada fixant una profunditat màxima de 4.
d) En un problema s'ha aplicat l'algorisme Hill-Climbing i s'ha arribat a la següent situació: Quin problema hi ha en aquesta situació? Digueu quin nom rep el problema i expliqueu breument en què consisteix.
S'ha arribat a una planura, és a dir, s'ha arribat a un estat del problema pel qual la seva heurística és idèntica a la de tots els seus veïns.
Proposeu dues possibles millores a l'algorisme Hill-Climbing que es poden aplicar per resoldre aquest problema.
• Fer moviments laterals: permetre moviments cap a estats amb heurística igual a l’heurística actual.
• Reinici amb estat inicial aleatori: repetir la cerca amb una altre estat inicial (aleatori) quan s’arriba a un màxim local.
• Selecció probabilística del successor: cada successor té una probabilitat de ser triat (normalment la probabilitat és proporcional a l’heurística).
• Considerar més d’un estat actual: es consideren k estats actuals i es realitzen els càlculs per aquests estats.
3.- (3 PUNTS) En la següent figura, teniu la planta d’una terminal d’un aeroport. El plànol s’ha dividit en àrees identificades per unes coordenades (x,y).
En aquesta terminal s’han de posar 3 màquines de vending i es volen situar de forma que la majoria d'usuaris tinguin una màquina a prop. Les màquines es poden posar a les àrees lliures de la terminal (àrees en blanc al plànol amb un numero a dins). A més, s'ha fet un estudi per saber el número mitjà d'usuaris que es mouen per cada area de la terminal i el resultat el teniu indicat a cada casella de la figura.
Amb aquesta informació, es vol situar les màquines en aquelles àrees tals que la suma de les distàncies entre cada àrea i la màquina més propera sigui la menor possible. Per a tenir en compte el número d'usuaris que es mou en cada àrea, la distància que es calcula per cada casella es vol ponderar (multiplicar) pel nombre mitjà d'usuaris de l'àrea. És a dir, el que es vol aconseguir és situar les màquines en unes posicions tals que la suma (per totes les àrees) de l'expressió: dist x, y , x p , y p U x, y sigui mínima. En aquesta expressió, dist() és la distància Euclídea entre dos punts, (xp,yp) és la posició de la màquina més propera a (x,y) i U(x,y) és el número mitjà d'usuaris que es mouen en l'àrea (x,y).
Dissenyeu la solució a aquest problema resolent les següents qüestions: a) Amb quin tipus de cerca resoldríeu el problema? Amb la cerca local amb objectiu no conegut b) Quin algorisme utilitzaríeu? L'algorisme Steepest Ascent c) Què representarien els estats del problema? Les posicions de les 3 màquines d) Com es representarien els estats del problema? Amb les coordenades (x,y) de cada màquina: E=(x1,y1,x2,y2,x3,y3) e) Quina seria la dimensió de l'espai d'estats del problema? L'espai d'estat té dimensió 6 (els estats del problema queden representats per 6 valors) f) Què representarien els nodes de l'arbre de cerca? Els nodes de l'arbre de cerca representen els estats del problema. Per tant, en aquest problema, els nodes representen la posició de les tres màquines.
g) Què representarien les branques de l'arbre de cerca? Les branques representen els possibles canvis de valor de les coordenades de les màquines.
h) Quin seria el factor de ramificació de l'arbre de cerca? Si en cada pas només permetem incrementar/decrementar en 1 el valor de cada coordenada per separat, tindrem b=6·2=12. (per x1 fem x1+ x i x1- x, per y1 fem y1+ y i y1- y, etc.).
Si permetem modificar a la vegada les dues coordenades de cada màquina tindrem b=3·8=24. (per (x1,y1) fem (x1+ x,y1), (x1- x,y1), (x1,y1+ y), (x1,y1- y), (x1+ x,y1+ y), (x1+ x,y1- y), (x1- x,y1+ y) i (x1x,y1- y), és a dir, per cada màquina surten 8 possibilitats).
Si en cada pas permetem modificar més de dues coordenades, tindrem 3 possibilitats (incrementar, decrementar o deixar igual) per cada coordenada. Per tant, b=3·3·3·3·3·3=36 i) Utilitzaríeu una funció heurística? En cas afirmatiu, digueu quina i doneu la fórmula per calcular-la.
Si. Volem minimitzar la suma de les distàncies entre cada àrea i la màquina més propera amb la distància ponderada pel número mitjà d'usuaris que hi ha a cada àrea: hE dist x, y , x p , y p U x, y x, y x xp 2 y yp 2 U x, y x, y on dist() és la distància Euclídea entre dos punts, (xp,yp) és la posició de la màquina més propera a (x,y) i U(x,y) és el número mitjà d'usuaris que es mouen en l'àrea (x,y).
Una altra forma d'expressar el mateix: hE min dist x, y , x1 , y1 , dist x, y , x 2 , y 2 , dist x, y , x3 , y 3 U x, y x, y 4.- (3 PUNTS) Una companyia local alemanya vol incloure un cercador de vols a la seva pàgina web per permetre que els seus clients puguin trobar la combinació de vols més barata entre les ciutats on opera la companyia. És molt important que el cercador sempre retorni la solució òptima (la més barata) i que el temps que trigui a trobar la solució sigui raonable. Per trobar la solució, es disposa dels preus dels vols que fa la companyia i s'ha definit una heurística que permet estimar el cost aproximat del viatge entre dues ciutats qualsevol a partir de la distància en línia recta entre les ciutats multiplicada per un preu per kilòmetre fix (heurística= (distància en línia recta) x (preu per km)).
Plantejat com un problema de cerca, responeu a les següents qüestions: a) Què representaran els nodes de l'arbre de cerca? Els aeroports b) Què representaran les branques de l'arbre de cerca? Els vols entre dos aeroports c) Quins serien els costos del problema? El preu del bitllet d) Quin algorisme seria el més adequat per resoldre el problema? Algorisme A* A partir del disseny del cercador que acabeu de fer, els directius de la companyia volen que els mostreu com funcionaria l'algorisme triat per trobar la millor combinació de vols en un cas concret. A continuació teniu la matriu que mostra els preus dels vols que opera la companyia: 1-Münster FMO 2-Hamburg HAM 3-Colonia CGN 4-Stuttgart STR 5-Frankfurt FRA 6-Munich MUC 7-Erfurt ERF 8-Berlin SXF 9-Dresde DRS 10-Rostock RLG 1 Münster FMO ---360 2 Hamburg HAM 360 ---340 375 120 250 3 Colonia CGN 4 Sttutgart STR 5 Frankfurt FRA 6 Munich MUC 340 ---- 375 120 150 150 ---170 80 200 250 150 ---150 190 190 170 ---- 7 Erfurt ERF 8 Berlin SXF 80 200 9 Dresde DRS 10 Rostock RLG 120 ---- 95 ------120 95 ---- e) Els directius de la companyia ens demanen que els mostrem quins passos faria l'algorisme que heu triat per trobar la millor combinació de vols entre HAMBURG i DRESDE. Doneu les llistes que generaria l'algorisme fins trobar la solució o fins un màxim de 6 iteracions.
Per a cada camí, doneu el valor de la funció que utilitza l’algorisme per seleccionar els camins a expandir.
Suposeu que el programa elimina els cicles i els camins redundants.
Al fer les llistes de camins, quan elimineu un camí redundant, indiqueu-ho d’alguna forma.
Els cicles, directament no cal posar-los.
Per poder utilitzar l’heurística, se us proporciona el valor de l'heurística (preu aproximat del viatge) entre cada ciutat i la destinació demanada.
Heurística 1-Münster 2-Hamburg 3-Colonia 4-Stuttgart 5-Frankfurt 6-Munich 7-Erfurt 8-Berlin 9-Dresde 10-Rostock 110 95 120 105 90 90 50 40 0 90 Distància (kms) 435 375 475 413 370 360 190 165 0 355 Preu x km 0.25€ 0.25€ 0.25€ 0.25€ 0.25€ 0.25€ 0.25€ 0.25€ 0.25€ 0.25€ Iteració 0 (inicialització llista): HAM 0 + 95 = 95 Iteració 1: HAM-FRA HAM-MUC HAM-CGN HAM-FMO HAM-STR 120 + 90 = 210 250 + 90 = 340 340 + 120 = 460 360 + 110 = 470 375 + 105 = 480 Iteració 2: HAM-FRA-ERF HAM-MUC HAM-FRA-SXF HAM-FRA-STR HAM-FRA-MUC HAM-FRA-CGN HAM-CGN HAM-FMO HAM-STR 120 + 80 + 50 = 250 250 + 90 = 340 120 + 200 + 40 = 360 120 + 150 + 105 = 375 120 + 170 + 90 = 380 (camí redundant: 290 > 250) 120 + 150 + 120 = 390 340 + 120 = 460 (camí redundant: 340 > 270) 360 + 110 = 470 375 + 105 = 480 (camí redundant: 375 > 270) Taula costos parcials FMO – 360 CGN – 340 STR – 375 FRA – 120 MUC – 250 Taula costos parcials FMO – 360 CGN – 340 270 STR – 375 270 FRA – 120 MUC – 250 ERF – 200 SXF – 320 Iteració 3: HAM-MUC HAM-FRA-SXF HAM-FRA-STR HAM-FRA-CGN HAM-FMO 250 + 90 = 340 120 + 200 + 40 = 360 120 + 150 + 105 = 375 120 + 150 + 120 = 390 360 + 110 = 470 Iteració 4: HAM-FRA-SXF HAM-FRA-STR HAM-FRA-CGN HAM-FMO HAM-MUC-FRA HAM-MUC-STR 120 + 200 + 40 = 360 120 + 150 + 105 = 375 120 + 150 + 120 = 390 360 + 110 = 470 250 + 170 + 90 = 510 (camí redundant: 420 > 120) 250 + 190 + 105 = 545 (camí redundant: 440 > 270) Iteració 5: HAM-FRA-STR HAM-FRA-CGN HAM-FRA-SXF-DRS HAM-FMO HAM-FRA-SXF-RLG 120 + 150 + 105 = 375 120 + 150 + 120 = 390 120 + 200 + 120 + 0 = 440 360 + 110 = 470 120 + 200 + 95 + 90 = 505 Iteració 6: HAM-FRA-CGN HAM-FRA-SXF-DRS HAM-FMO HAM-FRA-SXF-RLG HAM-FRA-STR-MUC 120 + 150 + 120 = 390 120 + 200 + 120 + 0 = 440 360 + 110 = 470 120 + 200 + 95 + 90 = 505 120 + 150 + 190 + 90 = 550 (camí redundant: 460> 250) Taula costos parcials FMO – 360 CGN – 270 STR – 270 FRA – 120 MUC – 250 ERF – 200 SXF – 320 Taula costos parcials FMO – 360 CGN – 270 STR – 270 FRA – 120 MUC – 250 ERF – 200 SXF – 320 Taula costos parcials FMO – 360 CGN – 270 STR – 270 FRA – 120 MUC – 250 ERF – 200 SXF – 320 DRS – 440 RLG – 415 Taula costos parcials FMO – 360 CGN – 270 STR – 270 FRA – 120 MUC – 250 ERF – 200 SXF – 320 DRS – 440 RLG – 415 Suposeu ara, que la companyia també vol que el cercador ofereixi un segon mode de cerca per buscar els vols amb menys escales. En aquest segon mode: f) Quin algorisme aplicaríeu? Cerca en amplada g) Utilitzaríeu costos? En cas afirmatiu, quins serien els costos del problema? No h) Utilitzaríeu heurística? En cas afirmatiu, quina? No Una altra possible solució: a) Quin algorisme aplicaríeu? Cerca A* b) Utilitzaríeu costos? En cas afirmatiu, quins serien els costos del problema? Si. Els costos serien el número d'escales (1 en cada branca de l'arbre).
c) Utilitzaríeu heurística? En cas afirmatiu, quina? Si. L'heurística seria una estimació del número d'escales a fer. Es podria calcular utilitzant la distància en línia recta entre dos punts dividida per la distància entre les dues ciutats més allunyades que tenen un vol directe. Aquesta heurística seria admissible, és a dir, garantiria que mai es sobreestimés el número real d'escales a fer.
...