Examen solucionado 2012-2013 (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 5
Fecha de subida 15/06/2017
Descargas 0
Subido por

Vista previa del texto

INTEL·LIGÈNCIA ARTIFICIAL – GESTIÓ AERONÀUTICA CURS 2012-2013 – 1er PARCIAL Cognoms i nom: ____________________________________________________ Resoleu les preguntes en l’espai disponible. Feu la pregunta 6 en un full apart.
1.- Definiu breument els següents components bàsics d’un agent intel·ligent i completeu l’esquema que teniu a continuació: Criteri d’èxit: És una mesura o avaluació del rendiment de l’agent.
Actuadors: Dispositius a través dels quals l’agent pot realitzar operacions sobre l’entorn per tal de fer la seva tasca. (Ex.-Pantalles, braços robòtics, motors, etc.) Sensors: Dispositius a través dels quals l’agent pot obtenir informació de l’entorn que és útil per fer la seva tasca. (Ex.-Teclats, sensors de temperatura, de proximitat, etc.) Entorn: Medi on l’agent realitza la seva tasca. L’entorn inclou l’espai físic on l’agent desenvolupa la seva tasca i tots els elements (persones, objectes, entitats, etc) amb els que interactua.
Percepcions: Informació que l’agent rep de l’entorn a través dels seus sensors.
Accions: Operacions sobre l’entorn que l’agent pot dur a terme amb els seus actuadors per tal de fer la seva tasca.
2.- Completeu els passos que falten de l’algorisme bàsic de cerca: Algorisme bàsic de CERCA 1. Posar l’estat inicial com a primer camí de la llista 2. Fins que el primer camí de la llista arribi a l’objectiu o la llista quedi buida fer: 2.a) Treure el primer camí de la llista 2.b) Expandir el camí obtingut al pas anterior 2.c) Eliminar els cicles dels camins obtinguts en expandir 2.d) Inserir a la llista els camins obtinguts a 2.c) 3. Si la llista té camins retornem el primer camí de la llista 4. Sinó (si la llista s’ha quedat buida), vol dir que no hi ha solució 3.- 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) Cerca en amplada b) Cerca en profunditat c) Cerca de cost uniforme d) Cerca en profunditat limitada (prof. màx. = 4) Solució trobada: A – [ei-e1-A] Núm. nodes avaluats: 9 Solució trobada: D – [ei-e1-e3-e6-f1-D] Núm. nodes avaluats: 9 Solució trobada: B – [ei-e2-e5-B] Núm. nodes avaluats: 11 / 12 (*) Solució trobada: C – [ei-e1-e3-e7-C] Núm. nodes avaluats: 10 (*) depèn de com s’ordenen els camins [ei-e2-e5-B] i [ei-e2-e4] que tenen cost=12 4.- Donat el següent arbre de joc corresponent a un problema de cerca amb adversaris, teniu les fulles etiquetades amb el valor de l’heurística.
a) Apliqueu l’algorisme Minimax sobre l’arbre (poseu a cada node el valor que donaria el Minimax) i digueu quina solució final retornaria: b) Si a l’arbre anterior s’aplica el minimax amb poda alfa-beta, quins nodes es podarien ( no s’avaluarien)? (Senyaleu-ho sobre la figura, o bé identifiqueu amb lletres els nodes i doneu aquí la llista de nodes no avaluats) Marcats amb ‘X’ a la figura.
5.- 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 fer reformes i hem de decidir la ubicació idònia dels tres lavabos que tindrà la terminal. Els lavabos han d’anar a la zona reservada pels diferents serveis als passatgers (zona gris a la part superior del plànol).
Els tres lavabos s’han de situar de tal forma que els passatgers de la terminar sempre tinguin un lavabo relativament pròxim. Per aconseguir-ho, volem que la ubicació dels 3 lavabos sigui tal que la suma de les distàncies des de qualsevol àrea de la terminal al lavabo més proper sigui el més petita possible.
Plantegeu la solució a aquest problema resolent les següents qüestions: a) Quin tipus de cerca és el més adequat per resoldre el problema? I quin algorisme? La cerca local amb objectiu no conegut. L’algorisme seria Steepest Descent (Steepest Ascent per buscar mínims de la funció heurística).
b) Què representaran els nodes en l’arbre de cerca? Com els representarem? Els nodes representaran les posicions dels lavabos a situar. Com que els lavabos només es poden situar a l’espai reservat (zona de serveis), només hem de trobar la coordenada x on ha d’anar cada lavabo. Per tant, cada node serà una tripleta (x1,x2,x3) on xi és la coordenada x del lavabo i.
c) Què representaran les branques en l’arbre de cerca? Les branques representaran els possibles canvis de valor de les coordenades x dels lavabos.
d) Quina serà la dimensió de l’espai d’estats del problema? Els estats (tripletes x1,x2,x3) tenen dimensió 3. Per tant, l’espai d’estats tindrà dimensió 3.
e) Quin serà el factor de ramificació de l’arbre? (b=factor de ramificació) Si en cada pas només permetem incrementar/decrementar en 1 el valor de cada coordenada per separat, tindrem b=3·2=6. Si permetem modificar més d’una coordenada a la vegada, tindrem b=3·3·3=27.
Si en cada pas permetem increments/decrements en 1 i 2 de cada coordenada per separat, tindrem b=3·4=12. Si permetem modificar més d’una coordenada a la vegada, b=5·5·5=125.
f) Quina serà la funció heurística del problema? L’heurística del problema (el valor que volem minimitzar) és la suma de les distàncies de totes les posicions de la terminal al lavabo més proper.
La fórmula corresponent seria: h( E ) dist xi , y i , x L ,1 i A xi xL 2 yi 1 2 i A on (xL,1) són les coordenades del lavabo més proper a la casella (xi,yi) i A és el conjunt de totes les caselles de l’àrea interior de la terminal.
6.- Una companyia aèria americana utilitza els seus avions per fer enviaments de documentació confidencial entre les seves oficines als diferents aeroports on opera. Per fer aquests enviaments de forma eficient, vol fer un programa que li permeti trobar quina és la combinació de vols que dóna el viatge més curt (menor distància recorreguda). La seva xarxa de vols queda definida per la següent matriu de distàncies, on cada número indica la distància en kilòmetres entre les ciutats de la fila i la columna corresponents. Les caselles sense cap número indiquen que la companyia no vola entre les ciutats d’aquella fila i columna.
1 NYC 1-Nova York (NYC) 2-Miami (MIA) 3-Chicago (CHI) 4-Atlanta (ATL) 5-Dallas (DFW) 6-Phoenix (PHX) 7-Denver (DEN) 8-Minneapolis (MSP) 9-Seattle (SEA) 10-San Francisco (SFO) 11-Los Angeles (LAX) 1750 1150 1200 2 MIA 1750 3 CHI 1150 970 950 4 ATL 1200 970 950 5 DFW 6 PHX 7 DEN 1400 1700 1050 950 9 SEA 10 SFO 11 LAX 580 1150 1150 1700 8 MSP 1400 1050 600 950 1550 2530 1100 580 1550 2530 600 1100 550 550 El programa utilitzarà la distància en línia recta com heurística per trobar la ruta a seguir.
Es vol trobar una ruta per anar de Los Angeles a Chicago.
a) Suposeu que el sistema utilitza l’algorisme A* amb eliminació de camins redundants.
Doneu les llistes de camins que generaria l’algorisme A* en les 3 primeres iteracions per calcular la ruta entre Los Angeles i Chicago. Quan elimineu algun camí redundant, indiqueu-ho d’alguna forma.
b) Suposeu que el sistema utilitza l’algorisme GBFS. Doneu les llistes de camins que generaria l’algorisme GBFS en les 3 primeres iteracions per calcular la ruta entre Los Angeles i Chicago.
En els dos casos: 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, per tant, no els poseu a les llistes.
Per poder calcular l’heurística, se us proporciona la distància en línia recta de totes les ciutats de la xarxa al destí Chicago (veure taula adjunta).
c) Si els responsables de l’empresa volen garantir que la ruta que calculi el sistema sempre sigui la que impliqui recórrer menor distància, quin algorisme implementaríeu al sistema? Justifiqueu la resposta.
1-Nova York (NYC) 2-Miami (MIA) 3-Chicago (CHI) 4-Atlanta (ATL) 5-Dallas (DFW) 6-Phoenix (PHX) 7-Denver (DEN) 8-Minneapolis (MSP) 9-Seattle (SEA) 10-San Francisco (SFO) 11-Los Angeles (LAX) Distància a Chicago 1150 1915 0 950 1290 2330 1475 580 2790 2985 2805 a) Iteració 0 (inicialització llista): LAX 0 + 2805 = 2805 Iteració 1: LAX-PHX LAX-SFO 600 + 2330 = 2930 550 + 2985 = 3535 Iteració 2: LAX-PHX-DEN LAX-PHX-DFW LAX-SFO Iteració 3: LAX-PHX-DFW LAX-SFO LAX-PHX-DEN-DFW LAX-PHX-DEN-ATL LAX-PHX-DEN-SFO 1550 + 1475 = 3025 2000 + 1290 = 3290 550 + 2985 = 3535 2000 + 1290 = 3290 550 + 2985 = 3535 2600 + 1290 = 3890 (camí redundant: 2600 > 2000) 3250 + 950 = 4200 3100 +2985 = 6085 (camí redundant: 3100 > 550) b) Iteració 0 (inicialització llista): LAX 2805 Iteració 1: LAX-PHX LAX-SFO 2330 2985 Iteració 2: LAX-PHX-DFW LAX-PHX-DEN LAX-SFO Iteració 3: LAX-PHX-DFW-ATL LAX-PHX-DEN LAX-PHX-DFW-DEN LAX-SFO 1290 1475 2985 950 1475 1475 2985 c) Caldria implementar l’algorisme A* que garanteix que trobarà la solució òptima sempre que l’heurística utilitzada sigui admissible. En aquest cas, l’heurística triada és admissible (la línia recta és la distància més curta entre dos punts) i, per tant, l’algorisme A* sempre trobarà la ruta més curta entre l’origen i el destí.
Recordeu: Una heurística és admissible si ens assegura que mai sobre-estima el cost que falta per arribar a la solució.
...