Terceiro Trabalho de Inteligência Artificial / Sistemas Inteligentes

Entrega: 04/05/2015

20 de Abril de 2015

1. Assuma que lhe foi pedido para fazer um programa para planeamento de viagens. O programa é muito simples, mas deve ser capaz de responder questões do tipo:
   • Em que dias da semana há um vôo direto de Londres para Ljubljana?
   • Como posso chegar de Ljubljana a Edinburgh na quinta-feira?
   • Tenho que visitar Milão, Ljubljana e Zurique, começando meu vôo a partir de Londres na terça-feira e retornando para Londres na sexta-feira. Em que seqüência devo visitar estas cidades de forma que eu não tenha mais que um vôo por dia?

   O programa deve estar baseado no banco de dados com informações de vôos abaixo, onde timetable(Place1,PLace2,List_of_flights) representa a informação sobre cada vôo com origem em Place1, destino em Place2 e uma lista (List_of_flights), com informações sobre o vôo, estruturada da seguinte forma: hora de saída/hora de chegada/número do vôo/lista de dias.

   Observação: para utilizar o formato desta base de dados como está, vai precisar redefinir os operadores ``:'' e ``/''. Consulte o manual do Yap em http://www.dcc.fc.up.pt/~vsc/Yap/documentation.html (Appendix A), o manual do swipl em http://www.swi-prolog.org/pldoc/man?predicate=op/3 ou a informação proveniente do livro do Bratko: http://www.cse.unsw.edu.au/~billw/cs9414/notes/prolog/op.html

   timetable(edinburgh,london,
   		[ 9:40/10:50/ba4733/alldays,
   		 13:40/14:50/ba4773/alldays,
   	 	 19:40/20:50/ba4833/[mo,tu,we,th,fr,su]]).
   
   timetable(london,edinburgh,
   		[ 9:40/10:50/ba4732/alldays,
   		 11:40/12:50/ba4752/alldays,
   	 	 18:40/19:50/ba4822/[mo,tu,we,th,fr]]).
   
   timetable(london,ljubljana,
   		[13:20/16:20/ju201/[fr],
   	 	 13:20/16:20/ju213/[su]]).
   
   timetable(london,zurich,
   		[ 9:10/11:45/ba614/alldays,
   		 14:45/17:20/sr805/alldays]).
   
   timetable(london,milan,
   		[ 8:30/11:20/ba510/alldays,
   		 11:00/13:50/az459/alldays]).
   
   timetable(ljubljana,zurich,
   		[11:30/12:40/ju322/[tu,th]]).
   
   timetable(ljubljana,london,
   		[11:10/12:20/yu200/[fr],
   		 11:25/12:20/yu212/[su]]).
   
   timetable(milan,london,
   		[ 9:10/10:00/az458/alldays,
   		 12:20/13:10/ba511/alldays]).
   
   timetable(milan,zurich,
   		[ 9:25/10:15/sr621/alldays,
   		 12:45/13:35/sr623/alldays]).
   
   timetable(zurich,ljubljana,
   		[13:30/14:40/yu323/[tu,th]]).
   
   timetable(zurich,london,
   		[ 9:00/9:40/ba613/[mo,tu,we,th,fr,sa],
   	 	 16:10/16:55/sr806/[mo,tu,we,th,fr,su]]).
   
   timetable(zurich,milan,
   		[ 7:55/8:45/sr620/alldays]).
   

   Seu problema principal é encontrar rotas exatas entre duas cidades num determinado dia da semana. A rota pode ser programada utilizando o predicado: route(Place1,Place2,Day,Route), que satisfaz os seguintes critérios:

   • o ponto de partida da rota é Place1;
   • o ponto de chegada da rota é Place2;
   • todos os vôos devem estar agendados para o mesmo dia da semana (Day);
   • todos os vôos em Route devem estar na relação timetable;
   • deve haver tempo suficiente para transferência entre vôos.

   A rota (variável Route) deve ser uma lista de elementos com o seguinte formato: From-To:número do vôo:Tempo de partida. Por exemplo, a consulta route(edinburgh,ljubljana,Day,Route) poderia retornar a seguinte resposta: Day=fr, Route=[edinburgh-london:ba4733:9:40,london-ljubljana:ju201:13:20].

   Você poderá precisar também dos seguintes predicados auxiliares:

   • flight(Place1,PLace2,Day,Flight_num,Dep_time,Arr_time) que diz que existe um vôo direto (Flight_num) entre Place1 e Place2 no dia da semana Day com tempo de partida Dep_time e tempo de chegada Arr_time.

   • deptime(Route,Time), tempo de partida de Route é Time, onde Route tem o formato: From-To:número do vôo:Tempo de Partida.

   • transfer(Time1,Time2), há uma diferença de pelo menos 40 minutos entre Time1 e Time2 suficiente para fazer a transferência de um vôo para o outro.

   Escreva um programa em Prolog, utilizando a informação dada, que responda às perguntas apresentadas acima.

   Escreva o mesmo programa utilizando uma linguagem (imperativa/procedural) da sua escolha.

2. Escreva um programa em Prolog, utilizando DCG (Definite Clause Grammar), que faça análise de frases em português. Uma parte de uma gramática para o português é dada na Figura 2, onde a primeira sentença fala sobre a estrutura de frases no singular e a segunda fala sobre a estrutura de frases no plural. Esta sintaxe é aceita por Prolog! (consultar ``Definite Clause Grammars'' - DCGs em qualquer livro sobre Prolog). Uma sentença é composta por uma frase nominal seguida por uma frase verbal. Parte das regras que definem uma frase nominal estão representadas pela cláusula frase_nom.

   Defina o restante da gramática (frases verbais, complementos) e um dicionário de palavras (verbos, nomes, adjetivos, etc) e utilize o conjunto de frases da Figura 2 para testar seu programa. Atenção aos apóstrofes que devem ser utilizados quando as palavras nas frases começam com letra maiúscula!

   Figure 1: Subconjunto de estrutura da língua portuguesa

   

   Figure 2: Conjunto de frases para teste (ao alto, frases corretas; embaixo, frases incorretas)

   

   Faça uma pequena modificação no seu programa para que este retorne a estrutura gramatical das frases analisadas. Por exemplo, a consulta sentenca(X,['A',vida,corre],[]) deveria retornar na variável X o valor:

   sent(frase_nom(artigo('A'),substantivo(vida)),frase_verbal(verbo(corre))).

   Observe que a frase do conjunto de exemplos corretos ``O sino bateu na menina'' é sintaticamente correta, mas é semanticamente incorreta. Há técnicas para codificação de gramáticas com semântica associada, porém este tema está fora do escopo desta disciplina e deste trabalho.

   Escreva o mesmo programa utilizando uma linguagem (imperativa/procedural) da sua escolha.

Juntem-se em grupos de 2 elementos, onde um elemento do grupo vai fazer a implementação em Prolog e o outro vai fazer a implementação em outra linguagem. No relatório vão relatar as facilidades/dificuldades de implementação que cada um teve.

Entregar:

1. trabalho escrito com a descrição da implementação.

   Organização do trabalho escrito:

   Introdução

   Descrição/Representação do problema em Prolog

   Descrição/Representação do problema em outra linguagem

   Comentários sobre representação do conhecimento e facilidades/dificuldades de implementação nas duas linguagens

   Comentários Finais e Conclusões

2. enviar o código fonte dos programas, como compilar e formato da entrada para cada problema, isto é, um pequeno manual de como correr os programas (pode ser um 'help' ou 'readme'). Além disso, em que ambiente foi compilado (tipos e versões do SO e da linguagem). Seu programa deve correr na minha máquina (com fedora instalado). Não assuma que eu tenho uma IDE (Integrated Development Environment) de qualquer tipo. O programa deve correr na linha de comando.

   A submissão será através do Moodle UP. Por favor, não inclua caracteres acentuados no nome do ficheiro de submissão.

Todos os trabalhos serão apresentados em data a combinar. Os dois componentes do grupo deverão estar presentes durante a apresentação. Quem nao estiver presente vai ter nota zero!

BÔNUS: integre o seu módulo Prolog em uma interface de sua escolha utilizando a ``foreign interface'' de Prolog. O Yap, por exemplo, permite chamadas a código Java e a código C, assim como pode-se invocar predicados Prolog a partir de Java ou de C (mais informações em http://www.swi-prolog.org/packages/jpl/java_api/index.html - Java, ou em http://www.swi-prolog.org/pldoc/man?section=foreign- C).