Programação

  • Geral

    Benvindos ao curso de Inteligência Artificial

    Começaremos as aulas nesta próxima quarta-feira, 7 de agosto, e usaremos a sala MZ-02, que fica no piso superior, Bloco B (o bloco mais novo onde ficam os laboratórios). Esta sala fica logo defronte de quem sai da passarela que liga o Bloco A ao Bloco B e é a primeira sala à direita de quem entra neste corredor. A primeira sala à esquerda, antes de entrar no corredor é o D-Lab, ou Design Lab, o meu laboratório de pesquisa. 

    Faremos algumas pequenas mudanças com relação ao curso do ano passado, começando por enriquecer a bibliografia com um livro-texto adicional. Mas, o importante é que continuamos com o objetivo de estudar os conceitos da Intelligência Artificial e da inteligência de máquina, um tópico importante tanto do ponto de vista dos processos de automação como em todos os procesos que geralmente envolvem pessoas e máquinas. 

    Começaremos a discutir isso já nesta primeira aula. 

  • Introdução



    Nesta primeira aula apresentaremos a estrutura do curso como um todo, livro texto, e a forma de avaliação. Faremos um breve histórico sobre o interesse geral da academia e de todo o resto da humanidade no conceito de inteligência e sua reprodução por máquinas e mecanismos. Introduziremos o conceito de agente inteligente, que é fundamental para a inteligência de máquina, seja embarcada ou distribuída em sistemas inteligentes. 

    O curso está dividido em uma parte teórica e uma parte prática. Gostaríamos de ter a capacidade de desenvolver pequenos programas inteligentes (lidaremos com software somente). A parte prática será trabalhada via este site, embora algumas das aulas "teóricas" tratarão de exercícios, exemplos práticos, e programas. Entretanto, não será possível inserir um curso de programação lógica em uma disciplina com dois créditos apenas. Portanto usaremos tutoriais e uma referência bibliográfica de apoio (Programming in Prolog, W. F Clocksin, C.S. Mellish, Springer, 2003). Um tutorial online para programação será usado (veja link abaixo).

    Para programação, uma versão online do SWI Prolog será usado (ver link abaixo). Com isso eliminaremos problemas de instalação, particularidades com sistemas operacionais, etc.

  • Resolução de problemas simples com regras



    Reunião no Dartmouth College para discutir a "inteligência Artificial".


    Nesta aula vamos começar a tratar da resolução de problemas de forma inteligente. A idéia é capacitar máquinas (computadores) para resolver problemas, uma capacidade normalmente associada a sistemas (humanos) inteligentes. Já vimos as limitações que esta inteligência de máquina pode ter, mas ainda assim, seria uma evolução tecnológica considerável ter sistemas capazes de fazer planos, aprender analizar padrões ou dar apoio à decisão. Ao invés de introduzir este tópico de maneira formal vamos abordá-lo (inicialmente) de forma simples com alguns problemas que podem ser tratados com "regras", agindo sobre uma base de fatos.

    Podemos sofisticar o nível de abstração destas regras (a distância para os "fatos") e também o número de regras tornando os programas mais complicados e mais "inteligentes".  Mas é ainda possível ver as limitações e também as possibilidades que surgem para aplicações, especialmente em automação. Aproveitamos para introduzir a linguagem Prolog e exercitar a sua aplicação no Swish SWI Prolog.

    Terminaremos propondo um avanço na forma de resolver problemas que nos aproxima ainda mais da modelagem estado-transição (ou dos "transition systems"). Novamente vamos entrar neste assunto de forma prática para colocar mais tarde a abordagem formal. A aplicação no momento seria um sistema automático para jogos.


    Cerca de 30% da emissão de passagens em companhias aéreas é feita usando Prolog.

    Uma matéria divulgada pela SICStus Prolog, que faz um ambiente de programação Prolog onde se pode produzir programas de interesse de mercado. Veja o link a abaixo...

  • Métodos e paradigmas para resolução de problemas



    Vamos agora avançar um pouco no entendimento dos tipos principais de problema e nos métodos para trata-los. A diferença entre um sistema algorítmico normal e um sistema inteligente está nos métodos de resolução de problemas e notadamente (no nível de abordagem deste curso) na capacidade de automatizar a resolução de problemas. Vamos portanto focar nos aspectos conceituais desta automação e nos algoritmos de apoio, o que começa com os algoritmos de busca. Veremos que a ligação entre os métodos de aplicação da inteligência artificial na engenharia (especialmente planning) e a base conceitual da IA começa pelos algoritmos de busca e sobre a estrutura de árvores, que por sua vez podem ser implementadas na forma de lista (a estrutura de dados mais importante no Prolog). Os algoritmos de busca sobre árvores serão explorados na aula que vem. 

    Devemos nos preparar para o primeiro trabalho em grupo, e portanto a turma deverá se dividir em grupos de quatro ou cinco pessoas até a aula do dia 28/08. Também colocaremos um novo chat para que todos possam colocar as dúvidas e também a formação dos grupos.  

  • Resolução de problemas por humanos e por máquinas




    Vamos retornar à nossa discussão sobre resolução de problemas, agora considerando a diferença entre a resolução de problemas por humanos e por máquinas. Aproveitaremos então para introduzir os sistemas baseados em regras, e os sistemas especialistas agora avançando na discussão sobre os métodos básicos de inferência. Um sistema especialista é composto por três elementos básicos: a interface com o usuário, a base de conhecimento e a máquina de inferência. A primeira não será objeto deste curso, embora seja muito importante e às vezes crucial para o sucesso comercial de várias aplicações de IA, como mostraremos na aula. A segunda é justamente o objeto da discussão na aula de hoje. A terceira, será parcialmente delegada para a máquina prolog e para a programação, e será discutida com mais detalhes mais adiante.

    Nas aulas seguintes discutiremos a representação de conhecimento, e em seguida os algoritmos de busca e busca informada. Em paralelo discutiremos as técnicas de programação em Prolog e a implementação do primeiro trabalho.

    Como leitura suplementar acrescentamos um artigo de Allen Newel e Herbert Simon sobre as diferenças entre "human problem solving and machine problem solving". Os que quiserem explorar mais este tema são fortemente aconselhados a ler este artigos. Mesmo para os demais o artigo é muito interessante e instigante e complementa com mais detalhes o tópico de discussão desta aula.


  • Resolução de problemas por máquinas: Algoritmos de busca




    Na aula passada discutimos conceitualmente as estratégias de resolução de problemas por humanos e máquinas, com o objetivo de fazer uma clara distinção entre os dois processos e deixar claro as limitações da máquina (no caso o computador no seu modelo von Neuman sequencial) para tratar de processos normalmente associados a humanos. A proposta de ter um método geral para resolução de qualquer problema (que discutiremos mais detalhadamente nas próximas aulas) está ligado a esta referência (humana) e é uma discussão antiga, como vimos no histórico das primeiras aulas.

    Partiremos do paradigma estado/transição para tratar do problema da resolução de problemas por máquinas, tomando como exemplo o exercício que foi dado para as equipes recentemente formadas. Discutiremos em primeiro lugar os algoritmos de busca não-informada e nas aulas seguintes os algoritmos de busca informado, o conceito de heurística e conhecimento tácito, muito importante para a elaboração de sistemas especialistas. Lembrando que estamos discutindo os conceitos clássicos da IA. 

    Apresentaremos algumas "boas práticas" no desenvolvimento de software para inteligencia artificial, novamente tomando como base o exercicio-programa. 

  • Introduzindo estruturas para os processos de busca



    Nesta aula vamos fazer um breve parêntese na discussão dos algoritmos de busca para inserir um tópico pertinente à implementação, que é a introdução de estruturas, como grafo, árvore, etc. Estas estruturas são implementadas de maneira direta nas linguagens procedurais, mas, em Prolog, como em outras linguagens declarativas, estas estruturas são interpretadas (como no Lisp, APL, etc.) constituindo-se na base para processos  recursivos.

    A razão para anteciparmos a discussão sobre implementação é municiar as equipes para o andamento do trabalho em grupo, deixando-os livres para pensar somente no núcleo inteligente do projeto e não nos aspectos periféricos que poderiam demandar certa habilidade de programação em Prolog. Por outro lado, trabalharemos com procedimentos bem simples, mesmo sabendo que existem opções mais eficientes e/ou mais elegantes para implementar a mesma coisa. A prioridade é a facilidade para entender o programa em caso de ser preciso fazer o "tracing" para debugar o código.

    Prosseguiremos ainda com a discussão qualitativa dos métodos de busca já que sua implementação começará a fazer parte do escopo à partir da aula de hoje. 

    Nesta aula também faremos uma breve discussão sobre o cronograma de execução do trabalho em grupo. 



    Para a próxima aula, dia 25/09, vocês devem submeter (até a meia-noite deste dia) a modelagem do domínio do mundo de blocos para o subsidiar o programa que irão fazer. Usem o exemplo dado nos slides, onde o domínio é definido pelos agentes e elementos do sistema (no caso bloco, robô, colunas pré-definidas), ações que estes podem fazer ou sofrer. Em seguida defina o problema de planejamento onde se caracteriza claramente o que significa estado e as ações (transições) do sistema, bem como as restrições a cada uma delas. Podem já adiantar a definição de habilitação das transições (dependente da definição anterior) e portanto estarão preparados para propor um mecanismo de inferência para o problema baseado no STRIPS. 


  • O STRIPS e o Frame Problem



    Vamos resumir o que vimos até aqui sobre os processos para resolver problemas genéricos usando Inteligência Artificial para ter uma noção mais precisa da evolução desta discussão desde a criação da IA, e de como esta abordagem dominou  a cena nos principais centros de pesquisa. Veremos que o Frame Problem, tem, além de aspectos filosóficos uma relação bem próxima com a representação de problemas para robótica e, em especial, para usar a abordagem estado-transição. Espera-se que isso traga algum insight para o trabalho de resolver o mundo de blocos. 

    Começaremos a discussão pelo best-first que será detalhado na próxima aula.

  • O Agoritmo A* e a busca informada




    Vamos agora introduzir o algoritmo de busca A* e suas propriedades. Temos já um bom resumo dos algoritmos de busca não-informada, contida no material da UVA disponibilizado no site depois da aula passada. Agora daremos um passo definitivo para ter um algoritmo de busca otimizante com performance exponencial. No entanto, dependendo do número de estados e da qualidade da heurística uma resposta (se existir) pode ser obtida em um tempo razoável, como veremos na resolução do STRIPS aplicado ao mundo de blocos.  

     

  • Explorando o STRIPS



    Nesta aula vamos entrar em mais detalhes sobre o STRIPS e consequentemente sobre os métodos de planejamento automático, antes de tratar os algoritmos de planning propriamente. Assim, os pressupostos do STRIPS são revistos baseado em um artigo do Fikes e Nilsson publicado em 1993 pela revista Artificial Intelligence, uma das mais destacadas na área. O artigo faz um retrospecto do projeto que consolidou o STRIPS, mostrando o esforço de grandes pesquisadores da área como R. Fikes, N. Nilsson, E. Sacerdoti, P. E. Hart, B. Raphael, e outros, envolvidos no projeto do robô Shakey (mostrado na figura que ilustra a aula passada). O objetivo é destacar a força conceitual do STRIPS e sua base do General Problem Solver (GPS), proposto por Allen Newel e Herbert Simon, que valeu a ambos o Turing Award. Por outro lado é preciso também mostrar as fragilidades do método que se foram importantes para simplificar o problema e direcionar o foco para o "STRIPS monitor" que efetivamente "prova o teorema" de como se pode ir do estado inicial para o estado final, também podem conduzir a resultados inesperados.

    A anomalia de Sussman, discutida na aula passada ilustra uma destas fragilidades e foi apresentada por Gerald J. Sussman na duarante a elaboração da sua tese de doutorado em 1973, orientada por Marvin Mynsky no MIT. Ao contrário da maioria dos grandes pesquisadores citados Sussman está vivo e ainda atuante no CSAIL (Computer Science and Artificial Intelligence Lab) do MIT. 

    Na verdade embora seja importante destacar as limitações do STRIPS isso não afeta os planejadores automáticos atuais e todos podem evitar facilmente (mesmo os planejadores dados como exercício para alunos de IC já fazem isso com facilidade) a anomalia de Sussman, mas a detecção destas anomalias servem para conduzir a busca por novas abordagens (ainda baseadas no STRIPS) para o problema do planejamento automático. Apresentaremos no final da aula uma destas abordagens voltadas para o tratamento do problema de planning com técnicas de Knowledge Engineering. 

  • Planejamento inteligente




    A atividade de planejamento é geralmente relacionada com processos racionais inteligentes, e, historicamente, marcou o desenvolvimento da humanidade e o seu caminho até os dias atuais. Nos dias atuais continua sendo uma atividade de grande destaque, e presente em qualquer atividade que pretenda ser eficiente, prática, e evitar percalços. Há portanto uma grande demanda por sistemas inteligentes de planejamento sejam eles baseados em técnicas que classificamos como clássicas, sejam baseado em estatística, cadeias de Markov, acoplados a processos de incerteza, e/ou aprendizado de máquina. Seja como for a demanda só aumenta, e o futuro da automação inteligente está intimamente ligado à sua capacidade de prover processos automatizados com capacidade para "planejar".

    Nesta aula vamos introduzir  os conceitos gerais do planejamento automático,  além do escopo de aplicações para a bordagem de planejamento. O ponto mais importante é no entanto a relação que existe entre os processos de planejamento e a modelagem estado-transição, usados na modelagem de sistemas discretos.  Este conceito vai inspirar o processo e a abordagem de planejamento mais conhecida, o STRIPS (Stanford Research Institute Problem Solver), voltada para "problem solving". O SRI se destacou durante os últimos 50 anos na pesquisa em Inteligência Artificial e foi o berço do que chamamos de planejamento clássico. O interesse maior foi sempre ter um planejador genérico, independente de domínio, que pudesse ser embarcado em sistemas autônomos, como o robô Shakey mostrado na figura acima.



    Segundo trabalho do curso
    Nesta aula começamos oficialmente a busca pelo tema do segundo trabalho do curso que consiste em, mantendo as equipes atuais, escolher uma aplicação clássica de Inteligência Artificial baseada nos métodos clássicos (sistemas especialistas, sistemas de diagnóstico, controle inteligente, planejamento) e pesquisar como esta aplicação foi programada, usando quais métodos, o que faz, alguma noção de sucesso e desempenho. A satisfação de usuários e stakeholders é igualmente importante. As informações podem ser obtidas na internet, em contato com quem usa e/ou mantém a aplicação e eventualmente com a empresa que fez o sistema. Elas costumam responder aos e-mails. O objetivo do trabalho é que vocês tenham uma noção mais precisa das aplicações da IA ligadas à engenharia e em especial à automação.

    O milestone para o dia 06/11 é escolher a aplicação e postar um arquivo PDF com o nome dos membros da equipe (se houver desistências do curso nomes podem ser retirados da lista), e com a descrição da aplicação escolhida, ressaltando o uso da IA clássica. Enviarei um feedback até a aula seguinte para reforçar (ou pedir ajustes) a proposta.



  • Competição - Algoritmos de Busca Informada




    Hoje realizamos a nossa competição de diferentes (?) implementações do algoritmo base do STRIPS para o problema modelo do mundo de blocos. Diferenças na implementação das heuristicas deveriam resultar em uma diferença de performance na execução, o que não aconteceu de forma marcante. 

    A avaliação é feita em duas etapas, uma pela nota da competição, e outra pela descrição que será atribuída ao relatório que deve ser enviado com o código e mais a descrição da heurística e sua justificativa como heurística admissível.  Os critérios para compor a justificativa estão sintetizados nos slides das aulas sobre planejamento e sobre o STRIPS. Consideraremos este último relatório a fase final do exercício, que deve requerer mais trabalho e portanto deve ter um peso de 60% da nota, enquanto que os trabalhos preparatórios anteriores valem 40%.

    Realizada a competição o resultado foi o seguinte:


    Nota da competição
    grupo 1a. rodada 2a. rodada 3a. rodada Media das rodadas  

    Grupo 1:

    Fernando Vicente Monteiro 8992919

    Marcos Menon José  8989112

    Sverker Fabian Hugert 11462480

    Vitor Augusto Martin 8993100

    9 7 10 8,7

    Grupo 2:

    David Calil Spindola Pedro - 8989384

    Diego Augusto Vieira Rodrigues - 8989276

    Felipe Cominato Nemr - 9345662

    Guilherme Sugahara Faustino - 9348971

    8 7 6 7

    Grupo 3:

    Lucas Hideki Sakurai 8989193

    Lucas Pereira Cotrim 8989092

    Matheus Torres Guinezi 9345679

    Monize Bessa Arabadgi 7961944

    Renan Masashi Yamaguchi 8989151

    9 10 9 9,3

    Grupo 4:

    Alexandre Zamora Zerbini Denigres - 8583072

    Dylan Kim Heleno - 8586072

    Henrique Yda Yamamoto - 9349502

    Vinicius Augusto Carnevali Miquelin - 8988410

    Vinicius Takiuti Miura - 9345874

    7 7 6 6,7

    Grupo 5:

    Guilherme Dello Russo - 9345895

    Nathan Géraud PERRIN- 10935360

    Natália Thoma Ricardo - 9344806

    8 8 7 7,7
     
    Grupo 6:

    Beatriz Santin de Araujo Pinho - 8533851

    Bianca Faria Silva - 8991599

    Bruna Sayuri de Souza Suzuki - 7987501

    Murillo José Almeida de Oliveira - 9436785


     
     Grupo 7:

    Daniel Tsutsumi - 9349005

    Gabriel Pinto - 8988017

    Juliana Lopes - 8512600

    Kaio Takase - 9345690

    Matheus Ramalho - 9345710


    8,3   



  • Tópico atual

    Algoritmos de Planejamento



    Nesta aula continuaremos a discussão sobre os principais algoritmos de planejamento automático fazendo um link para a demanda atual e o que seria necessário para tratar destes problemas saindo do escopo dos algoritmos clássicos STRIPS-like. Revisaremos o que foi discutido antes da competição para termos uma comparação mais direta entre as aplicações que queremos automatizar com algoritmos inteligentes, os tipos de planejamento, para inserir algumas extensões que nos permita ampliar o escopo das aplicações práticas. Especial atenção será dada para as aplicações cooperativas e de comunicação direta com o usuário, especialmente se tivermos como objetivo as diferentes aplicações em sistemas de serviço. Um exemplo interessante é o interesse do setor bancário nesse tipo de aplicação e expectativa dos stakeholders desta área com relação aos sistemas inteligentes.