Examen solucionado 2014-2015 (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 7
Fecha de subida 15/06/2017
Descargas 1
Subido por

Vista previa del texto

INTEL·LIGÈNCIA ARTIFICIAL – GESTIÓ AERONÀUTICA CURS 2014-2015 – 1er PARCIAL Cognoms i nom: _____________SOLUCIONS_____________________________ NIU: _____________ Resoleu les preguntes en l’espai disponible. Feu la pregunta 6 en un full apart.
1.- (2 PUNTS) Responeu de forma breu les següents qüestions: a) Digueu si les següents afirmacions són certes o falses. Una pregunta fallada resta 1/2 d'una correcta.
a.1) L'algorisme Hill-climbing s'adapta molt bé a problemes en els que es vol trobar un ajust d'un conjunt de paràmetres en base a la resposta que van tenint aquests. ( CERT / FALS ) a.2) Un problema de satisfacció de restriccions es soluciona normalment amb l'algorisme Backtracking. ( CERT / FALS ) a.3) Es pot aplicar un Forward-Checking a l'algorisme del Backtracking si tenim un problema en el que l'assignació d'una variable permet treure elements dels dominis de les altres variables. (CERT / FALS) a.4) L'algorisme Hill-climbing és complet. ( CERT / FALS ) a.5) L'algorisme Hill-climbing és òptim. ( CERT / FALS ) b) Suposeu que volem dissenyar un vehicle autònom per transportar maletes de la terminal d'un aeroport als avions (agent vist a classe de problemes). Quins serien els quatre elements bàsics que definirien aquest agent? Criteri d’èxit: temps per arribar a l'avió, evitant qualsevol col·lisió amb altres vehicles o amb persones i evitant perdre maletes pel camí Entorn: els carrils marcats a l'aeroport que porten de la terminal als avions, els avions, el personal de l'aeroport, altres vehicles que treballen a l'aeroport, etc.
Sensors: sensor per detectar la posició de l'avió (ex. un receptor d'un senyar emés des de la posició de l'avió), sensor per detectar línies del carril per on es mou (ex. una càmera), sensor per detectar altres vehicles que es mouen (ex. un sensor làser), etc.
Actuadors: motor, les rodes, accelerador, frens, direcció de les rodes, un clàxon per avisar altres vehicles o persones que envaeixin el carril, etc.
c) Doneu les característiques de l'entorn de treball de l'agent de l'apartat anterior segons els criteris.
Observable (total / parcial) parcial Determinista / Estocàstic estocàstic Episòdic / Seqüencial seqüencial Estàtic / Dinàmic dinàmic Discret / Continu continu Mono- / MultiAgent mono-agent d) Suposeu que apliquem l’algorisme A* a un problema usant tres heurístiques diferents. A la taula, teniu el valor que retorna l'heurística per a cada estat del problema. Digueu quina de les 3 és la millor heurística que podem aplicar i per què.
estat d(n) h1(n) h2(n) h3(n) E1 9 8 8 8 E2 5 3 6 3 E3 7 7 9 6 E4 8 4 9 3 E5 10 4 9 4 E6 23 12 22 8 E7 5 3 3 2 E8 2 1 2 1 E9 9 5 10 3 d(n) és el cost real des del node n fins a la solució La millor heurística seria h1 perquè és admissible (no sobreestima el cost real mai) i domina a h3 ja que per tot node n h1(n) h3(n).
2.-(1 PUNT) Suposeu un problema que genera el següent arbre de cerca (amb costos associats a les branques) i sobre el que tenim definida l'heurística que teniu a la taula.
Estat e1 e2 e3 e4 e5 e6 e7 e8 e9 e10 e11 e12 e13 e14 e15 e16 e17 e18 ....
h(n) 9 10 7 12 7 13 5 2 5 4 3 10 6 2 5 2 1 4 ....
En cadascun dels casos següents, digueu quin algorisme generaria les llistes de camins donades per les 5 primeres iteracions: a) Algorisme: Cerca de cost uniforme (CCU) o A* Iteració 0 1 2 3 4 5 Llista de camins ei ei-e2 ei-e1 ei-e1 ei-e2-e5 ei-e2-e6 ei-e2-e5 ei-e1-e3 ei-e2-e6 ei-e1-e4 ei-e2-e5-e10 ei-e1-e3 ei-e2-e6 ei-e1-e4 ei-e2-e5-e10-e18 ei-e2-e5-e10-e17 ei-e1-e3 ei-e2-e6 ei-e1-e4 b) Algorisme: Cerca en amplada Iteració 0 1 2 3 4 5 Llista de camins ei ei-e1 ei-e2 ei-e2 ei-e1-e3 ei-e1-e4 ei-e1-e3 ei-e1-e4 ei-e2-e5 ei-e2-e6 ei-e1-e4 ei-e2-e5 ei-e2-e6 ei-e1-e3-e7 ei-e1-e3-e8 ei-e2-e5 ei-e2-e6 ei-e1-e3-e7 ei-e1-e3-e8 ei-e1-e4-e9 c) Algorisme: Cerca GBFS Iteració 0 1 2 3 4 5 Llista de camins ei ei-e1 ei-e2 ei-e1-e3 ei-e2 ei-e1-e4 ei-e1-e3-e8 ei-e1-e3-e7 ei-e2 ei-e1-e4 ei-e1-e3-e8-e14 ei-e1-e3-e7 ei-e1-e3-e8-e13 ei-e2 ei-e1-e4 ei-e1-e3-e8-e14-eo ei-e1-e3-e7 ei-e1-e3-e8-e13 ei-e2 ei-e1-e4 d) Algorisme: Cerca en profunditat Iteració Llista de camins ei ei-e1 ei-e2 ei-e1-e3 ei-e1-e4 ei-e2 ei-e1-e3-e7 ei-e1-e3-e8 ei-e1-e4 ei-e2 ei-e1-e3-e8 ei-e1-e4 ei-e2 ei-e1-e3-e8-e13 ei-e1-e3-e8-e14 ei-e1-e4 0 1 2 3 4 5 ei-e2 3.-(1 PUNT) Ompliu la següent taula d'anàlisi dels algorismes de cerca respecte els criteris d'optimalitat i completesa. Si hi ha algun factor que condiciona la resposta, indiqueu-ho.
Cerca en amplada Cerca en profunditat limitada Complet ? SI 1 NO Òptim ? SI 4 1 Si el factor de ramificació és finit, menor número de branques Cerca de cost uniforme SI 1,2 NO 2 Si els costos són positius, Cerca GBFS SI 3 SI 3 Si s'eliminen cicles, NO 4 Si òptim vol dir 4.-(2 PUNTS) En un nou aeroport que està a punt d’iniciar la seva activitat, tenim encomanada la tasca de fer l’assignació dels 20 taulells de facturació de què disposa la instal·lació entre les 6 companyies que operaran a l’aeroport inicialment.
Les companyies són: New Airways, Europe Express, Air BCN, QLM, LuxAir, Global France Per operar en el nou aeroport, les companyies han imposat una sèrie de condicions que s’han de satisfer en l’assignació que proposem: Totes les companyies volen tenir almenys dos taulells assignats.
Air BCN i QLM en volen més i volen un mínim de 4 taulells assignats LuxAir és la companyia de més volum de passatgers i vol 6 taulells New Airways i Europe Express no volen estar a tocar i exigeixen que hi hagi almenys 4 taulells entre les seves zones.
Es decideix resoldre el problema plantejant-lo com un problema per a satisfacció de restriccions: a) Què representen i quines són les variables en aquest problema? Les variables representen... els taulells.
Variables = { T1, T2, ... , T20} b) Què representa i quin és el domini dels valors en aquest problema? Els valors del domini representen... les companyies.
Domini = {1,...,6} on 1 correspon a New Airways, 2 a Europe Express, 3 a AirBCN, 4 a QLM, 5 a LuxAir i 6 a Global France c) Formuleu les restriccions del problema. (Si necessiteu utilitzar algun operador o funció, definiu-los i indiqueu què retornen) i 1≤i≤6 TaulellsAssignats(i) ≥ 2 i 3≤i≤4 TaulellsAssignats(i) ≥ 4 TaulellsAssignats(5)=6 i,j 1 ≤ i ≤ 20 , 1 ≤ j ≤ 20 Ti=1 , Tj=2 |i-j| ≥ 5 TaulellsAssignats(X) – Funció que retorna el número de taulells assignats a la companyia X (és a dir, el número de variables que tenen assignat el valor X) d) Quin algorisme s’aplicaria per resoldre el problema? S'hauria d'aplicar l'algorisme Backtracking (Backtracking amb Forward Checking trobaria la solució de forma més ràpida).
e) Quina seria la mida màxima (número de nodes del darrer nivell) de l'arbre de cerca que es generaria? La mida màxima de l'arbre de cerca seria (# valors)# variables = 620 5.-(2 PUNTS) En un aeroport, hem de distribuir els espais que ocuparan els serveis als passatgers dins d’una nova terminal. Un d’aquests serveis són les pantalles amb la informació dels vols. El plànol de la terminal s’ha dividit en àrees tal com es veu a la figura. Cadascuna d’aquestes àrees s’identifica per unes coordenades (x,y).
Es volen posar 3 pantalles d’informació i volem posar-les de tal forma que la suma de les distàncies (al quadrat) des de qualsevol àrea de la terminal a la pantalla més propera sigui la menor possible. La posició de les pantalles queda definida per les coordenades (x,y) de l’àrea en la que estan situades.
Plantegeu la solució a aquest problema resolent les següents qüestions: Important: Justifiqueu totes les respostes. Les respostes han de fer referència al problema concret plantejat.
a) Quin tipus de cerca és el més adequat per resoldre el problema? Quin algorisme s’aplicaria per resoldre’l? La cerca local. Aquest és un problema d’optimització en el qual no hi ha un objectiu final determinat. Per tant, s'utilitzaria l'algorisme Steepest Descent (versió de l'algorisme Steepest Ascent quan es busca un mínim de la funció heurística).
b) Què representaran els nodes en l’arbre de cerca? El nodes representen les posicions de les 3 pantalles. Els estats del problema corresponen a les coordenades de les posicions de les pantalles (xp1,yp1,xp2,yp2,xp3,yp3).
c) Què representaran les branques en l’arbre de cerca? Les branques representen modificacions en els valors de les coordenades de les posicions de les pantalles: sumar o restar 1 al valor d’una o més coordenades de les pantalles d) Quin seria l'estat inicial del problema? L'estat inicial del problema correspondria als valors inicials que donéssim a les coordenades de les 3 pantalles. Una forma de d'assignar aquests valors inicials a les posicions (xp1,yp1), (xp2,yp2) i (xp3,yp3) seria donar valors aleatoris.
e) Quin seria l'estat objectiu del problema? L'estat objectiu del problema no és conegut. D'entrada no sabem a quina posició final han d'anar col·locades les pantalles perquè això és el que estem buscant.
f) Quina serà la dimensió de l’espai d’estats del problema? La dimensió de l’espai d’estat és 6 perquè tenim 2 coordenades per cadascuna de les 3 pantalles. Els estats del problema estan formats per 6 valors que volem ajustar.
g) Quin serà el factor de ramificació de l’arbre? Si en cada pas només permetem incrementar/decrementar en 1 el valor de cada coordenada per separat, tindrem b = 4 x 3 = 12. (per xp1 fem xp1+ x i xp1- x, per yp1 fem yp1+ y i yp1- y, etc.).
Si permetem modificar alhora les dues coordenades de cada pantalla tindrem b = 8 x 3 = 24.
(per (xp1,yp1) fem (xp1+ x,yp1), (xp1- x,yp1), (xp1,yp1+ y), (xp1,yp1- y), (xp1+ x,yp1+ y), (xp1+ x,yp1- y), (xp1- x,yp1+ y) i (xp1- x,yp1- y), és a dir, per cada pantalla 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 h) Utilitzaríeu una funció heurística? En cas afirmatiu, digueu quina i doneu la fórmula per calcular-la.
Si que utilitzaríem una heurística.
L’heurística del problema (el valor que volem minimitzar) seria la suma de les distàncies al quadrat de totes les posicions de la terminal a la pantalla més propera.
La fórmula corresponent seria: h( E ) dist xi , y i , x p , y p i 2 xi xp 2 yi yp 2 2 i on (xp,yp) són les coordenades de la pantalla més propera a la casella (xi,yi).
Una altra forma d'escriure la fórmula de l'heurística: h( E ) min(dist xi , y i , xp1 , yp1 , dist xi , y i , xp 2 , yp 2 , dist xi , y i , xp3 , yp3 ) i 2 6.-(2 PUNTS) Indonesia Taxi Flight (ITF) és una empresa de taxis aeris que opera entre els aeroports de les illes d'Indonèsia per proporcionar transport ràpid per desplaçar-se entre dos punts qualsevol de la xarxa d'aeroports de l'arxipèlag. ITF disposa d'avions amb una autonomia màxima de 1500km. Per tant, per qualsevol viatge on els aeroports estiguin a més de 1500km de distància, l'avió haurà de fer una o més escales. Així, la xarxa de vols que pot fer ITF queda definida per la següent matriu de distàncies: 1-Yakarta (HLP) 2-Surabaya (SUB) 3-Padang (PDG) 4-Medan (MES) 5-Pekanbaru (PKU) 6-Pontianak (PNK) 7-Manado (MDC) 8-Denpasar (DPS) 9-Ambon (AMQ) 10-Jayapura (DJJ) 1 2 3 4 5 6 7 8 9 10 Yakarta Surubaya Padang Medan Pekanbaru Pontianak Manado Denpasar Ambon Jayapura HLP SUB 660 PDG 930 MES 1420 PKU 960 MDC DPS 965 315 AMQ DJJ 660 930 1420 960 745 540 205 460 890 540 205 1000 PNK 745 890 1000 1250 880 965 315 460 1250 880 1165 685 1500 1165 685 1500 1400 1400 Per poder triar sempre la ruta que impliqui recórrer menor distància, ITF vol que li dissenyem un agent calculador de rutes òptimes. L'enginyer principal del projecte no té clar si utilitzar l'algorisme A* o GBFS. És per això que ens demana ajuda. Concretament, l'enginyer vol saber: a) Quin seria el resultat a l'acabar la 3ª iteració de l'algorisme A* si es vol calcular la ruta entre Padang i Manado? b) Quin seria el resultat a l'acabar la 3ª iteració de l'algorisme GBFS si es vol calcular la ruta entre Padang i Manado? En els dos casos: Suposeu que s'eliminen els cicles i, per tant, no els poseu a les llistes.
Per a cada camí, doneu el valor de la funció que utilitza l’algorisme per seleccionar els camins a expandir. Indiqueu els passos de càlcul per arribar al valor que doneu.
Si l'algorisme triat genera camins redundants, indiqueu quins són i elimineu-los.
Si necessiteu una funció heurística, utilitzeu la que teniu a la taula de la dreta (distància en línia recta a la destinació) 1-Yakarta (HLP) 2-Surabaya (SUB) 3-Padang (PDG) 4-Medan (MES) 5-Pekanbaru (PKU) 6-Pontianak (PNK) 7-Manado (MDC) 8-Denpasar (DPS) 9-Ambon (AMQ) 10-Jayapura (DJJ) Distància a Manado 2175 1660 2740 2920 2605 1735 0 1555 685 1820 c) Un altre dels enginyers del projecte proposa utilitzar l'algorisme de cerca en amplada. Li recomanaríeu utilitzar aquest algorisme? Per què? No, perquè l'algorisme de cerca en amplada no és òptim si els costos de les branques de l'arbre de cerca són diferents. A més, en general, l'algorisme de cerca en amplada trigarà molt més que els algorismes de cerca informada a trobar la solució.
d) En general, quin algorisme li recomanaríeu utilitzar en la implementació de l'agent calculador de rutes? Per què? L'algorisme A* perquè amb l'heurística de la distància en línia recta a l'objectiu (és una heurística admissible) aquest algorisme garanteix que sempre trobarà el camí amb menor distància recorreguda (camí òptim).
a) Algorisme A* Iteració 0 (inicialització llista): PAD 0 + 2740 = 2740 Iteració 1: PDG-PNK PDG-PKU PDG-HLP PDG-MES 1000 + 1735 = 2735 205 + 2605 = 2810 930 + 2175 = 3105 540 + 2920 = 3460 Iteració 2: PDG-PKU PDG-HLP PDG-MES PDG-PNK-SUB PDG-PNK-DPS PDG-PNK-HLP PDG-PNK-PKU PDG-PNK-MES 205 + 2605 = 2810 930 + 2175 = 3105 540 + 2920 = 3460 1000 + 890 + 1660 = 3550 1000 + 1165 + 1555 = 3720 1000 + 745 + 2175 = 3920 (camí redundant: 1745 > 930) 1000 + 880 + 2605 = 4485 (camí redundant: 1880 > 205) 1000 + 1250 + 2920 = 5170 (camí redundant: 2250 > 540) Iteració 3: PDG-PKU-PNK PDG-HLP PDG-PKU-HLP PDG-MES PDG-PNK-SUB PDG-PKU-MES PDG-PNK-DPS 205 + 880 + 1735 = 2820 (camí redundant: 1005 > 1000) 930 + 2175 = 3105 205 + 960 + 2175 = 3340 (camí redundant: 1165 > 930) 540 + 2920 = 3460 1000 + 890 + 1660 = 3550 205 + 460 + 2920 = 3585 (camí redundant: 665 > 540) 1000 + 1165 + 1555 = 3720 b) Algorisme GBFS Iteració 0 (inicialització llista): PDG 2740 Iteració 1: PDG-PNK PDG-HLP PDG-PKU PDG-MES 1735 2175 2605 2920 Iteració 2: PDG-PNK-DPS PDG-PNK-SUB PDG-HLP PDG-PNK-HLP PDG-PKU PDG-PNK-PKU PDG-MES PDG-PNK-MES 1555 1660 2175 2175 2605 2605 2920 2920 Iteració 3: PDG-PNK-DPS-AMQ PDG-PNK-SUB PDG-PNK-DPS-SUB PDG-HLP PDG-PNK-HLP PDG-PNK-DPS-HLP PDG-PKU PDG-PNK-PKU PDG-MES PDG-PNK-MES 685 1660 1660 2175 2175 2175 2605 2605 2920 2920 Taula costos parcials HLP – 930 MES – 540 PKU – 205 PNK – 1000 Taula costos parcials HLP – 930 MES – 540 PKU – 205 PNK – 1000 SUB – 1890 DPS – 2165 Taula costos parcials HLP – 930 MES – 540 PKU – 205 PNK – 1000 SUB – 1890 DPS – 2165 ...