Examen solucionado 2015-2016 (2º 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 0
Subido por

Vista previa del texto

UNIVERSITAT AUTÒNOMA DE BARCELONA GESTIÓ AERONÀUTICA - INTEL·LIGÈNCIA ARTIFICIAL CURS 2015-2016 – 2on PARCIAL Cognoms i nom: ___________ SOLUCIONS _____________________________ NIU: ______________ 1.- (2 PUNTS) Una companyia aèria vol disposar d'un sistema intel·ligent per assignar pilot als seus vols. Suposem que la companyia té 8 pilots disponibles i ha d'assignar pilot a 5 vols.
Cada vol es realitza amb un model concret d'avió que requereix que el seu pilot tingui una determinada certificació i un mínim d'hores d'experiència de vol. Per altra banda, els pilots no poden superar un màxim de 30 hores de vol setmanals. A continuació teniu resumida la informació dels vols i els pilots de la companyia.
Vol 1 2 3 4 5 VOLS Certificació Hores de vol requerida requerides C6 3000 C8 2000 C6 1000 C3 700 C2 500 Durada vol (h) 8 5 7 2 1 Pilot 1 2 3 4 5 6 7 8 PILOTS Certificació Hores que té de vol C8 6000 C6 6000 C8 4000 C3 3000 C6 2500 C6 900 C2 600 C3 500 Hores de vol setmana actual 12 25 10 6 24 20 18 2 El sistema que heu de dissenyar ha d’assignar un pilot a cada vol assegurant que: el pilot assignat a un vol, no s'assigna a cap altre vol el pilot assignat a un vol té la certificació requerida per aquell vol el pilot assignat a un vol té una quantitat d'hores de vol igual o superior al número d'hores requerides en el vol el pilot assignat a un vol no superarà el màxim de 30 hores setmanals de vol després de fer el vol A més, per una política d'empresa que no se'ns especifica, al vol 2 no es pot assignar el pilot 3 i al vol 3 no es pot assignar el pilot 5.
Òbviament, a un mateix vol no se li pot assignar més d'un pilot.
Per solucionar el problema, plantegeu-lo com una cerca per a satisfacció de restriccions responent les següents qüestions: a) Què representen i quines són les variables en aquest problema? Les variables representen: els vols Variables = { V1, V2, V3, V4, V5 } b) Què representa i quin és el domini dels valors en aquest problema? Els valors del domini representen: els pilots (identificats pel seu número del 1 al 8) Domini = { 1, 2, 3, 4, 5, 6, 7, 8 } c) Formuleu les restriccions del problema. (Recordeu que si necessiteu utilitzar algun operador o funció, heu de definir-los i indicar què retornen) Definim les següents funcions: CertificacióRequerida(X) – Retorna la certificació requerida per pilotar l'avió que fa el vol X CertificacióPilot(X) – Retorna la certificació que té el pilot X HoresVolRequerides(X) – Retorna el número d'hores de vol requerides per fer el vol X HoresVolPilot(X) – Retorna el número d'hores de vol que té el pilot HoresVolSetmana(X) – Retorna el nº d'hores de vol que ha fet el pilot X a la setmana actual DuradaVol(X) - Retorna la durada en hores del vol X Les restriccions són: i,j Vi ≠ Vj per i ≠ j i CertificacióRequerida(i) = CertificacióPilot(Vi) i ExperiènciaRequerida(i) ≤ ExperiènciaPilot(Vi) i HoresVolSetmana(Vi) + DuradaVol(i) ≤ 30 V2 ≠ 3 V3 ≠ 5 d) Quin algorisme s’aplicaria per resoldre el problema? Digueu quin és i completeu els passos de l’algorisme en l'esquema que teniu a continuació: Algorisme: BACKTRACKING 1. Inicialment: LVA = [ ] LVNA = variables del problema 2. Si LVNA és buida sinó Tenim la solució a LVA Retornar LVA Agafar la 1ª variable de LVNA 3. Per cada valor del domini que podem assignar a la variable, fer: a) Si (es satisfan / no es satisfan) les restriccions: 3.
Posar la variable i el valor a LVA 4.
Continuar assignant les variables de LVNA en el següent nivell de l’arbre (Tornar al pas 2 ) b) Si (es satisfan / no es satisfan) les restriccions: 3.
Abandonar la branca actual (tornar enrere) 4. Si cap branca ha satisfet totes les restriccions No hi ha solució Obs.- En els passos 3a) i 3b) heu de triar entre les dues possibilitats donades: (es satisfan / no es satisfan) LVA = Llista de variables assignades LVNA = Llista de variables no assignades e) Quina millora es pot fer sobre l'algorisme de l'apartat anterior? Digueu quina és i expliqueu breument en què consisteix.
Backtracking amb forward checking - Consisteix en fer comprovacions de les restriccions per avançat (Forward Checking) i eliminar del domini de cada variable els valors que no poden complir les restriccions. Quan el domini d’una variable es queda buit, tornem enrere en l’arbre de cerca (fem backtracking). L’efecte sobre l’algorisme Backtracking és que ens estalviem cercar en branques que no poden portar a una solució i, per tant, l’algorisme és més ràpid.
f) Quina seria la mida màxima (número de nodes del darrer nivell) de l'arbre de cerca que es generaria? (#valors)#variables = 85 2.- (2 PUNTS) Donat el següent sistema basat en regles: Base de Regles: R1: a ^ b o1 R2: a ^ b o2 R3: a ^ b ^ o1 o3 R4: o1 ^ o3 o4 ^ eliminar(o1) R5: o2 ^ o4 sol1 R6: o2 ^ o4 ^ c sol2 R7: o2 ^ b ^ c sol3 S’utilitzen les següents estratègies de resolució de conflictes en l’ordre donat: 1- Refractorietat 2- Especificitat 3- Recència 4- Ordre de les regles Quin resultat donaria el sistema si s’aplica un encadenament endavant amb la següent memòria de treball inicial: MT={a,b,c}? Completeu el quadre següent fins que s'obtingui la primera solució (sol1, sol2 ó sol3). A la columna "Estratègies res. conflictes aplicades" indiqueu quines estratègies de resolució de conflictes heu aplicat.
Pas 1 2 3 4 5 a, b, c R1, R2 a, b, c, o1 R1, R2, R3 Estratègies res.
conflictes Ordre aplicades Ordre de les R1,R2 regles Refr. + Espec.
R3,R2,R1 a, b, c, o1, o3 R1, R2, R3, R4 Refr. + Recència a, b, c, o3, o4 R1, R2 Refractorietat a, b, c, o2, o3, o4 R1,R2,R5,R6,R7 Refr. + Esp. + Rec. R6,R7,R5,R4, R2 Memòria de Treball Regles aplicables Regla aplicada Accions R1 afegir o1 R3 afegir o3 R4,R2,R1,R3 R4 R2,R1 R2 afegir o4 eliminar o1 afegir 02 R6 afegir sol2 3.- (2 PUNTS) Una companyia aèria vol identificar les causes dels retards en les sortides dels seus vols. La companyia es vol centrar només en els retards que són atribuïbles a demores en l'embarcament dels passatgers per tal de millorar aquest procés i poder reduir els retards en la sortida dels seus vols. Els experts en les operacions d'embarcament creuen que la majoria dels retards en l'embarcament estan relacionats amb uns tipus concrets de passatgers. Per això, s'han recollit dades de tots els vols que han tingut un retard de més de 5 minuts sobre l'hora final prevista de l'embarcament de passatgers.
A partir de diverses fonts d'informació, per cada vol amb més de 5 minuts de retard s'ha comptat el número total de passatgers del vol, el número de passatgers que van fer una reserva conjunta (viatgers en grup), número de passatgers menors de 10 anys, número de passatgers amb mobilitat reduïda, número de passatgers que van realitzar compres a l'aeroport i el número de passatgers en trànsit.
Amb aquesta informació, la companyia vol saber els dos tipus de vols que acumulen més retards per tal d'introduir millores en l'operació d'embarcament d'aquests vols i reduir així els retards.
Per solucionar l'encàrrec de la companyia, plantegem el problema com un problema de reconeixement de patrons.
a) Dissenyeu una representació adequada per representar tota la informació del problema. Descriviu totes les seves components. Indiqueu quantes classes hi hauria al problema i què representarien aquestes classes.
La representació adequada seria un espai de característiques amb 6 característiques: número total de passatgers al vol número de passatgers que viatgen en grup (reserves conjuntes) número de passatgers menors de 10 anys número de passatgers amb mobilitat reduïda número de passatgers que han realitzat compres a l'aeroport número de passatgers en trànsit Per tant, l'espai es representarà en un sistema de coordenades de 6 eixos (un eix per a cada característica). En aquest espai: un punt representa la informació d'un vol (només vols amb més de 5 min. de retard) es volen trobar dues classes que correspondrien a dos tipus de vols que acumulen retard es crearan dues particions, una per a cada classe de vol amb retard b) Suposeu que per tal de facilitar la visualització de les dades i reduir el temps de càlcul, es passa a una nova representació de dues dimensions a partir d'agrupar algunes de les característiques i descartar la resta. En aquesta nova representació: el primer eix representa la suma del número de passatgers menors de 10 anys i el número de passatgers amb mobilitat reduïda.
el segon eix representa la suma del número de passatgers que van realitzar compres a l'aeroport i el número de passatgers en trànsit.
En aquesta representació, quin algorisme aplicaríeu per trobar el que vol saber la companyia? Amb quin paràmetre? Es podria aplicar l'algorisme k-means amb k=2 perquè volem trobar 2 classes.
c) Quins són els passos bàsics de l'algorisme triat a l'apartat anterior? 1. Escollir aleatòriament els k punts representants de les k classes a trobar.
2. Repetir Per a cada classe fer: 1. Assignar-li les mostres d’aprenentatge per a les que el representant de la classe és el més proper.
2. Calcular el nou representant de la classe fent el centroide de totes les mostres que han estat assignades a la classe al pas 2.1.
FiPer Fins que les classes quedin estables i cap mostra canvi de classe 3. Retornar el representant de cada classe d) Es podria aplicar aquest algorisme en la representació inicial dissenyada a l'apartat a)? En cas afirmatiu, quines diferències hi hauria respecte l'aplicació en la representació definida a l'apartat b)? En cas negatiu, per què no es podria aplicar? L'algorisme k-means es pot aplicar en un espai de qualsevol dimensió. Per tant, si és podria aplicar a l'espai inicial de 6 dimensions. Els centroides tindrien dimensió 6 i per tant, implicaria fer més càlcul que en l'espai de 2 dimensions.
e) Suposeu que en la representació definida a l'apartat b), les dades recollides per la companyia queden representades com teniu a la figura. Simuleu de forma esquemàtica com serien les 3 primeres iteracions de l'algorisme que heu triat a l'apartat b) amb els valors inicials marcats amb una 'X' i digueu quin seria (aproximadament) el resultat final de l'algorisme. Quina interpretació tindria aquest resultat? INICIALITZACIÓ PAS 1 PAS 2 PAS 3 El resultat final de l'algorisme serien els dos centroides aproximadament a les posicions (15,25) i (25,10) que correspondrien als dos tipus principals de vols amb retard. Aquests dos tipus correspondrien a: vols on viatgen més de 20 persones que es mouen per l'aeroport (compres i en trànsit) vols on viatgen més de 10-15 persones amb mobilitat reduïda i/o nens f) Apart de l'estratègia utilitzada en l'apartat b) per reduir la dimensió de l'espai inicial, quin altre mètode es podria haver utilitzat per reduir la dimensió de l'espai inicial a dues dimensions amb la menor pèrdua possible d'informació? Digueu quin és aquest mètode i enumereu els passos principals.
Es podria haver aplicat l'anàlisi de components principals (Transform. de Karhunen-Loeve). Passos: Construir una matriu X que contingui una mostra d'aprenentatge a cada fila.
Construir la matriu de covariança R de la matriu X: R Calcular els valors propis i els vectors propis de R: 1 1 n 1 XTX 2 c1 d c2 cd Seleccionar els n vectors propis amb valor propi més gran.
Aplicar el canvi de base multiplicant les mostres x de l'espai original per la matriu de canvi de base que conté els n vectors propis triats, un a cada fila: c1 T xi cn yi y1i y ni T 4.- (2 PUNTS) Responeu les següents qüestions referents als sistemes multiagent.
a) Digueu si són certes o falses les següents afirmacions sobre els sistemes multiagent (una pregunta fallada resta 1/2 d'una pregunta correcta): a.1) En un sistema multiagent sempre hi ha un agent central que controla el funcionament global del sistema.
( CERT / FALS ) a.2) En un sistema multiagent, per tal que els agents que el formen puguin interactuar, cal disposar d'un mecanisme comú de comunicació que els permeti compartir informació. ( CERT / FALS ) a.3) En un sistema multiagent es poden obtenir comportaments complexes globals, encara que les estratègies individuals dels agents siguin simples. ( CERT / FALS ) a.4) Els agents que formen un sistema multiagent han de tenir una visió global del sistema i han de tenir accés a tota la informació de l'entorn per a poder aconseguir el seu objectiu. ( CERT / FALS ) a.5) En un sistema multiagent es pot aconseguir una interacció de tipus 'cooperació' a partir d'agents que han estat dissenyats per maximitzar el seu resultat individual (agents "egoistes"). ( CERT / FALS ) b) En l’esquema dels sistemes multiagent que hi ha a continuació, quins són els tres elements que el diferencien de l’esquema d’un agent intel·ligent individual? Definiu-los breument.
Els tres elements que diferencies un sistema multiagent d’un agent intel·ligent individual són els que estan superposats a la figura: múltiples agents, recursos i comunicació.
COMUNICACIÓ MÚLTIPLES AGENTS (I ALTRES OBJECTES DE L’ENTORN) RECURSOS Múltiples agents: en un sistema multiagent hi ha diversos agents compartint el mateix entorn i els mateixos recursos. A l’entorn també hi pot haver altres objectes amb els quals els agents realitzen accions.
Recursos que els agents han de compartir: elements de l’entorn que els agents necessiten per a realitzar les seves funcions (energia, eines, materials, espai, temps,...) Comunicació: mecanisme a través del qual els agents estableixen relacions entre ells.
c) Completeu el quadre amb els tres tipus d’interacció que es donen en els sistemes multiagent segons els objectius i les capacitats dels agents i els recursos de l'entorn: Objectius Recursos Capacitats Compatibles Suficients Suficients Compatibles Suficients Insuficients Compatibles Insuficients Suficients Compatibles Insuficients Insuficients Incompatibles Suficients Suficients Incompatibles Suficients Insuficients Incompatibles Insuficients Suficients Incompatibles Insuficients Insuficients Tipus d’interacció INDIFERÈNCIA COOPERACIÓ COMPETICIÓ d) Enumereu i descriviu breument dos problemes de la gestió aeronàutica als quals es poden aplicar els sistemes multiagent.
Gestió del tràfic aeri - Sistemes que permeten coordinar els plans de vol dels diferents avions que arriben a un aeroport per tal de donar suport al "Flow director" en la tasca de fixar l'hora i la seqüència d'aterratge dels avions.
Prevenció de col·lisions - Sistemes que analitzen els plans de vol dels avions que es mouen en l'espai aeri per tal de detectar conflictes entre les trajectòries planificades pels avions i evitar col·lisions, violacions de reglamentacions de distància entre avions, etc.
5.- (2 PUNTS) En un aeroport internacional en el qual es mouen diàriament milers de passatgers s'està implementant un sistema intel·ligent que ha de predir el nombre de plantes de l'aparcament que cal obrir per absorbir tots els vehicles que hi volen aparcar.
Els experts en mobilitat de l'aeroport recomanen basar-se en dues variables d'entrada: l'ocupació actual de l'aparcament i el nombre de passatges que han de sortir o arribar a l'aeroport en les properes 3 hores. La variable de sortida del sistema ha de ser el nombre de plantes de l'apartament que cal obrir.
Els sistema és un sistema de regles basat en lògica difusa i s'ha dissenyat amb les següents regles: R1: (OCUPACIÓ és R) ^ (NUM_PASSATGERS és B) (NUM_PLANTES és MP) R2: (OCUPACIÓ és R) ^ (NUM_PASSATGERS és M) (NUM_PLANTES és P) R3: (OCUPACIÓ és R) ^ (NUM_PASSATGERS és A) (NUM_PLANTES és P) R4: (OCUPACIÓ és E) ^ (NUM_PASSATGERS és B) (NUM_PLANTES és P) R5: (OCUPACIÓ és E) ^ (NUM_PASSATGERS és M) (NUM_PLANTES és P) R6: (OCUPACIÓ és E) ^ (NUM_PASSATGERS és A) (NUM_PLANTES és G) Les funcions de pertinença als conjunts difusos definits per cadascuna de les variables els teniu a continuació: OCUPACIÓ: Nombre de places d'aparcament ocupades en la part de l'aparcament que està oberta actualment.
Valors lingüístics que pot prendre: Reduïda(R) i Elevada (E).
REDUIDA 1 8000 x 4000 0 ( x) si x 4000 si 4000 si x 8000 8000 ELEVADA x 0 x 4000 4000 1 ( x) si x si 4000 si 4000 x 8000 8000 x NUM_PASSATGERS: Previsió del número de passatgers que passaran per l'aeroport en les properes 3 hores.
Valors lingüístics que pot prendre: Baix(B), Mitjà(M) i Alt(A).
BAIX ( y) 1 10000 y 5000 0 si y si 5000 5000 y 10000 10000 si MITJA ( y ) y 0 y 5000 5000 1 20000 y 5000 0 5000 si y si 5000 y 10000 si 10000 y 15000 si 15000 y 20000 20000 si ALT ( y) y 0 y 15000 5000 1 y 15000 si si 15000 y 20000 si 20000 y NUM_PLANTES: Número de plantes de l'aparcament que cal obrir per absorbir els vehicles en les properes hores. El seu valor pot anar de 0 fins a un màxim de 10 plantes a obrir.
Valors lingüístics que pot prendre: Molt Petit(MP), Petit(P) i Gran(G).
MOLTPETIT ( z) 1 3 z 2 0 si z 1 si 1 z 3 si 3 z PETIT ( z) 0 z 1 2 1 8 z 2 0 si z 1 si 1 z 3 si 3 z 6 si 6 z 8 si 8 GRAN ( z) 0 z 6 2 1 si z si 6 si 6 z 8 8 z z Suposeu que en un moment concret es vol saber si cal obrir noves plantes de l'aparcament. En aquest moment, l'ocupació és de 5000 cotxes a l'aparcament i la previsió d'arribada de passatgers en les 3 properes hores és de 25000 passatgers.
a) Calculeu el grau de compliment de l’antecedent de cada regla amb els valors d’entrada donats.
R1: αR1=min{ 0,75 , 0 } = 0 R2: αR2=min{ 0,75 , 0 } = 0 R3: αR3=min{ 0,75 , 1 } = 0.75 R4: αR4=min{ 0,25 , 0 } = 0 R5: αR5=min{ 0,25 , 0 } = 0 R6: αR6=min{ 0,25 , 1 } = 0.25 b) Representeu gràficament el conjunt difús de la conclusió de les regles amb grau de compliment de l’antecedent diferent de zero i escriviu la funció matemàtica de cadascun d'aquests conjunts difusos.
Regla 3 Regla 6 PETIT GRAN ( z) (z) 0 z 1 2 0.75 8 z 2 0 0 z 6 2 0.25 si si z 1 z 1 si 2.5 si 2.5 z z 6.5 si 6 z si 6 8 z 8 si 6.5 6.5 z 6.5 si z c) Representeu gràficament el conjunt difús global de les conclusions de totes les regles, i escriviu la funció matemàtica que representa aquest conjunt difús.
PETIT ( z) 0 z 1 2 0.75 8 z 2 0.25 si si z 1 z 1 2.5 si 2.5 z 6.5 si 6.5 z 7.5 si 7.5 z d) Segons el sistema, quin és el nombre de plantes que cal obrir? Indiqueu el mètode utilitzat per calcular aquest valor.
Aplicant el mètode de nitidificació del centre del màxim obtenim un valor de z=4.5. Això vol dir que el sistema recomanaria obrir 4 o 5 plantes d'aparcament.
...

Comprar Previsualizar