Inteligência Artificial e Robótica - Aula2

Prévia do material em texto

AULA 2 
 
 
 
 
 
 
 
 
 
INTELIGÊNCIA ARTIFICIAL E 
ROBÓTICA 
 
 
 
 
 
 
 
 
 
Prof. Luciano Frontino de Medeiros 
 
 
2 
TEMA 1 – AGENTES INTELIGENTES 
A Robótica é uma ciência pragmática por princípio. Os pesquisadores de 
robôs — sejam empresas fabricantes de robôs industriais, sejam crianças 
construindo seguidores de linha — precisam lidar com conhecimentos de maneira 
experimental, levando em consideração conceitos e ideias consolidadas em 
outras áreas, além de empreender por tentativa e erro, tendo em mente certa 
finalidade. 
Em primeiro lugar, um robô deverá trabalhar de forma autônoma. A 
autonomia considera que ele deverá estar atento a certos eventos ou condições 
existentes no ambiente em que deverá executar suas tarefas. Deverá “pensar” 
sobre essas condições e depois “tomar decisões”, sem a interferência de um ser 
humano, pressupondo um comportamento autônomo. 
Assim, a tarefa do construtor de robôs é, de certa forma, provê-lo de uma 
certa “consciência” e fazê-lo agir conforme regras estabelecidas em seu projeto. 
A Robótica herda da Inteligência Artificial o conceito de agente inteligente. 
De forma mais geral do que um robô, um agente precisa executar tarefas de forma 
autônoma, testando as condições do ambiente e executando ações conforme um 
programa estabelecido, o que se aplica tanto para um robô quanto para um 
software que não esteja embutido em um artefato real. 
Conforme Russell e Norvig (2004), um agente é um artefato equipado com 
sensores que têm a capacidade para perceber o ambiente e agir sobre ele por 
meio de atuadores. Em comparação com o ser humano, os sensores são 
equivalentes aos olhos, ouvidos, nariz e o tato. Os atuadores podem equivaler às 
mãos, às pernas, à boca e às demais partes ativas de nossa anatomia. 
Hoje em dia os robôs são construídos tendo sensores, tais como 
câmeras, dispositivos de infravermelho, de som e ultrassom, de gás, de 
temperatura e de umidade, dentre outros. Como atuadores, podemos 
relacionar os servomotores, motores de passo, pistões hidráulicos e 
relês. Mas um agente precisa também processar os sinais provenientes 
dos sensores para efetuar alguma ação que seja caracterizada como 
inteligente sobre o seu ambiente (Medeiros, 2018, p.35). 
Por exemplo, um robô seguidor de linha tem sensores para detectar as 
variações de luz de uma trilha de cor diferente do chão por onde deverá se 
movimentar (conforme a Figura 1). 
Tal sensor pode ser baseado em um componente denominado light 
dependent resistor — LDR (resistor dependente de luz) ou em um conjunto de 
 
 
3 
emissor-receptor de luz infravermelha. Por meio da movimentação e das 
variações de luz, o robô tem em seu programa um conjunto de regras que permite 
continuar o seu movimento sobre a trilha. Como atuadores, o robô possui motores 
para dar velocidade e ajustar a direção do movimento conforme a detecção do 
trajeto. 
Figura 1 – Exemplo de um robô seguidor de linha 
 
Crédito: MASSIMO PARISI/SHUTTERSTOCK 
De forma geral, um agente inteligente interage com o seu ambiente da 
maneira que será mostrada na Figura 2. Por meio dos sensores, um agente tem 
percepções do ambiente. 
Os sensores podem atuar de forma combinada para caracterizar uma 
percepção de algo acontecendo ao redor deles. Entretanto, a percepção do 
ambiente está sujeita a mudanças, possuindo um aspecto temporal, sendo 
necessário considerar, também, a sequência de percepções. 
Essa sequência é processada internamente pelo agente. Conforme Russel 
e Norvig (2004, p.34), “a escolha da ação de um agente em qualquer instante 
dado pode depender da sequência inteira de percepções observadas até o 
momento”. 
 
 
 
4 
Figura 2 – Interação do agente inteligente com o ambiente e seus elementos 
internos 
 
Fonte: Russel; Norvig, 2004. 
O processamento dos sinais sensoriados pelo agente para a execução de 
ações tem uma similaridade bastante grande com o conceito função da 
Matemática. Denomina-se função do agente o mapeamento das possíveis ações 
por meio de sequências de percepções disponíveis na memória do referido 
agente, de acordo com Russel e Norvig (2004). 
A tarefa nobre do projetista de robôs está na determinação da função do 
agente. 
Para robôs que executarão tarefas simples, a função do agente pode ser 
bem determinada, e seu comportamento pode acondicionar um conjunto de ações 
bem definidas. Para outros robôs, a função do agente pode ser impossível de 
descrever de forma bem definida. 
Agentes que desenvolvam tarefas simples, como um robô aspirador, tem 
uma função de agente bem delimitada de forma a produzir um 
comportamento que pode ser aplicado a uma gama bem definida de 
ambientes sobre os quais pode fazer a limpeza. Por outro lado, um robô 
destinado a jogar xadrez representa um desafio, pois a quantidade de 
jogadas possíveis chega a valores astronômicos (aproximadamente 
10120 possibilidades – o número estimado de átomos no Universo chega 
a 1080). Dessa forma, um agente inteligente para o jogo de xadrez deve 
ter a sua função de agente limitada, de forma que não leve milhões de 
anos para fazer uma jogada, e que tenha memória suficiente para 
armazenar jogadas possíveis considerando um horizonte de poucas 
jogadas à frente (Medeiros, 2018, p.36). 
 
 
5 
A função do agente se trata de uma descrição abstrata, que pode ser feita 
utilizando diagramas ou outras simbologias que permitam representar o que o 
agente deve fazer. Por meio da função do agente, elabora-se o programa do 
agente, que é implementado de forma concreta e está comprometido com 
aspectos da arquitetura do agente, segundo Russel e Norvig (2004, p. 34). 
O programa se exprime na linguagem de programação utilizada para 
desenvolver o agente. Por exemplo, um robô baseado na plataforma Arduino pode 
utilizar a linguagem “C” ou mesmo a linguagem Scratch. 
Para ilustrar com outro exemplo, supõe-se um mundo de um robô aspirador 
bastante simples, composto de nove blocos nos quais ele pode se posicionar e 
identificar se existe sujeira ou não (conforme mostra a Figura 3). 
Os blocos são referenciados mediante linhas e colunas. Caso ele comece 
inicialmente no quadrado central, uma sequência de ações pode fazer com que o 
robô proceda a uma varredura e verifique se existe sujeira ou não em cada 
quadrado que for visitar, segundo Medeiros (2018). 
Figura 3 – Representação do ambiente de um robô aspirador 
 
Fonte: Medeiros, 2018, p. 37. 
Podem-se imaginar diferentes formas pelas quais o robô poderá visitar 
cada um dos blocos. Possuindo um sensor detector de sujeira e atuadores na 
forma de motores para auxiliar a movimentação, o robô pode se movimentar pelos 
blocos. Assim, diversas sequências de percepções podem ser obtidas. 
 
 
6 
Na Figura 4 está descrita uma sequência de percepções possível. Cada 
percepção é composta da posição de onde o robô se encontra, além do sinal 
proveniente do detector de sujeira. 
Conforme a definição, o robô deve levar em consideração os movimentos 
feitos nessa sequência, para que se atinja sua finalidade geral — que é a limpeza 
de todo o seu “mundo”. 
Essa sequência pode ser combinada com a representação do ambiente do 
agente, conforme ilustra a Figura 5. 
Quadro 1 – Descrição da função do agente para o exemplo do robô aspirador 
 
Fonte: Medeiros (2018, p.38). 
 
 
 
7 
Figura 4 – Representação do ambiente do robô aspirador com o mapeamento de 
ações conforme a sequência de percepções 
 
Fonte: Medeiros, 2018, p. 38. 
Como constatado, existem diversas formas pelas quais o robô aspirador 
pode executar a sua tarefa. Apesar de ele conseguir deixar o seu ambiente limpo, 
podemos nos questionar se o robô está sendo eficiente no desenvolver dessa 
atividade. 
Surge então as seguintes perguntas: existe uma maneira correta de o robô 
executar a tarefa? Existe um caminho pelo qual ele pode se movimentar de forma 
mínima para que o ambiente todoesteja limpo? 
Até agora não houve preocupação quanto a isso. Entretanto, à medida que 
a função do agente se torna mais complexa, tais questionamentos podem se 
tornar prioridade, dado que um robô poderá se movimentar de forma interminável, 
sem deixar o ambiente limpo (por exemplo, o robô poderia entrar em loop, saindo 
do centro para um bloco lateral, para um bloco diagonal, para outro lateral 
adjacente e voltar novamente ao centro, assim sucessivamente). 
O agente — além de cumprir a tarefa (ou seja, ser eficiente) — precisa ser 
também racional: aquele que, por meio do resultado das suas ações, possa obter 
o maior sucesso. 
Desse modo, é preciso considerar algum método para a quantificação do 
sucesso de um certo agente, segundo Russel e Norvig (2004, p. 36) “para cada 
 
 
8 
sequência de percepção possível, um agente racional deve selecionar uma ação 
que se espera venha a maximizar sua medida de desempenho, dada a evidência 
fornecida pela sequência de percepções e por qualquer conhecimento interno do 
agente”. 
Portanto, é necessária uma medida (ou um conjunto de medidas) de 
desempenho, para que se possa aferir a racionalidade do agente. 
De acordo com Russel e Norvig (2004, p. 36), a racionalidade irá depender 
em qualquer momento de quatro fatores. Vejamos: 
1. a medida de desempenho como critério para obtenção do sucesso da 
tarefa; 
2. o conhecimento prévio do agente em relação ao ambiente; 
3. as ações que o agente pode executar; 
4. a sequência de percepções que o agente tem até o momento. 
No caso do robô aspirador, uma medida de desempenho poderia ser a 
quantidade de quadrados limpos em um período de tempo ou por movimentação. 
O ambiente em que o robô executa a sua tarefa é conhecido, mas a sujeira 
pode aparecer de maneira variável nos blocos. O sensor de posição pode 
identificar o bloco em que ele se encontra (usando um leitor de posição) e, assim, 
averiguará se existe sujeira ou não — por meio de uma câmera ou de algum 
sensor que identifique a diferença de um bloco limpo ou sujo. 
Portanto, o robô aspirador poderá ser classificado como um agente 
racional. 
TEMA 2 – TIPOS DE AMBIENTES 
Devido à importância que o ambiente desempenha no papel de um agente, 
um projetista de robôs precisa saber caracterizar adequadamente como tal 
ambiente é. Dessa forma, é um dos elementos essenciais para a criação de um 
agente racional. 
Russell e Norvig (2004, p. 39) apontam que uma das primeiras atividades 
na modelagem de um agente é a definição do ambiente de tarefa. Este é composto 
de quatro elementos: desempenho, ambiente, atuadores e sensores. No inglês, 
assume o acrônimo PEAS (Performance, Environment, Actuators and Sensors). 
 
 
9 
No Quadro 2 estão alguns exemplos de caracterização do PEAS para 
diferentes situações: sistema de diagnóstico médico, jogo de xadrez, tutor 
inteligente e robô de solda. 
Quadro 2 – Exemplos de agentes racionais e as descrições do PEAS 
Tipo de Agente Medida de desempenho Ambiente Atuadores Sensores 
Sistema de 
diagnóstico 
médico 
Paciente 
saudável, 
minimizar 
custos. 
Quarto de 
hospital, 
paciente, 
equipe. 
Mostrar 
perguntas, 
testes, 
diagnósticos, 
tratamentos. 
Entrada por 
teclado, voz, 
descoberta de 
informação. 
Sistema de 
xadrez 
Calcular a 
jogada ótima, 
ganhar a partida. 
Tabuleiro 8x8, 
peças de 
xadrez, 
posições 
iniciais, jogadas 
possíveis. 
Braço articulado 
para mover as 
peças. 
Câmera para ver 
as posições das 
peças. 
Tutor 
inteligente 
Maximizar as 
notas dos alunos 
nos testes. 
Área de 
interação do 
software, chat 
de mensagens. 
Mostrar 
conteúdos, exibir 
exercícios. 
Entrada pelo 
teclado 
Robô de solda Efetuar os 
pontos de solda 
no tempo 
previsto, 
qualidade da 
solda. 
Linha de 
montagem. 
Braço articulado 
para 
movimentos no 
espaço, ponteira 
de solda. 
Identificação de 
novo objeto a 
ser soldado, 
quantidade de 
solda, 
temperatura de 
solda. 
Fonte: Adaptado de Russell; Norvig, 2004, p. 40. 
Dentro do PEAS, os ambientes ainda podem receber diferentes 
classificações conforme uma série de critérios, de acordo com Russel e Norvig 
(2004, p. 41-42): 
• Completamente observável x parcialmente observável: se os sensores 
acessarem de forma completa os estados do ambiente em cada instante, o 
espaço que o rodeia será completamente observável. Mas se houver ruído 
sensoriamento impreciso ou lacunas, será parcialmente observável. Por 
exemplo, um jogo de xadrez é completamente observável. Já um sistema 
de busca na internet é parcialmente observável. 
• Determinístico x estocástico: caso o estado seguinte seja 
completamente determinado mediante o estado atual — e pela ação 
executada pelo agente —, o ambiente será determinístico ou estocástico. 
Caso o sistema seja determinístico, porém apresentando elementos 
estocásticos, o ambiente poderá ser estratégico. Por exemplo, o robô 
 
 
10 
aspirador de pó é determinístico; um carro com direção autônoma é 
estocástico. 
• Episódico x sequencial: em um ambiente episódico o agente experimenta 
os eventos de forma atômica, com os episódios começando a partir da 
percepção do agente, bem como pela execução de uma única ação. No 
caso de um ambiente sequencial, existe a dependência dos estados atuais 
com os estados anteriores. Por exemplo, um jogo de xadrez é sequencial. 
Um robô aspirador de movimento aleatório é episódico. 
• Estático x dinâmico: um ambiente que se altera enquanto o agente 
executa a tarefa é dinâmico. Caso o ambiente não se altere, será estático. 
No entanto, pode haver situações em que os ambientes sejam 
semidinâmicos. Por exemplo, um jogo de xadrez é estático. Já um carro 
com direção autônoma é dinâmico (ou semidinâmico, considerando as 
rotas predefinidas). 
• Discreto x contínuo: Depende da forma com que o tempo decorre, do 
estado do ambiente, das percepções e das ações. Uma sequência de 
estados discretos muda aos “saltos” de um estado para outro. Uma 
sequência de estados contínua, por sua vez, muda de maneira suave. Por 
exemplo, um jogo de xadrez é considerado discreto, ao passo que um 
sistema de refrigeração de temperatura pode ser contínuo. 
• Individual x multiagente: refere-se à quantidade de agentes utilizados 
para a resolução de um problema. Caso exista somente um agente, 
significa que é individual. Caso contrário, o sistema será considerado 
multiagente. Por exemplo, um jogo de xadrez pode ser um agente 
individual. No caso de um agente jogar contra o outro, é multiagente. Já um 
sistema de busca na internet pode ser multiagente por utilizar vários bots 
que encontram e organizam a informação. 
No Quadro 3 estão alguns exemplos a respeito da caracterização da 
natureza do ambiente. 
 
 
 
11 
Quadro 3 – Alguns exemplos de caracterização do ambiente de tarefa 
 
Fonte: Russell; Norvig, 2004, p. 44. 
TEMA 3 – TIPOS DE AGENTES 
O estudo do tipo de agente, em vez da caracterização do ambiente, 
preocupa-se com aspectos internos deste. Como foi visto, deve-se agora lidar com 
o programa do agente, de acordo com a finalidade que ele terá. 
O agente deverá ter uma arquitetura que permita implementar o programa 
do agente, por meio de um conjunto de sensores e atuadores, conectados a um 
processador que irá executar o programa do agente, consoante Russel e Norvig 
(2004, p. 44). 
Portanto, o mesmo conceito pode ser aplicado a robôs. 
Conforme a sua arquitetura, um agente poderá ser classificado em cinco 
tipos, de acordo com Russel e Norvig (2004, p. 48): 
• Agentes reativos simples; 
• Agentes reativos baseados em modelo; 
• Agentes baseados em objetivos; 
• Agentes baseados na utilidade; 
 
 
12 
• Agentes com aprendizagem. 
3.1 Agentes reativos simples 
É o tipo mais simples de agente. O programa do agente sempre irá mapear 
as ações com base na percepção atual, descartando a sequência de percepções 
anteriores. 
A implementação de programas para esse tipo de agente pode serfeita 
utilizando-se regras de produção ou regras de lógica se-então. Elas têm uma 
característica determinística e, por meio de teste de condições, serão executadas 
ações, conforme o conjunto de regras que estão implementadas. 
SE <condição> ENTÃO <ação> 
O robô aspirador do exemplo mencionado anteriormente poderá conter 
quatro regras que irão gerar o comportamento desejado para o robô, segundo 
Medeiros (2018, p. 44). 
1. SE estado = Sujo ENTÃO Aspirar 
2. SE estado = Limpo ENTÃO faça movimento = SIM SENÃO faça movimento 
= NÃO 
3. SE faça movimento = SIM E quadrado na frente = SIM ENTÃO direção do 
movimento = FRENTE 
4. SE faça movimento = SIM E quadrado na frente = NÃO ENTÃO direção do 
movimento = DIREITA 
Nesse sistema de quatro regras, a primeira se encarrega da limpeza do 
quadrado por meio da variável estado. 
Caso o quadrado esteja limpo, a variável faça movimento recebe o valor 
SIM, o que é feito pela segunda regra. Com isso, as regras 3 e 4 ficam habilitadas 
para operar. Assim, é testada a variável quadrado na frente (ou seja, armazena o 
valor do sensor que identifica o quadrado). 
Se houver um quadrado à frente, a variável de ação direção do movimento 
recebe o valor FRENTE. 
Caso não houver (ou seja, o quadrado estará à direita), a variável direção 
de movimento recebe o valor DIREITA. 
 
 
13 
De maneira geral, a arquitetura de um agente reativo simples é mostrada 
na Figura 5. Boa parte dos robôs mais simples que podem ser construídos em 
robótica educacional poderá contar com essa arquitetura, o que facilitará a 
implementação por parte dos alunos. 
Por meio das percepções do ambiente, o agente se pergunta: “qual é a 
aparência do mundo?”. Tal aparência irá consistir em um conjunto de condições 
que irão “disparar” as regras que conseguirem atender a elas, e assim a ação a 
ser executada será selecionada e levada aos atuadores. 
Figura 5 – Arquitetura para um agente reativo simples 
 
Fonte: Adaptado de Russell; Norvig, 2004, p. 47. 
3.2 Agentes reativos baseados em modelo 
No caso de um ambiente ser caracterizado como observável parcialmente, 
é necessário que o robô mantenha estados internos que dependam da sequência 
de percepções para atuar de maneira mais efetiva. Por exemplo, se o robô 
aspirador tiver uma memória em que possa armazenar um histórico de 
percepções, ele terá informação em quais blocos apareceram mais sujeira do que 
outros, podendo começar os movimentos por tais blocos. 
Um agente que tem o conhecimento de “como o mundo funciona” possui 
um modelo de mundo. Um agente que tenha um modelo de mundo é denominado 
agente reativo baseado em modelo (Figura 6). 
 
 
 
14 
Figura 6 – Arquitetura para um agente reativo baseado em modelo 
 
Fonte: Adaptado de Russell; Norvig, 2004, p. 49. 
3.3 Agentes baseados em objetivos 
Apenas o conhecimento do estado atual do ambiente pode não ser o 
suficiente para que um robô decida o que fazer. 
Além de saber a descrição do estado atual e da sequência de percepções 
obtidas até o momento, pode ser necessária a definição de algum objetivo 
relacionado a situações ou a cenários desejados, consoante Russel e Norvig 
(2004, p. 49). 
A tomada de decisão baseada em objetivos é diferente do uso de regras 
de produção, pois a primeira está envolvida em uma situação a ser alcançada, 
uma situação de futuro. 
O agente então se pergunta: “o que vai acontecer se eu fizer essa ação ou 
aquela outra?” ou “isso irá me fazer feliz?”. Tais informações nos agentes reativos 
não são representadas de maneira explícita, graças ao mapeamento direto das 
percepções para as ações (Figura 7). 
Para Russel e Norvig (2004, p. 49), ainda que o agente baseado em 
objetivos possa parecer menos eficiente, ele tende a ser mais flexível. 
Voltando ao exemplo do robô aspirador, pode ser colocado em seu projeto 
um objetivo que leve em conta o custo de operação ou de consumo de energia. 
Com a execução contínua, o robô pode antecipar a frequência com que as 
limpezas são feitas, e nos intervalos ele pode entrar em modo de economia de 
energia para alcançar esse objetivo, segundo Medeiros (2018, p. 46). 
 
 
15 
Figura 7 – Esquema de um agente baseado em objetivo 
 
Fonte: Adaptado de Russell; Norvig, 2004, p. 50. 
3.4 Agentes baseados em utilidade 
Como saber se um agente está sendo útil por meio de uma medida? Até 
agora, os agentes anteriores não estavam preocupados com esse aspecto. Pode-
se especificar uma espécie de medida de utilidade: conforme a avaliação de uma 
função de utilidade, o agente ou o robô poderá tomar decisões mais adequadas 
(Figura 8). 
Pode ser que o robô tenha objetivos contraditórios e apenas alguns deles 
podem ser alcançados em dado momento. Ou pode haver vários objetivos, mas 
nenhum deles pode ser alcançado com alto grau de certeza, conforme lecionam 
Russel e Norvig (2004, p. 50). 
Por exemplo, um robô seguidor de linha pode conter um sensor que permite 
identificar se existe um bloqueio intermitente na trilha para a execução do 
movimento. Portanto, além da avaliação das regras conforme o sensoriamento da 
trilha, deverá também monitorar a todo momento se há algum objeto bloqueando 
a trilha. No caso de haver mais de uma trilha a ser percorrida, o robô poderá 
executar aquela em que uma função de avaliação minimize o percurso ou em que 
maximize o alcance do objetivo. 
Figura 8 – Esquema de um agente baseado em utilidade 
 
 
16 
 
Fonte: Adaptado de Russell; Norvig, 2004, p. 51. 
3.5 Agentes com Aprendizagem 
O agente com aprendizagem permite ir além do conhecimento prévio na 
construção do agente, dotando-o de mecanismos para que possa aprender na 
experiência com o ambiente, tornando-se mais competente ao longo da sua 
operação (Figura 9). 
Conforme ensinamentos de Russel e Norvig (2004, p. 51-52), um agente 
de aprendizado pode ser dividido em quatro elementos: 
• Elemento de desempenho: é a parte considerada até agora sobre 
agentes, que recebem as percepções e decide qual ação executar. 
• Crítico: elemento do agente que informa como ele está se comportando 
em relação ao seu padrão constante de desempenho. 
• Elemento de aprendizado: utiliza a informação proveniente do crítico para 
modificar o elemento de desempenho em direção a um melhor 
funcionamento no futuro. 
• Gerador de problemas: elemento responsável para sugestão de novas 
regras e ações que podem levar a novas experiências. 
 
 
 
17 
Figura 9 – Esquema de um agente com aprendizagem 
 
Fonte: Adaptado de Russell; Norvig, 2004, p. 52. 
TEMA 4 – AGENTE DE RESOLUÇÃO DE PROBLEMAS POR BUSCA 
Os agentes de resolução de problemas precisam tomar decisões sobre os 
próximos passos, de modo a encontrar as sequências de ações que resultam em 
estados que são desejáveis, segundo Russel e Norvig (2004, p. 62). Por exemplo, 
um problema recorrente é o de roteirização. Esse problema é característico de 
várias áreas tais como a área de logística e turismo. Quando se tem um conjunto 
de locais que precisam ser visitados considerando a existência de rotas definidas 
para esses locais, o objetivo é como percorrer todos eles considerando um custo 
mínimo ótimo. Esse problema foi retratado na Inteligência Artificial como o 
problema do viajante. 
Aplicando o problema a um mapa rodoviário, ilustrado na Figura 10, o 
objetivo é sair da cidade de Foz do Iguaçu e chegar à cidade de Curitiba. 
Dessa forma, o agente deve escolher uma rota ou um curso de ação que 
permita chegar ao destino, e aqueles que não permitem chegar em um tempo 
considerado aceitável possam ser rejeitados. Assim, a formulação de objetivos se 
baseia na situação atual do agente e na medida de desempenho do mesmo, 
configurando o primeiro passo para a resolução do problema. 
 
 
 
18 
Figura 10 – Mapa rodoviário utilizado no texto 
 
Fonte: Medeiros, 2018, p. 54. 
Se o agente possui um mapa, ele pode obter informações sobre os estados 
em que sepossa entrar e quais as ações ele pode perfazer. 
O agente considera então as possíveis rotas a partir das cidades 
consideradas. Dessa forma, um agente que possua uma série de opções 
imediatas de valor desconhecido pode decidir o que fazer avaliando 
primeiro as diferentes sequências de ações possíveis que irão levar a 
estados de valor conhecido, tendo condições de escolher a melhor 
sequência. O processo de procurar esta sequência é denominado de 
busca (Russel; Norvig, 2004, p. 62). 
Um algoritmo de busca recebe em sua entrada um problema e apresenta 
na sua saída uma solução, descrita sob a forma de uma sequência de ações 
definidas. Por meio da obtenção da solução, as ações recomendadas por ela são 
colocadas em execução. O algoritmo para a resolução de problemas simples pode 
ser então descrito nos seguintes passos, segundo os dizeres de Russel e Norvig 
(2004, p. 63): 
• Formulação do objetivo e do problema; 
• Busca de uma sequência de ações que resolvem o problema; 
• Execução das ações uma por uma. 
Quando a sequência se completa, ele formula outro objetivo e então 
recomeça. É importante observar que na execução da sequência, o agente não 
leva em conta as percepções, na hipótese de que a solução que foi encontrada 
na busca sempre funcione. 
 
 
19 
Um problema pode ser definido de maneira formal em quatro componentes: 
• Um estado inicial: o estado no qual o agente começa. Por exemplo, se o 
agente do exemplo da viagem estiver em Foz do Iguaçu, o estado inicial 
pode ser descrito como origem (Foz do Iguaçu). 
• Uma função sucessor: dado um estado particular x, Sucessor(x) retorna 
um conjunto de pares ordenados <Ação Sucessor>, em que cada ação é 
uma das ações válidas no estado x, e cada sucessor pode ser alcançado 
partindo-se de x. Como exemplo, no caso do estado inicial ser Origem (Foz 
do Iguaçu), a função sucessor para o problema retornaria 
{<Destino(Cascavel), Origem(Foz do Iguaçu)>, 
<Destino(Pato Branco), Origem(Foz do Iguaçu)>} 
O estado inicial e a função denominada Sucessor definem o espaço de 
estados do problema, ou seja, o conjunto de todos os estados acessíveis 
tendo como partida o estado inicial. O espaço de estados representa um 
gráfico, em que os nós são os estados, e os arcos entre os nós são as 
ações. 
• O teste de objetivo: determina se um estado é um estado objetivo. O 
objetivo do exemplo é o estado final Origem(Curitiba). Em alguns casos, 
um objetivo pode ser definido como uma propriedade abstrata e não por 
um estado ou por um conjunto de estados específicos. Por exemplo, em 
um jogo de xadrez, o objetivo é alcançar o xeque-mate. 
• A função de custo: também chamada de função de custo de caminho, que 
atribui um custo numérico a cada caminho. O agente irá escolher, portanto, 
uma função de custo que irá significar a sua própria medida de 
desempenho. No caso do agente do exemplo, a função de custo seria a 
distância em quilômetros (Figura 11). Há, então, um custo de passo para ir 
de um estado a outro. 
Definidos os quatro elementos da formulação do problema, uma solução 
para um problema é um caminho que leva o agente desde o estado inicial até o 
estado objetivo. Considerando a qualidade da solução, a qual é medida pela 
função Custo, uma solução ótima é aquela que apresenta o menor custo entre 
todas as soluções possíveis, de acordo com Russel e Norvig (2004, p. 64). 
Figura 11 – Mapa com as distâncias em quilômetros do Estado do Paraná. 
 
 
20 
 
Fonte: Medeiros (2018, p.56). 
Os problemas a serem estudados na Inteligência Artificial podem ser 
divididos em miniproblemas (para ilustração de métodos de resolução) ou 
problemas do mundo real (geralmente não tendem a ter uma descrição concisa e 
exata). No Quadro 4, encontra-se a formulação do problema para o robô 
aspirador. 
Quadro 4 – Formulação do miniproblema do robô aspirador 
Robô Aspirador 
Formulação Descrição 
Estados O agente se posiciona em uma de 9 posições 
diferentes que podem conter sujeira ou não. A 
quantidade de espaços possíveis (contando que 
todos contenham sujeira) é de 9 x 2 estados mais 
2 do estado inicial resultando em 20 estados. 
Estado inicial Robô na posição (2,2) 
Função sucessor Gera os estados válidos resultantes da tentativa 
de ação (Para-frente, Para-direita, Aspirar). Ver 
na Figura 3. 
Teste de objetivo Verificar se todos os quadrados estão limpos 
Custo de caminho Cada passo custa 1 unidade; o custo do caminho 
é o número de passos. 
Para o miniproblema do robô seguidor de linha, o Quadro 5 mostra uma 
possível formulação. Nesse caso, é adotado como premissa que existe um início 
na trilha (que pode ser uma marcação na trilha de outra cor) e que o robô adote 
um movimento genérico para poder ficar sobre a trilha, caso esteja fora dela (por 
exemplo, adote um caminho aleatório até que esteja posicionado sobre a trilha). 
Quadro 5 – Formulação do miniproblema do robô seguidor de linha. 
 
 
21 
Robô Seguidor de Linha 
Formulação Descrição 
Estados O robô se posiciona em qualquer lugar no tablado 
onde se encontra a trilha a ser seguida. Ele pode 
estar em uma posição sobre a trilha ou fora dela. 
Estado inicial Robô em qualquer posição sobre o tablado onde 
se encontra a trilha. 
Função sucessor Aciona o motor esquerdo caso detecte que está à 
esquerda da trilha; aciona o motor direito caso 
detecte que está à direita da trilha. 
Teste de objetivo Verifica se alcançou o marco de início da trilha 
Custo de caminho Cada acionamento de um motor custa 1 unidade; 
o custo do caminho é o número de acionamentos 
do motor, relativo ao número de vezes em que 
esteve fora da trilha. 
Segundo Russell e Norvig (2004, p. 73), no caso de um agente de resolução 
de problemas por busca, a avaliação de desempenho de um algoritmo pode ser 
feita a partir de quatro aspectos: 
• Completeza: o algoritmo de busca oferece a garantia de encontrar uma 
solução quanto ela existir? 
• Otimização: a estratégia encontra a solução ótima? 
• Complexidade de tempo: quanto tempo é dispendido para encontrar 
uma solução? 
• Complexidade de espaço: quanto de memória é necessária para a 
execução da busca? 
TEMA 5 – ESTRATÉGIAS DE BUSCA 
A partir de um problema de busca formulado adequadamente, do qual não 
existe um algoritmo determinístico para a resolução, é necessário que o agente 
adote alguma estratégia para poder alcançar uma possível resolução. 
As estratégias de busca se dividem em duas classes: estratégias sem 
informação ou estratégias cegas e estratégias com informação ou busca 
heurística. As estratégias se diferenciam conforme a ordem de expansão dos nós 
da árvore de busca. 
As estratégias sem informação dividem-se em: 
• Busca em extensão ou amplitude; 
• Busca de custo uniforme; 
• Busca em profundidade; 
 
 
22 
• Busca em profundidade limitada; 
• Busca de aprofundamento iterativo; 
• Busca bidirecional. 
Apesar de haver vários tipos de estratégias, podemos destacar dois 
procedimentos principais: a busca em extensão (ou em amplitude) e a busca em 
profundidade. 
A busca em extensão (ou em amplitude) é uma estratégia simples em que 
o nó raiz é expandido inicialmente; posteriormente, os sucessores do nó raiz; 
depois, os sucessores dos sucessores do nó raiz e assim por diante, de acordo 
com as lições de Russell e Norvig (2004, p. 74). 
Figura 12 – Exemplo da busca em extensão de uma árvore binária simples. O 
marcador indica qual o é nó que será expandido 
 
A estratégia de busca em profundidade expande sempre o nó mais 
profundo na borda atual da árvore de busca. Na Figura 8 podemos ver como esse 
algoritmo se desenvolve. A busca prossegue até o nível mais profundo da árvore, 
em que não existem mais nós sucessores. Após visitar os nós mais profundos, a 
busca retorna ao nível mais raso que ainda possua nós não explorados, 
asseveram Russell e Norvig (2004, p. 76). 
Essas duas estratégias básicas formam a base para as outras estratégias 
de buscasem informação. 
 
 
23 
Figura 13 – Ilustração da busca em profundidade em uma árvore binária. Os nós 
que foram expandidos e não possuem descendentes na borda podem ser 
removidos da memória 
 
As estratégias de busca sem informação tendem a ser ineficientes na 
maioria dos casos. As que utilizam algum conhecimento específico do sistema 
podem ser uma opção mais eficiente. As estratégias de busca com informação 
podem contar com uma função de avaliação do problema (por exemplo, a 
distância entre cada cidade, no exemplo do mapa rodoviário) e uma função 
heurística (a distância em linha reta de cada cidade até o objetivo, isto é, Curitiba), 
segundo Medeiros (2018, p. 73). 
Dois tipos de estratégias de busca com informação são: 
• Busca gulosa; 
 
 
24 
• Algoritmo A* (A — estrela). 
A busca gulosa é uma estratégia que leva em consideração apenas a 
função heurística. Nesse caso, o passo seguinte será aquele em que for 
apresentado o valor da função heurística de menor custo. No caso do mapa 
rodoviário, será levada em consideração apenas a distância em linha reta de cada 
cidade, conforme expõe Medeiros (2018, p. 74). 
A busca A* combina a função de avaliação e a função heurística. No caso 
de a função heurística atender a certas condições, essa estratégia é considerada 
completa e ótima. Completa porque sempre encontrará uma solução, e ótima pois 
a solução que será encontrada é a melhor de todas, leciona Medeiros (2018, p. 
75). 
 A busca A* é bastante utilizada em jogos para que um avatar percorra uma 
distância até encontrar um jogador oponente. Em Robótica, a busca A* pode ser 
utilizada para trajetórias de robôs e a resolução de puzzles, tais como o cubo de 
Rubik. 
 
 
 
25 
REFERÊNCIAS 
MATARIC, J. M. Introdução à robótica. São Paulo: UNESP/Blucher, 2014. 
MEDEIROS, L. F. de. Inteligência artificial aplicada: uma abordagem 
introdutória. Curitiba: InterSaberes, 2018. 
PAPERT, S. A máquina das crianças: repensando a escola na era da 
informática. Porto Alegre: ed. Artes Médicas, 1994. 
RESNICK, M. et al. Scratch: programming for all. Communications of the ACM, 
v. 52, n. 11, p. 60–67, Nov. 2009. 
RUSSEL, S.; NORVIG, P. Inteligência artificial. Tradução da 2. ed. Rio de 
Janeiro: Campus, 2004. 
SANTOS, I. Contribuição da robótica como ferramenta pedagógica no ensino 
da matemática no terceiro ano do ensino fundamental. 161 f. Dissertação 
(Mestrado Profissional em Educação e Novas Tecnologias) – Centro Universitário 
Internacional UNINTER, Curitiba, 2017. 
ZILLI, S. do R. A robótica educacional no ensino fundamental: perspectivas e 
práticas. 89 f. Dissertação (Mestrado em Engenharia de Produção) – Universidade 
Federal de Santa Catarina, Florianópolis, 2004.