Examen solucionado 2013-2014 (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 0
Subido por

Vista previa del texto

INTEL·LIGÈNCIA ARTIFICIAL – GESTIÓ AERONÀUTICA CURS 2013-2014 – 1er PARCIAL Cognoms i nom: ____ SOLUCIONS ___________________________________ NIU: _____________ Resoleu les preguntes en l’espai disponible. Feu la pregunta 5 en un full apart.
1.- Responeu de forma breu les següents qüestions: a) Suposeu que volem dissenyar el sistema de pilot automàtic d’un avió. Quins serien els quatre elements bàsics que definirien aquest agent? Criteri d’èxit: Desviació respecte la trajectòria ideal, grau d’estabilitat de l’avió, número d’incidents, etc.
Entorn: Avió, pilots, espai aeri Sensors: Els sensors disponibles a l’avió com altímetre, sensors de pressió, sensors de mesura de la velocitat i direcció del vent, senyals d’alarma, etc.
Actuadors: Els dispositius i mecanismes de l’avió que intervenen al vol: motors, alerons, timó de cua, etc b) Què ens diu el “Principi de la representació del coneixement”? El principi de la representació del coneixement diu que en alguns casos, un cop el problema s'ha descrit amb una representació adequada, el problema està quasi solucionat c) Citeu i expliqueu breument tres de les característiques desitjables en una representació del coneixement.
Una representació del coneixement ha de 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.
completa: ha de permetre descriure tot el que necessitem.
concisa: ha de permetre descriure tot el que necessitem però no més.
computable: vol dir que existeixi un algorisme que la pugui construir, transformar i eliminar.
eficient: ha de permetre actualitzar la informació ràpidament.
d) Suposeu que apliquem l’algorisme A* a un problema usant quatre heurístiques diferents. Digueu quina és la millor heurística que podem aplicar, considerant la següent informació: d(n) és el cost real des del node n fins a la solució h1 és una heurística per a la qual hi ha nodes en què h1(n)>d(n).
h2 és una heurística que mai sobreestima el cost real del problema h3 és una heurística admissible que per tots els nodes n compleix que h2(n)≤h3(n) h4 és una heurística no admissible que per tots els nodes n compleix h4(n)>h3(n) La millor heurística de les quatre és h3. Les heurístiques h1 i h4 no són admissibles i h3 domina h2 (h3(n)≥h2(n) per tots els nodes).
2.- Donats els següents algorismes, identifiqueu a quin algorisme de cerca correspon cadascun: a) ALGORISME: CERCA DE COST UNIFORME 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) de forma que la llista quedi ordenada segons el valor del cost acumulat dels camins 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ó b) ALGORISME: CERCA EN AMPLADA 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 al final de 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ó c) ALGORISME: CERCA GBFS 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) de forma que la llista quedi ordenada segons el valor de la funció heurística h(n) dels camins 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ó d) ALGORISME: CERCA EN PROFUNDITAT 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 al davant de 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.- 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 4 pantalles d'informació i es volen situar de forma que en conjunt siguin visibles des del màxim nombre possible d'àrees de la terminal. Les pantalles es poden posar a les àrees lliures de la terminal (àrees en blanc al plànol), però si es posen en posicions amb altres objectes a prop, les pantalles poden quedar semi-ocultes i ser poc visibles. A més, la informació de les pantalles només es visible fins a una certa distància.
Suposeu que per dissenyar la solució d'aquest problema, disposeu de dues funcions: AreesVisible(P) - Calcula el número d'àrees del plànol de la terminal des d'on és visible la pantalla P Solapament(P1,P2,P3,P4) - Calcula el nombre d'àrees des d'on són visibles dues o més pantalles Per exemple, per les pantalles del gràfic, tindríem: AreesVisible(P1)=16 AreesVisible(P2)=25 Solapament(P1,P2,P3,P4)=6 P1, P2, P3 i P4 són les posicions de les 4 pantalles.
Dissenyeu la solució a aquest problema resolent les següents qüestions. Digueu: 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 4 pantalles d) com es representarien els estats del problema Amb les coordenades (x,y) de cada pantalla: E=(x1,y1,x2,y2,x3,y3,x4,y4) e) quina seria la dimensió de l'espai d'estats del problema L'espai d'estat té dimensió 8 (els estats del problema queden representats per 8 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 quatre pantalles.
g) què representarien les branques de l'arbre de cerca Les branques representen els possibles canvis de valor de les coordenades de les pantalles.
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=8·2=16. (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 pantalla tindrem b=4·8=32.
(per (x1,y1) fem (x1+ x,y1), (x1- x,y1), (x1,y1+ y), (x1,y1- y), (x1+ x,y1+ y), (x1+ x,y1- y), (x1x,y1+ y) i (x1- x,y1- 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·3·3=38 i) utilitzaríeu una funció heurística? En cas afirmatiu, digueu quina i doneu la fórmula per calcular-la.
Si. Volem maximitzar el nombre d'àrees des d'on són visibles les pantalles.
h(E)=AreesVisible(P1)+AreesVisible(P2)+AreesVisible(P3)+AreesVisible(P4)-Solapaments(P1,P2,P3,P4) 4 o bé hE AreesVisible( Pi ) Solapament ( P1 , P2 , P3 , P4 ) on Pi=(xi,yi) i 1 Important: Justifiqueu totes les respostes. Les respostes han de fer referència al problema concret plantejat.
4.- Una companyia aèria vol que dissenyeu un sistema per fer l’assignació de les aeronaus a les rutes comercials que explota des de Barcelona. La companyia opera 8 rutes i disposa de 10 aeronaus.
Tal com es pot veure a la taula que teniu a continuació, per cada ruta es coneix la distància que ha de recórrer l’avió i s’ha fet una estimació del número de passatgers que hi haurà en cada vol. Per altra banda, cada avió té una certa autonomia (kilòmetres que pot volar sense proveir-se de combustible) i una determinada capacitat (número màxim de passatgers).
Aeronaus Rutes Núm avió Autonomia (kms) Capacitat Núm. ruta Distància (kms) Núm. Pax 1 2 : : : : 9 10 800 2500 : : : : 12000 12000 100 100 : : : : 600 600 1 2 : : 7 8 11000 8000 : : 350 475 450 300 : : 90 75 El sistema que heu de dissenyar ha d’assignar una aeronau a cada ruta de forma que: la capacitat de l’aeronau sigui més gran que el nombre estimat de passatgers en els vols de la ruta l’autonomia de l’aeronau sigui més gran que la distància a recórrer en la ruta A més, a la ruta 1 (que corresponen al vol a Singapur) es vol que l’aeronau assignada sigui la 9 o la 10 perquè són les més noves i la companyia vol donar el millor servei en aquesta ruta tan llarga.
Per altra banda, les rutes regionals (6, 7 i 8) es volen fer amb els avions amb menys prestacions, que són els avions del 1 al 5.
Per últim, no es vol assignar la mateixa aeronau a dues rutes diferents.
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... les rutes.
Variables = { R1, R2, ... ,R10 } b) Què representa i quin és el domini dels valors en aquest problema? Els valors del domini representen... les aeronaus.
Domini = { 1, 2, ... , 12 } 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: Autonomia(X) – Funció que retorna l’autonomia de l’aeronau X Capacitat(X) – Funció que retorna la capacitat de l’aeronau X Distància(X) – Funció que retorna la distància de la ruta X Passatgers(X) – Funció que retorna el número de passatgers de la ruta X Les restriccions són: i Capacitat(Ri) > Passatgers(i) i Autonomia(Ri) > Distància(i) R1 ≥ 9 Ri ≤ 5 per 6 ≤ i ≤ 8 (també: i {6,7,8} Ri ≤ 5 ,o també: R6 ≤ 5, R7 ≤ 5, R8 ≤ 5) i,j Ri≠Rj per i≠j d) Quin algorisme s’aplicaria per resoldre el problema? Digueu quin és i dibuixeu de forma esquemàtica, l’arbre de cerca que s’obriria en els tres primers passos de l’algorisme.
S'hauria d'aplicar l'algorisme Backtracking (Backtracking amb Forward Checking trobaria la solució de forma més ràpida).
5.- L'Associació Francesa de Vol Privat (AFVP) vol implementar una eina per planificar els viatges que fan els seus associats. L'eina està orientada a persones que realitzen vols privats amb avions petits que tenen una autonomia limitada i que, per tant, han de parar a proveir-se de combustible si la distància a volar és més gran que l'autonomia de l'avió.
La finalitat de l'eina a implementar és que calculi la ruta més curta (menor distància) entre dos aeroports de la xarxa. La ruta quedarà definida per la seqüència d'aeroports on l'avió s'haurà de proveir de combustible.
Per altra banda, es vol que l'eina sigui ràpida i calculi la ruta en el menor temps possible, però sense renunciar en cap cas a que la ruta calculada sigui la més curta.
a) Quin algorisme implementaríeu per resoldre aquest problema? En respondre, recordeu que l'eina ha d'utilitzar un algorisme que calculi la ruta de menor distància de vol entre l'origen i el destí, en el menor temps que sigui possible.
b) Quins altres algorismes es podrien aplicar per resoldre el problema? Quin/s inconvenient/s tindrien aquests algorismes respecte el que has triat a l'apartat a) ? c) Suposeu que una persona que fa ús d'aquesta aplicació vol fer un viatge des d'Estrasburg a Bordeus amb un avió que té 400kms. d'autonomia. Aleshores, les connexions entre aeroports que es poden fer són entre aeroports separats per menys de 400 kms. En aquest cas concret, la xarxa de vols possibles 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 valor indiquen que les ciutats estan separades per més de 400 kms i per tant no es pot volar entre elles amb l'avió de què disposem.
1-Marsella (MRS) 2-Lió (LYS) 3-Paris (CDG) 4-Bordeus (BOD) 5-Nantes (NTE) 6-Dijon (DIJ) 7-Estrasburg (SXB) 8-Metz (ETZ) 9-Lille (LIL) 1 2 3 4 5 6 7 8 9 Marsella Lió Paris Bordeus Nantes Dijon Estrasburg Metz Lille MRS ---275 LYS 275 ---395 CDG BOD NTE DIJ SXB ETZ LIL 175 260 385 390 280 205 ---275 345 275 ---- ---250 220 395 250 ---130 175 385 390 395 ---345 260 280 205 220 130 ---280 395 280 ---- Doneu les llistes de camins que generaria l’algorisme triat a l'apartat a) en les 3 primeres iteracions per calcular la ruta entre Estrasburg i Bordeus.
Suposeu que el programa elimina 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 el vostre algorisme necessita una heurística, utilitzeu l'heurística de la línia recta fins el destí.
Teniu aquesta informació per cas demanat a la taula següent: 1-Marsella (MRS) 2-Lió (LYS) 3-Paris (CDG) 4-Burdeus (BOD) 5-Nantes (NTE) 6-Dijon (DIJ) 7-Estrasburg (SXB) 8-Metz (ETZ) 9-Lille (LIL) Distància a Bordeus 505 435 500 0 275 510 760 700 700 a) Utilitzaríem l’algorisme A* amb l’heurística de la distància en línia recta. Amb aquesta heurística, com que és admissible, garantim que l’algorisme sempre trobarà la ruta de menor distància. A més, la utilització de l’heurística aconseguim que l’algorisme, en general, sigui ràpid en el càlcul de la solució.
b) Altres algorismes que es podríen utilitzar són: Cerca de cost uniforme: Trobaria la ruta òptima (ruta de menor distància de vol) però en general trigaria molt més que l’A*. La cerca de cost uniforme és molt lenta per problemes amb factor de ramificació alt i costos semblants a les branques.
Cerca Greedy-Best-First-Search (GBFS): En general trigaria menys que l’A* en trobar la solució, però com que en la cerca de la solució no té en compte els costos reals del problema, aquest algorisme no garanteix que sempre es trobés la solució corresponent a la ruta de menor distància de vol.
c) Iteració 0 (inicialització llista): SXB 0 + 760 = 760 Iteració 1: SXB-DIJ SXB-LYS SXB-ETZ 250 + 510 = 760 385 + 435 = 820 130 + 700 = 830 Iteració 2: SXB-LYS SXB-ETZ SXB-DIJ-CDG SXB-DIJ-LIL SXB-DIJ-ETZ SXB-DIJ-LYS 385 + 435 = 820 130 + 700 = 830 250 + 260 + 500 = 1010 250 + 395 + 700 = 1345 250 + 175 + 435 = 860 (camí redundant: 425 > 130) 250 + 220 + 700 = 1170 (camí redundant: 470 > 385) Iteració 3: SXB-ETZ SXB-DIJ-CDG SXB-DIJ-LIL SXB-LYS-MRS SXB-LYS-DIJ SXB-LYS-CDG SXB-LYS-ETZ 130 + 700 = 830 250 + 260 + 500 = 1010 250 + 395 + 700 = 1345 385 + 275 + 505 = 1165 385 + 175 + 510 = 1070 (camí redundant: 560 > 250) 385 + 395 + 500 = 1280 (camí redundant: 780 > 510) 385 + 390 + 700 = 1475 (camí redundant: 775 > 130) Taula costos parcials DIJ – 250 LYS – 385 ETZ – 130 Taula costos parcials DIJ – 250 LYS – 385 ETZ – 130 CDG – 510 LIL – 645 Taula costos parcials DIJ – 250 LYS – 385 ETZ – 130 CDG – 510 LIL – 645 MRS – 660 ...

Comprar Previsualizar