ROBÔS MÓVEIS BASEADA EM ACORDO BIZANTINO

Prévia do material em texto

UNIVERSIDADE FEDERAL DE SANTA CATARINA 
TECNOLOGIAS DA INFORMAÇÃO E COMUNICAÇÃO 
TELMO DOS SANTOS KLIPP 
PROPOSTA DE UMA ARQUITETURA PARA ALOCAÇÃO DE 
TAREFAS EM GRUPOS DE ROBÔS MÓVEIS BASEADA EM 
ACORDO BIZANTINO 
Araranguá, 28 de fevereiro de 2013
TELMO DOS SANTOS KLIPP 
PROPOSTA DE UMA ARQUITETURA PARA ALOCAÇÃO DE TAREFAS EM GRUPOS 
DE ROBÔS MÓVEIS BASEADA EM ACORDO BIZANTINO 
Trabalho de conclusão de Curso submetido à 
Universidade Federal de Santa Catarina como 
parte dos requisitos necessários para a 
obtenção do Grau de Bacharel em Tecnologias 
de Informação e comunicação. Sob a 
orientação do Professor Anderson Luiz 
Fernandes Perez. 
Araranguá, 2013 
Telmo dos Santos Klipp 
PROPOSTA DE UMA ARQUITETURA PARA ALOCAÇÃO DE TAREFAS EM 
GRUPOS DE ROBÔS MÓVEIS BASEADA EM ACORDO BIZANTINO 
Trabalho de Curso submetido à Universidade 
Federal de Santa Catarina, como parte dos 
requisitos necessários para a obtenção do Grau 
de Bacharel em Tecnologias de Informação e 
Comunicação. 
 
Araranguá, 28 de fevereiro de 2013
Aos meus pais, Nauro José e Rosa 
Honorata, e ao meu irmão Elton Davi. 
 AGRADECIMENTOS 
A Deus por me conceder sua centelha divina, a 
vida da qual desfruto todos os dias. Aos meus pais 
que sempre me apoiaram concedendo-me educação 
para a vida. Aos meus colegas e amigos pelo apoio e 
presença nessa caminhada de aprendizado, em es-
pecial ao Tiago Elias e ao Fernando Puntel. Aos 
membros do LARM (Laboratório de Automação e 
Robótica Móvel) e aos nobres colegas do Posto de 
Fiscalização Sanitária (BR-101, Araranguá) pelos 
auxílios concedidos. A Universidade Federal de 
Santa Catarina que abre tantos caminhos e em es-
pecial ao meu orientador, professor Anderson Luiz 
Fernandez Perez, por suas importantes contribui-
ções ao desenvolvimento do trabalho e por ser razão 
de intensa motivação, paciência e inspiração. 
Examinai tudo. Retende o bem. 
Tessalonicenses 5-21 
 
RESUMO 
Robôs móveis vêm sendo usados cada vez mais para a execução de inúmeras tarefas, seja na 
indústria, na prestação de serviços ou em aplicações militares. Muitas tarefas são de natureza 
complexa e exigem a adoção de mais de um robô para sua completa execução. Sendo assim, a 
formação de grupos de robôs é fundamental e deve basear-se nas características da tarefa a ser 
executada, ou seja, das exigências funcionais do que é preciso para executá-la, mas também 
garantindo que, havendo uma falha de um ou mais robôs, a tarefa poderá ser concluída, mes-
mo em um tempo computacionalmente maior. Assim os robôs membros de um grupo devem 
ser escolhidos baseados em critérios físicos, comportamentais (habilidades) e de tolerância a 
falhas. Uma maneira de garantir a execução de uma tarefa por um grupo de robôs é adotar 
alguma técnica de tolerância a falhas, tal como o acordo bizantino. Acordo bizantino é basea-
do no princípio de que havendo falha de um robô no grupo existirão tantos outros que poderão 
dar continuidade a execução da tarefa. Este trabalho apresenta uma proposta de arquitetura 
para a alocação de tarefas em sistema multi-robôs baseada na taxonomia MRTA e que utiliza 
acordo bizantino para garantir o consenso e a resiliência entre membros de um grupo de ro-
bôs. 
 
Palavras-chave: robótica móvel, sistemas multi-robôs, acordo bizantino, alocação de tarefas, 
algoritmo de eleição. 
ABSTRACT 
Mobile robots are increasingly being used to perform many tasks, such as in industry, service 
or military applications. Many tasks are complex and require the adoption of more than one 
robot to complete its execution. Thus, the formation of groups of robots is critical and must be 
based on the characteristics of the task to be performed, that is, the functional requirements it 
takes to carry it out, but also ensuring that there is a failure of one or more robots, the task can 
be completed, even in a longer computationally time. Thus the robot group members should 
be chosen based on physical criteria, behavioral (skills) and fault tolerance. One way to en-
sure the execution of a task by a group of robots is to adopt some fault tolerance technique, 
such as byzantine agreement. Byzantine Agreement is based on the principle that existing 
failure of one robot in the group there will be many others who will continue the task. This 
work presents a proposed architecture for task allocation in multirobot system based on 
MRTA taxonomy and byzantine agreement to ensure consensus and resilience among mem-
bers of a group of robots. 
 
Keywords: mobile robotics, multirobot systems, byzantine Agreement, task allocation, elec-
tion algorithm. 
LISTA DE ILUSTRAÇÕES 
Figura 2.1 Braço manipulador de linha industrial. ..................................................... 22 
Figura 2.2. Possível classificação para máquinas....................................................... 23 
Figura 2.3 Robô Curiosity. ......................................................................................... 23 
Figura 2.4. Robô móvel Asimo. .................................................................................. 24 
Figura 2.5. Ciclo percepção-ação. .............................................................................. 26 
Figura 2.6 Ligação entre robô, tarefa e ambiente. ...................................................... 26 
Figura 2.7 Alguns sensores presentes no robô PowerBot. ......................................... 28 
Figura 2.8 Alguns atuadores disponíveis no robô PowerBot. .................................... 28 
Figura 2.9 Classificação segundo a mobilidade. ........................................................ 29 
Figura 2.10 Robôs móveis terrestres. ......................................................................... 30 
Figura 2.11 Veículo aéreo autônomo Tiriba. ............................................................. 31 
Figura 2.12 Veículo autônomo aquático Argo Float. ................................................. 32 
Figura 2.13 Sistema de controle de robôs móveis. ..................................................... 33 
Figura 2.14 Arquitetura de controle reativa. .............................................................. 34 
Figura 2.15 Arquitetura de controle deliberativa. ...................................................... 35 
Figura 2.16 Arquitetura de controle híbrida. .............................................................. 36 
Figura 3.1 Robôs do projeto Swarmanoid. ................................................................. 40 
Figura 3.2 Representação de tarefas. .......................................................................... 42 
Figura 3.3 Clássico problema bizantino. .................................................................... 50 
Figura 4.1 Visão geral da arquitetura MRTA-B......................................................... 53 
Figura 4.2 Anúncio das capacidades por parte dos robôs da população. ................... 54 
Figura 4.3 Exemplo de um bloco de descrição da tarefa............................................ 55 
Figura 4.4 Exemplo do algoritmo do anel. ................................................................. 58 
Figura 4.5 Processo de eleição. .................................................................................. 59 
Figura 4.6 Arquitetura do sistema de controle de cada robô. ..................................... 60 
Figura 4.7 Exemplo do processo de estabelecimento do acordo bizantino. ............... 62 
 
LISTA DE TABELAS 
Tabela 1 Taxonomia de problemas de MRTA. .......................................................... 45 
Tabela 2 Abstração das informações do senso populacional ..................................... 64 
Tabela 3 Abstração dos requisitos das tarefas presentes nos BDT. ........................... 65 
Tabela 4 Resultado da alocação de tarefas com os respectivos grupos formados. .... 67 
 
LISTA DE ABREVIATURAS E SIGLAS 
GPS Global PositionSystem 
IA Inteligência Artificial 
IAD Inteligência Artificial Distribuída 
JPL Jet Propulsion Laboratory 
MR Mult Robots 
MRTA Multi Robot Task Allocation 
MT Mult Tasks 
NASA National Aeronautics and Space Administration 
RIA Robotic Industries Association 
SMR Sistema de Multi-robôs 
SR Single Robots Tasks 
ST Single Tasks Robots 
 
SUMÁRIO
1 INTRODUÇÃO ..................................................................................................... 15 
1.1 Objetivos ..................................................................................................................... 17 
1.2 Motivação e justificativa ............................................................................................... 17 
1.3 Metodologia ................................................................................................................. 18 
1.4 Organização do trabalho ............................................................................................. 19 
2 ROBÓTICA MÓVEL ............................................................................................ 21 
2.1 Breve histórico e importância ...................................................................................... 21 
2.2 Robôs móveis ............................................................................................................. 25 
2.2.1 Percepção e ação ...................................................................................................................... 27 
2.2.2 Classificação de robôs móveis quanto a mobilidade ................................................................. 29 
2.3 Sistemas de controle em robôs ................................................................................... 32 
2.4 Arquitetura de controle ................................................................................................ 33 
2.4.1 Arquitetura de controle reativa ................................................................................................... 34 
2.4.2 Arquitetura de controle deliberativa ........................................................................................... 34 
2.4.3 Arquitetura de controle híbrida ................................................................................................... 35 
3 COMPARTILHAMENTO DE TAREFAS EM ROBÓTICA MÓVEL ....................... 37 
3.1 Sistemas distribuídos .................................................................................................. 37 
3.2 Tarefas em robótica móvel .......................................................................................... 38 
3.2.1 Utilidade na execução de tarefas ............................................................................................... 40 
3.2.2 Tratamento de tarefas ................................................................................................................ 41 
3.2.3 Modelo e ambiente da tarefa...................................................................................................... 43 
3.3 Métodos de alocação de tarefas entre múltiplos robôs ................................................ 44 
3.4 Acordos em sistemas com falhas ................................................................................ 46 
3.4.1 Acordo bizantino ......................................................................................................................... 49 
4 ARQUITETURA DE COMPARTILHAMENTO DE TAREFAS .............................. 52 
4.1 Definições preliminares ............................................................................................... 52 
4.2 Visão geral da arquitetura proposta ............................................................................. 53 
4.3 Modelo de comunicação na arquitetura MRTA-B ......................................................... 56 
4.4 Formação de grupos ................................................................................................... 57 
4.5 Processo de eleição do coordenador e dos líderes de grupo ...................................... 58 
4.6 Arquitetura de controle dos robôs ................................................................................ 60 
4.7 Comunicação baseada em acordo bizantino ............................................................... 61 
5 ANÁLISE SOBRE A ARQUITETURA PROPOSTA ............................................. 63 
5.1 Definições gerais ......................................................................................................... 63 
6 CONSIDERAÇÕES FINAIS E PROPOSTAS PARA TRABALHOS FUTUROS .. 69 
6.1 Propostas para trabalhos futuros ................................................................................. 70 
REFERÊNCIAS ......................................................................................................... 71 
 
15 
 
1 INTRODUÇÃO 
Ao longo dos tempos a robótica móvel vem sendo aplicada a uma gama de tarefas 
(BRUMITT, 1998), tais como: exploração espacial (JPL - NASA), sondas de inspeção de du-
tos de petróleo e gás (robô G.I.R.I.N.O - Petrobrás), cirurgias (Da Vinci Surgical System - 
Intuitive Surgical), eletrodomésticos (robô Roomba - iRobot), entre outras. Em algumas apli-
cações o uso de apenas um único robô não é o suficiente para a solução do problema, neste 
caso faz-se necessário à utilização de um grupo de robôs móveis. 
A partir do interesse na área de robótica móvel se faz necessário entender além do 
funcionamento de um robô as tecnologias que permitem atribuir comportamentos mais com-
plexos, como o compartilhamento de tarefas entre robôs, que permite estender a capacidade 
individual de um robô conjuntamente com outros a problemas maiores ou mais elaborados. 
O compartilhamento, seja de informações ou recursos, tem se apresentado como so-
lução para diversos problemas de origem distribuída e assume um papel importante em dife-
rentes tecnologias, permitir seu uso pode significar economia de tempo, esforço, capacidade 
de processamento, vida útil de recursos, entre outros fatores. 
Não obstante, existem problemas que podem ser complexos o suficiente para exigir 
uma divisão em partes e distribuição entre entidades especializadas nessas partes para uma 
possível solução. Nessa divisão de tarefas, vê-se que, o termo distribuído permite uma série 
de benefícios no que tange a utilização de recursos, podendo-se aplicar vários conceitos com-
putacionais que otimizam esse processo, como, paralelismo, multiprocessamento, divisão da 
carga de trabalho, entre outros. 
O uso e o compartilhamento de tarefas entre robôs móveis pode significar uma van-
tagem na execução destas. Segundo Ribeiro et al.(2001), tarefas inerentemente distribuídas 
(espaço, tempo, funcionalidade), como busca e resgate, exploração, combate a incêndios são 
adequadas para o uso de um grupo de robôs. 
16 
 
Por mais que robôs possam apresentar cada vez mais um comportamento inteligente 
utilizando tecnologias que os aproximem da capacidade cognitiva e racional humana, o que 
mais diferencia e valoriza o seu uso é o compartilhamento de tarefas proporcionando uma 
variedade de possibilidades tecnológicas. Um sistema pode atribuir a capacidade de monito-
rar, explorar, avaliar locais objetos e operações em vastas regiões geográficas. 
Destaca-se o aproveitamento de robôs móveis para o provimento de diversos serviços 
e que por meio de um sistema de ampla abrangência possa produzir dados para análise e ge-
rência de amplos recursos dispostos geograficamente, a exemplo de um sistema de vigilância 
efetuado por robôs em locais e ambientes determinados (prédios, pátios, oceanos, florestas). 
A adoção de um grupo de robôs para a realização de algumas tarefas exige que o sis-
tema de controle seja bem projetado, neste caso, é importante que o sistema seja capaz de 
determinar o que cada robô fará, ou seja, qual a tarefa que ele executará.Para este tipo de 
aplicação faz-se necessário à adoção de um sistema de compartilhamento de tarefas, que visa 
dividir o problema em problemas menores e então associar cada problema menor a um tipo de 
robô, respeitando as características e potencialidade do robô. 
Para que seja possível o compartilhamento de tarefas entre um grupo de robôs mó-
veis é necessário a adoção de algum critério de alocação. A alocação de tarefas deve conside-
rar que esta pode ser executada por um único robô, ou por mais de um robô, e ainda, que al-
guns robôs possam realizar mais de uma tarefa (GERKEY; MATARIC, 2004). 
Devido à multiplicidade de atribuições entre robôs e tarefas pretende-se utilizar uma 
taxonomia que trata de problemas de alocação de tarefas, MRTA (Multi Robot Task Alloca-
tion) proposta por Gerkey e Mataric (2004), somadas à necessidade de gerência e alocação 
dessas tarefas entre o grupo. 
Em sistemas multi-robôs a comunicação entre os robôs é essencial e deve incorporar 
confiabilidade e segurança na troca de mensagens, para que um grupo de robôs possa entrar 
em concordância sobre condições aplicadas ao mesmo (aceitação de uma tarefa). Em razão 
disso será proposta uma abordagem confiável através de acordo bizantino, para garantir que a 
comunicação entre o grupo seja tolerante a falhas eventuais, que não podem ser previstas. 
A garantia de tolerância a falhas em grupos de robôs móveis está relacionada com o 
objetivo principal deste trabalho que culmina com a proposta de uma arquitetura capaz de 
alocar tarefas entre robôs de maneira confiável. A arquitetura proposta é chamada de MRTA-
17 
 
B, pois faz uso da taxonomia MRTA com comunicação confiável baseada no acordo bizanti-
no. 
1.1 Objetivos 
Esta sessão apresenta o objetivo geral e os objetivos específicos deste trabalho. 
 Geral 
O objetivo principal deste trabalho é o projeto de uma arquitetura de controle para 
grupos de robôs móveis que vise a alocação de tarefas em grupos de robôs móveis de maneira 
confiável com o uso de acordo bizantino. 
 Específicos 
Para se atingir o objetivo geral proposto neste trabalho, faz-se necessário o cumpri-
mento dos seguintes objetivos específicos: 
o Apresentar as principais técnicas de controle de robôs móveis; 
o Apresentar os algoritmos de alocação de tarefas entre robôs móveis, sobretu-
do a taxonomia MRTA; 
o Apresentar a abordagem de acordo bizantino; 
o Propor uma arquitetura de controle que seja baseada no modelo MRTA e que 
utilize acordo bizantino, intitulada MRTA-B; 
o Análise sobre a arquitetura MRTA-B. 
1.2 Motivação e justificativa 
O uso de robôs especializados no provimento de serviços é cada vez mais corrente 
em vários setores de atividades humanas, é uma tendência atual e futura, que se configura em 
atividades que são tediosas, repetitivas, insalubres, de risco, no entanto, alguns desses servi-
ços não podem ser realizados por um único robô, sendo necessária a utilização de um grupo 
(ZLOT, 2006). 
Como exemplo cita-se um grupo de robôs para serviços de busca e resgate ou com-
bate a incêndio, onde cada robô tenha capacidades próprias para executar um papel no serviço 
geral que somadas às capacidades de outros robôs determinam a realização do serviço. Um 
robô pode ter o gatilho do disparo de água, outro ser capaz de realizar arrombamentos e perfu-
18 
 
rações, outro ainda pode ter a capacidade de retirar escombros, entre outras especialidades 
necessárias. 
Isso leva a questões inerentes ao trabalho em grupo, que é cooperativo. Quando cada 
robô deve iniciar sua tarefa? Quais informações um robô deve repassar para outros no grupo? 
Quando uma tarefa executada por um robô não é mais necessária? Nessas condições a realiza-
ção de tarefas implica na proposição de soluções a problemas que influenciam diretamente no 
sucesso e qualidade do serviço geral. 
Um compartilhamento de tarefas bem realizado têm implicações positivas em siste-
mas distribuídos. Um sistema de robôs móveis deve ter uma arquitetura bem construída, nele 
a comunicação e divisão de tarefas tem papéis fundamentais. 
Cada robô, membro de um grupo, deve ter suas habilidades e modo de funcionamen-
to mapeado e classificado em virtude da distribuição de tarefas, que devem ser atribuídas para 
os robôs certos aptos a executá-las. 
A comunicação tem fator crucial e essencial em uma arquitetura distribuída exatamen-
te como se configura no uso de um grupo de robôs móveis. Os robôs pertencentes ao grupo, 
além de manter o conhecimento sobre outros membros, devem ter um meio para provar a ori-
gem das tarefas que passam a receber, pois existem inúmeras possibilidades de corrupção das 
atividades desses robôs, seja por códigos maliciosos ou mecanismos de ataque externos, por 
interesses individuais de um robô, por um robô do grupo ficar inoperante, entre outros fatores. 
O projeto de uma arquitetura que garanta a confiabilidade na realização de serviços 
por um grupo heterogêneo de robôs móveis é o principal objetivo deste trabalho. 
1.3 Metodologia 
Para a formulação da proposta apresentada neste trabalho foram estudados os concei-
tos e técnicas envolvidos na alocação de tarefas em SMR (Sistemas Multi-Robôs), bem como 
características, funcionamento e aplicação de robôs móveis. Ao longo do texto deste trabalho 
serão apresentados técnicas e algoritmos da computação distribuída, como, o algoritmo de 
eleição do anel e o consenso para tratamento de falhas bizantinas, sendo que, estes serão dire-
tamente aplicados ao projeto da arquitetura MRTA-B. 
A metodologia adotada levará em consideração uma arquitetura distribuída, onde um 
grupo heterogêneo de robôs será constituído. Cada grupo de robôs deverá solucionar um ou 
mais problemas, compartilhando entre si uma ou mais tarefas em busca de uma solução. No 
19 
 
projeto da arquitetura será levado em consideração, a estrutura, os componentes e suas liga-
ções, as entidades integrantes, os processos necessários, e as condições dentro da arquitetura 
proposta para que ela forneça soluções na área de SMR. 
Para que a alocação de tarefas seja possível será aplicado um ou mais algoritmos da 
arquitetura distribuída, sendo que, a divisão de tarefas será baseada na taxonomia MRTA, e 
no caso da comunicação será utilizado o acordo bizantino, sendo que os mesmos serão estu-
dados e exemplificados no decorrer deste trabalho. 
Os resultados obtidos serão exemplificados ao final deste trabalho e se basearam em 
um análise sobre a arquitetura de controle através de um estudo de caso. Serão feitas suposi-
ções sobre o funcionamento da arquitetura MRTA-B diante de uma população de robôs e uma 
lista de tarefas. 
1.4 Organização do trabalho 
Este documento, além desta introdução, está organizado em mais 5 (cinco) capítulos 
que versam sobre os seguintes conteúdos: 
 No Capítulo 2 serão descritas algumas definições em robótica móvel, modelos de 
arquiteturas, sua importância e aplicabilidade, bem como conceitos de projeto, arquitetura e 
implementação de robôs capazes de interagir com um ambiente real. 
O Capítulo 3 aborda tarefas em robótica móvel e técnicas que permitam seu compar-
tilhamento, tais como, decomposição e alocação, bem como a taxonomia MRTA (Multi Robot 
Task Allocation) para classificação de problemas de alocação de tarefas. O capítulo também 
aborda o conceito de acordos em sistemas com falhas bizantinas. 
O Capítulo 4 descreve a arquitetura proposta para o controle de múltiplos robôs mó-
veis. Apresenta uma descrição mais detalhada do problema, dos conceitos e definições que 
dão embasamento teórico a arquitetura MRTA-B que visa solucionar o problema de alocação 
de tarefas em grupos de robôs móveis de maneira confiável com a adoção de acordo bizanti-
no. 
O Capítulo 5 apresenta uma análise sistêmica do processo de alocação de tarefas a 
grupos de robôs com o uso da arquitetura MRTA-B. Para viabilizar a análise é descrito um 
estudo de caso.20 
 
O Capítulo 6 apresenta as considerações finais e lista um conjunto de tópicos que 
poderão ser realizados como trabalhos futuros. 
21 
 
2 ROBÓTICA MÓVEL 
Neste capítulo serão descritas algumas definições em robótica móvel, modelos de ar-
quiteturas, sua importância e aplicabilidade, bem como conceitos de projeto, arquitetura e 
implementação de robôs capazes de interagir com um ambiente real. 
2.1 Breve histórico e importância 
A robótica móvel possui um vasto campo de estudo, devido à necessidade de inter-
disciplinaridade de várias áreas do conhecimento como Mecatrônica, Tecnologias de Infor-
mação, Inteligência Artificial, Sistemas de Comunicação dentre outras (Rosário, 2005). 
As pesquisas em robótica visam o projeto de peças mecânicas como rodas ou esteiras, 
bem como o desenvolvimento de hardware e circuitos eletrônicos juntamente com softwares 
de controle que podem ser desde um simples programa até um sistema operacional embarca-
do. 
A história da humanidade revela sempre um interesse ligado à pesquisa e prática na 
produção de máquinas e dispositivos capazes de aliviar, substituir e ultrapassar a capacidade 
humana em tarefas cotidianas, como autômatos (ancestrais dos robôs atuais), robôs industriais 
(braços manipuladores), e mais atualmente robôs móveis. 
A aplicabilidade de robôs se expande com a convergência de novas tecnologias e no-
vas necessidades do ser humano. A evolução das ciências e economia, com destaque para 
circuitos integrados em microcomputadores, possibilitou o desenvolvimento e uso dos robôs 
sobre os mais diferentes aspectos na indústria, entretenimento e pesquisas cientificas (ROSA-
RIO, 2005). 
A partir da revolução industrial, após a segunda guerra mundial, os robôs começaram 
a ser empregados de forma mais ostensiva em indústrias, área onde encontraram maior di-
22 
 
mensão de aplicabilidade, com a substituição do trabalho braçal por estruturas mecânicas so-
bre bases fixas, braços mecânicos ou braços manipuladores. 
Os braços manipuladores em linhas de montagem realizam movimentos padroniza-
dos geralmente simples e repetitivos. Atualmente sistemas automatizados são amplamente 
utilizados nas indústrias, e em seguimentos como, exploração de ambientes e pesquisas cientí-
ficas, na medicina por meio de próteses e equipamentos cirúrgicos, na área militar e de segu-
rança com a substituição do ser humano pelo uso de robôs manipuladores em situações de 
risco (ROSARIO, 2005). A Figura 2.1 ilustra um braço manipulador fabricada pela KUKA 
Roboter. 
 
Figura 2.1 Braço manipulador de linha industrial. 
Extraído de Kuka (2012). 
A Robotic Industries Association (RIA) considera um robô como sendo um manipu-
lador programável multi-funcional capaz de mover materiais, partes, ferramentas ou dispositi-
vos específicos através de movimentos variáveis programados para realizar uma variedade de 
tarefas RIA apud (NEHMZOW, 2003). 
Segundo Silva (2003), esta definição descreve toda uma categoria de máquinas, sen-
do possível considerar qualquer equipamento capaz de ser programado como um robô. A uti-
lização de robôs (na condição de máquinas-ferramentas), de um modo geral, grandes, fixos, 
desprovidos de inteligência de alto nível e autonomia acontece a décadas nos cenários indus-
triais, pela substituição da mão de obra humana, em especial onde a riscos envolvidos. Uma 
possível classificação é ilustrada na Figura 2.2: 
23 
 
 
Figura 2.2. Possível classificação para máquinas. 
Extraído de Silva (2003). 
Os robôs móveis, pela inerente capacidade de locomoção e aplicabilidade em tarefas 
onde não existam limites geográficos, programáveis em alto nível e capazes de interagir com 
o ambiente via sensores e atuadores, são muito mais versáteis, independentemente da capaci-
dade de autonomia (PEREIRA, 2003). 
O desenvolvimento de robôs móveis tem aumentado, porém com um uso mais osten-
sivo e restrito, geralmente em indústrias, laboratórios e projetos de pesquisa de universidades, 
em instituições e agências de pesquisa. Um exemplo é o robô Curiosity desenvolvido no JPL 
(Jet Propulsion Laboratory) da California Institute of Technology em parceria com a NASA 
(National Aeronautics and Space Administration), que é considerado um laboratório de ciên-
cia móvel em solo marciano. A Figura 2.3 ilustra o robô Curiosity. 
 
Figura 2.3 Robô Curiosity. 
Extraído de Nasa (2012). 
24 
 
Segundo Marchi (2001) um robô móvel é um dispositivo mecânico montado sobre 
uma base não fixa que age sob o controle de um sistema computacional, equipado com senso-
res e atuadores que o permitem interagir com o ambiente. 
O foco na construção de robôs móveis, dotados de locomoção e capacidade de inte-
ragir com o ambiente expande as possibilidades do uso da robótica, mas insere um nível de 
complexidade exponencialmente maior à medida que a autonomia desses robôs e o nível de 
entropia nos ambientes em que estão imersos crescem. 
Em diversas áreas (ciência, exploração aeroespacial e terrestre, infraestrutura, indús-
tria, automatização de processos), esta complexidade é confrontada com a utilidade para as 
necessidades e progressos humanos presentes e futuros, denotando a importância da robótica 
móvel, seja para garantir a segurança do ser humano, seja pela economia de tempo e esforço. 
O produto dessa área são robôs capazes de se moverem em um ambiente e apresentar 
comportamentos frente ao ambiente em que estão inseridos. A Figura 2.4 ilustra o robô móvel 
Asimo projetado pela Honda. 
 
Figura 2.4. Robô móvel Asimo. 
Extraído de Honda Motors (2012). 
Robôs móveis podem ser de grande utilidade sobre vários aspectos e avaliações, so-
bretudo pelo potencial de realizar tarefas de complexidade acima da capacidade humana. 
Na literatura encontra-se algumas classificações para robôs móveis segundo suas 
funcionalidades dentre as quais citam-se: 
a) Robôs Industriais – São robôs que atuam em ambientes estruturados realizando 
tarefas em sequência, possuem conhecimento do ambiente em que estão imersos através de 
25 
 
informações pertinentes a suas atividades como, posição própria, posição de objetos. Estes 
robôs, geralmente são plataformas móveis que executam tarefas pesadas como carregar gran-
de quantidade de materiais, ferramentas, entre outros. Navegam em ambientes industriais se-
guindo linhas no chão e são denominados AGVs (Automated Guided Vehicles) (DE PIERI 
2002); 
b) Robôs de serviço – São robôs imersos em ambientes estruturados (residências, 
pátios, etc), e reconhecidos por meio de modelos internos. Estes robôs realizam atividades 
com certa autonomia frente a eventos inesperados como, desviar de pessoas e objetos, sendo 
que para isso processam a informação de sensores. São aplicáveis a uma gama de serviços 
gerais como, limpeza, transporte, vigilância, manipulação de objetos (DE PIERI 2002). 
c) Robôs de campo – São robôs que executam tarefas em ambientes desestruturados, 
pouco conhecidos, muitas vezes perigosos. Podem ser usados em exploração espacial, mine-
ração, busca e resgate, limpeza de acidentes nucleares, entre outras aplicações, (DE PIERI 
2002). Devido aos ambientes em que atuam, necessitam de alto grau de autonomia, possuem 
relativo hardware e executam algoritmos de alto nível para mapeamento, localização e loco-
moção, muitas vezes construindo modelos de mundo em tempo real. 
d) Para pesquisa − Robôs usados para estudos e pesquisas, geralmente na área aca-
dêmica, muitos destes são de baixo custo. 
e) Entretenimento - Robôs associados a diversão voltados a públicos variados. São 
construídos para apresentarem uma gama de atividades ou comportamentos ligados a entrete-
nimento, como interagir com o usuário, desempenhar papel de brinquedo inteligente, fornecer 
jogos ao usuário. 
2.2 Robôs móveis 
Basicamente um robô móvel é composto de uma arquitetura de hardware projetada 
para integrar e exercer funções sobre partes mecânicas eum sistema de controle. Segundo 
Bräunl (2008), um robô móvel é um sistema autônomo dotado de sensores e atuadores capaz 
de interagir com o mundo real. 
A interação com o ambiente se dá através de ciclos percepção-ação que consistem 
em três passos fundamentais (DE PIERI 2002): 
 Obtenção de informações sobre o ambiente por meio de sensores; 
26 
 
 Processamento das informações e seleção de ações a serem executadas; 
 Execução das ações selecionadas por meio de atuadores. 
Um robô realiza diversos ciclos de percepção-ação, modificando o estado do ambien-
te em busca da realização da tarefa (RIBEIRO et al., 2001). A Figura 2.5 ilustra o ciclo per-
cepção-ação. 
 
Figura 2.5. Ciclo percepção-ação. 
Adaptado de Perez (2006). 
Para que um robô apresente uma ou várias funcionalidades ele deve ser projetado so-
bre a perspectiva de como solucionar um problema do ponto de vista do ambiente em que está 
inserido, interagindo de forma a receber informações e agir nesse ambiente real. 
Robô, tarefa e ambiente estão fortemente ligados. O comportamento geral de um ro-
bô resulta da interação desses três fatores, que são interdependentes e influenciam um ao ou-
tro. A funcionalidade e operabilidade de um robô estão relacionadas a execução de uma ou 
mais tarefas em um ambiente determinado (NEHMZOW, 2003). A Figura 2.6 ilustra essa 
interdependência. 
 
Figura 2.6 Ligação entre robô, tarefa e ambiente. 
Adaptado de Nehmzow (2003). 
Nesse contexto deve-se compreender os meios de que um robô dispõe para interagir 
diretamente com o ambiente, ou seja, os sensores e atuadores. Isso envolve diretamente qual 
tipo de problema estará apto a resolver. 
27 
 
2.2.1 Percepção e ação 
Uma característica importante em robôs é a capacidade de extrair informações perti-
nentes do ambiente, resultando na sua percepção de mundo. Essa percepção é realizada atra-
vés de sensores. 
Um sensor é um dispositivo que pode sentir e mensurar certa propriedade física de 
um ambiente, como, temperatura, luminosidade, resistência ao toque, peso, tamanho, etc. São 
informações de baixo nível sobre o ambiente em que o robô atua, porém nenhum dispositivo é 
perfeito e estas informações podem ser imprecisas, contraditórias e ambíguas (NEHMZOW, 
2003). 
Existe uma grande variedade de sensores, que utilizam diferentes técnicas de medi-
ção e diferentes tipos de interface de controle (modo de acesso ao dispositivo). É de suma 
importância encontrar o sensor mais adequado a uma aplicação, com a técnica de aferição 
correta, e também características como, peso e tamanho, consumo de energia e preço adequa-
dos (BRÜANL, 2008). 
Do ponto de vista de robôs móveis é mais interessante classificar sensores da seguin-
te maneira (BRÜANL, 2008) e (NEHMZOW, 2003): 
 Proprioceptivo – monitoram o estado interno do robô, ex: encoders, monitor 
de nível de bateria, monitor de temperatura, potenciômetros, etc.; 
 Exteroceptivo – monitoram e adquirem informação do ambiente em que o 
robô está imerso ex: laseres, sonares, sensores de toque, câmeras, bússola, 
GPS, etc.; 
 Passivos – monitoram o ambiente sem afetá-lo e interferi-lo, ex: câmeras, 
microfones, sensores de toque, bússola, sensor de temperatura, entre outros; 
 Ativos – interagem com o ambiente emitindo energia sobre o mesmo e então 
adquirindo informações, laser, sonares, encoders, GPS, entre outros. 
Os sensores trabalharam com uma faixa de leitura de uma propriedade física, e for-
necem ao robô condições necessárias para se localizar no ambiente, reconhecer obstáculos, a 
velocidade que se desloca, o consumo de energia, entre outras. Caberá ao software de controle 
ou hardware lidar com imprecisões e erros nessas leituras. A Figura 2.7 ilustra alguns senso-
res de que dispõem o robô PowerBot da empresa Adept Mobile Robots. 
28 
 
 
Figura 2.7 Alguns sensores presentes no robô PowerBot. 
Extraído e adaptado de Adept Technology (2012) 
A maioria dos sensores permitem a coleta de informações básicas do ambiente, sal-
vos alguns que realizam o pré-processamento dessas informações. Cabe a um sistema de con-
trole, através de algoritmos especializados, desenvolver modelos elaborados do ambiente, 
junto com informações de alto nível que deem suporte a execução de tarefas pelo robô móvel. 
As ações de um robô por sua vez são desempenhadas diretamente pelos atuadores, 
que entram em contato com o ambiente. Na robótica móvel é mais comum o uso de motores 
elétricos (motores de corrente continua, motores de passo e servo motores), atuadores pneu-
máticos com válvulas e hidráulicos (BRÜANL, 2008) (NEHMZOW, 2003). 
Motores de corrente contínua que movem rodas são bons para serem sensoriados, is-
to é permitem que seja feita a leitura do movimento executado determinando a distância per-
corrida por um robô. Os motores de passo desenvolvem movimentos precisos e sutis. Estes 
motores elétricos atuam com pouco ruído e geram energia suficiente para uma grande varie-
dade de tarefas (NEHMZOW, 2003). 
Os atuadores pneumáticos e hidráulicos podem ser usados em partes mecânicas como 
garras, braços, pernas, entre muitas outras possibilidades. A Figura 2.8 ilustra alguns atuado-
res de que dispõem o robô PowerBot da empresa Adept Mobile Robots. 
 
Figura 2.8 Alguns atuadores disponíveis no robô PowerBot. 
Extraído e adaptado de Adept Technology (2012) 
29 
 
2.2.2 Classificação de robôs móveis quanto a mobilidade 
Os robôs móveis podem ser encontrados na literatura sob algumas classificações, 
conforme, De Pieri (2002), Siegwart (2004) e Brüanl (2008). Quanto a mobilidade os robôs 
podem ser classificados em três grandes grupos, aéreos, aquáticos e terrestres (DE PIERI 
2002). A Figura 2.9 ilustra esta classificação: 
 
Figura 2.9 Classificação segundo a mobilidade. 
Extraído de De Pieri (2002). 
A definição dos tipos de robôs móveis segundo a classificação da Figura 2.9 pode 
ser, segundo autores da área: 
Robôs com rodas – são robôs que utilizam uma um mais rodas para se locomove-
rem, podendo ser de projeto e construção simples devido a questões de custo e engenharia. 
Isso pode ser provado pelo simples fato de não ser necessário maior preocupação com equilí-
brio nesses robôs, já que passam todo tempo em contato com o chão. O foco no estudo e pro-
jeto de robôs com rodas passa para problemas como, tração, estabilidade, manobrabilidade e 
controle (SIEGWART, 2004). O robô móvel Seekur Jr. (ver Figura 2.10 a) da empresa Adept 
MobilesRobots é um exemplo de robô que se locomove por rodas e segundo o fabricante pode 
ser usado para pesquisa, segurança, exploração, entre outros. 
Robôs com esteira – robôs com direção diferencial, que lhe permitem boa 
manobrabilidade em terrenos irregulares. Durante a tração possui maior contato e fricção com 
o solo. São robôs mais robustos dotados de sensores, geralmente na parte de cima, que lhes 
permite navegarem com certa segurança ao atuarem sobre terrenos irregulares em atividades 
como busca e resgate, no desarmamento de bombas, etc. (BRÜANL, 2008). 
Alguns robôs com esteira da empresa iRobot (ver Figura 2.10 b), o iRobot Warrior, 
foram usados no episódio recente de terremoto e tsunami que arrasaram o nordeste do Japão e 
30 
 
que provocaram a explosão e o vazamento na usina nuclear de Fukushima. O iRobot Warrior 
é capaz de subir escadas e enfrentar terrenos íngremes e irregulares, possui uma garra que 
pode levantar até 52 quilos e bateria com autonomia de 5 horas, além de atuarem em ambien-
tes hostis, sendo por isso usados na manutenção da usina de Fukushima. 
Robôs com pernas – são robôs dotados de um conjunto de pernas para se locomove-
rem, biologicamente inspirados em animais e caracterizados por pontos de contato com o 
chão. Não são necessárias todas as pernas para manter o robô estável, sendo que por este fato 
se adaptam melhor em terrenos desestruturados e rudes, desdobrando-se nas habilidades de 
adaptabilidade, manobrabilidadee manipulação de objetos com destreza. Devido a locomoção 
por pernas são de complexidade maior, em vista de necessitarem partes articuladas que reque-
rem certo nível de liberdade para prover movimentos variados (SIEGWART, 2004). 
A empresa Boston Dynamics é um expoente na produção de robôs com locomoção 
por pernas, o robô Cheetah (ver Figura 2.10 c), por exemplo, é o mais rápido robô com pernas 
existente. O Cheetah possui quatro pernas flexíveis e foi inspirado no animal do qual carrega 
o nome, que é o mais rápido animal terrestre. A capacidade deste robô já lhe rendeu um re-
corde de velocidade em relação ao velocista recordista mundial, Usain Bolt. 
 
Figura 2.10 Robôs móveis terrestres. 
a) SeeKur Jr. Extraído de Adept Mobilerobots (2012). b) iRobot Warrior. Extraído de Irobot (2012) c) Cheetah. 
Extraído de Boston Dynamics (2012) 
31 
 
Robôs Aéreos – geralmente são aeronaves, principalmente aeromodelos ou LTAs 
(Lighter-Than-Air) (De Pieri, 2002), controladas remotamente, porém podem se tornar autên-
ticos robôs móveis autônomos, as chamadas UAVs (Unmanned Aerial Vehicles). Para isso 
recebem sensores e atuadores (GPS, servo-motores, etc), um hardware controlador embarcado 
e um sistema de controle próprio. Segundo Brüanl (2008), aeronaves autônomas são mais 
difíceis na concepção de projeto e desenvolvimento do que outros tipos de robôs móveis, de-
vido a exigência de alto grau de segurança, em virtude dos equipamentos que são de elevado 
custo e sobretudo para as pessoas, que podem ser expostas a situações de risco. 
 
Figura 2.11 Veículo aéreo autônomo Tiriba. 
Extraído de Inct-sec (2012). 
Um exemplo de robô aéreo e o Tiriba (Figura 2.11) que é um VANT (Veículo Aéreo 
Não Tripulado) produzido pela empresa AGX tecnologia em parceria com o INCT-SEC (Ins-
tituto Nacional de Ciência e Tecnologia em Sistemas Embarcados Críticos). Essa aeronave 
elétrica utiliza um sistema de controle e navegação totalmente autônomo, conta com uma uni-
dade de orientação automática baseada em sensores de pressão barométrica e inerciais e GPS 
(Sistema de Posicionamento Global), com a aplicação voltada na área de defesa civil, monito-
ramento ambiental e agrícola (INCT-SEC, 2012). 
Robôs Aquáticos – são veículos que navegam acima da água (modelos de embarca-
ções) ou abaixo dela (robôs-submarinos) controlados remotamente ou com autonomia própria 
por meio de um sistema de controle. São equipados com sensores (medidores de pressão) e 
atuadores (propulsores, balões de ar) que os permitem interagir e sobreviver em ambientes 
aquáticos. 
 Segundo Brüanl (2008), especialmente os AUVs (Autonomous Underwater Vehi-
cles) requerem um nível de habilidade adicional em relação a outros tipos de robôs, devido a 
pressão no fundo do mar que aumenta conforme a profundidade e a necessidade de manter 
32 
 
conexões externas com os sensores e atuadores. Os AUVs são muito promissores com relação 
ao custo de missões teleoperadas ou tripuladas, porém um grande problema é manter comuni-
cação com esses veículos, uma vez que, em imersão na água, métodos atuais de comunicação 
como WLAN ou Bluetooth não funcionam além de 50 cm, sendo o sonar o único método pos-
sível, mas com transmissão a taxas relativamente baixas. 
 
Figura 2.12 Veículo autônomo aquático Argo Float. 
Extraído de Global Ocean Observing System (2012). 
O robô aquático Argo Float (Figura 2.12), por exemplo, é utilizado para medir e regis-
trar a temperatura e o nível de salinidade das águas nos oceanos podendo submergir até apro-
ximadamente 2000 metros, através de um sistema de flutuabilidade por motor de fluídos e 
bexiga externa. Este robô tem um formato cilíndrico e possui motor, bateria, sensores, sistema 
hidráulico, antena de transmissão via satélite, um sistema de controle embarcado entre outras 
peças. O sistema embarcado é responsável por transmitir os dados coletados para algum saté-
lite, sendo que para isso o Argo tem de emergir a superfície, depois de determinado tempo sob 
a água. Esse robô faz parte do projeto Integrated Global Observation Strategy, que espalhou 
pelos oceanos do globo terrestre mais de 3000 unidades de Argos para formar um sistema 
global de coleta de dados dos oceanos. O projeto já tem uma enorme contribuição em pesqui-
sas e estudos, destacando-se as pesquisas em aquecimento global. 
2.3 Sistemas de controle em robôs 
Um sistema de controle de um robô é um software que comanda suas funcionalida-
des. Segundo Heinen (2002), existem duas partes interagindo com um sistema de controle: o 
sistema controlado (robô), sistema do qual se deseja controlar, e o ambiente, que não pode ser 
totalmente controlado diretamente pelo sistema de controle, mas interfere no seu funciona-
mento. A Figura 2.13 ilustra um modelo de sistema de controle. 
33 
 
 
Figura 2.13 Sistema de controle de robôs móveis. 
Extraído de (HEINEN, 2002). 
Um sistema de controle reage de acordo com as mudanças no ambiente, no sistema 
controlado ou da interação de ambos, sendo necessário o monitoramento dessas mudanças 
para agir quando necessário. Para auxiliar o sistema de controle podem ser utilizados sensores 
no robô ou no ambiente (HEINEN, 2002). 
Em um ambiente em que um robô deve simplesmente arrastar um objeto de um pon-
to a outro, qualquer situação ou condição que leve o robô a ser impedido ou a ignorar o com-
portamento de arrastar a caixa, deve induzir o sistema de controle a agir e conduzir novamen-
te o robô ao comportamento desejado e consequentemente ao estado esperado para todo o 
sistema. 
Os sistemas são projetados de acordo com alguma arquitetura. Os tipos de arquitetu-
ras representam modelos de projeto que podem ser de complexidade variável, como um sim-
ples programa, até um sistema operacional embarcado. 
2.4 Arquitetura de controle 
Uma arquitetura de software é composta por um conjunto de ações que são executa-
das conforme o ciclo percepção-ação, desta forma existe a interpretação de informações do 
ambiente fornecidas pelos sensores e sua relação pelos atuadores (PEREZ, 2006). 
Um robô que é controlado por um sistema computacional, tem o conhecimento dos 
dispositivos de hardware que dispõem para perceber e agir sobre o ambiente, nele algumas 
estruturas de software são responsáveis pela interpretação de como se comportar frente a este 
ambiente (ALVAREZ et al., 2001). 
34 
 
A arquitetura de controle determinará a forma de comportamento do robô. Dentre as 
arquiteturas destacam-se como principais: Reativa, Deliberativa e Híbrida. 
2.4.1 Arquitetura de controle reativa 
Nessa arquitetura o robô é controlado por um sistema baseado em ação-reação, onde 
por meio de sensores o robô capta dados que traduzidos em informações designam uma ou 
mais ações por meio de atuadores. O sistema de controle fica a cargo de atribuir a cada infor-
mação uma ação conveniente. 
Na reatividade ocorrem mapeamentos simples ligando estímulos sensoriais a respos-
tas (ações) (RIBEIRO et al., 2001). Como exemplo cita-se um robô móvel que faz uso de sen-
sores de toque que ao se chocar em uma parede recebe o sinal do sensor e induz uma reação 
contrária, como ir na direção oposta ao choque. A Figura 2.14 ilustra a arquitetura de controle 
reativa. 
 
Figura 2.14 Arquitetura de controle reativa. 
Adaptado de De Pieri (2002) 
Não é necessário manter um histórico de estados do robô e ambiente, nem mapea-
mento do o ambiente no qual o robô está inserido, mas uma continua captação do ambiente 
em tempo real suficiente para responder com ações do robô que lhe permitam a execução de 
uma tarefa. 
2.4.2 Arquitetura de controle deliberativa 
Na arquitetura deliberativa o robô faz uma análise de longo prazo onde ações serão 
alicerçadas para chegar a um objetivo. É realizado um planejamento sobre as ações. 
35 
 
A deliberação implica um estágio intermediário de planejamento, baseado em um 
modelo do mundo real onde o robô interage(RIBEIRO et al., 2001). Para isso é fundamental 
manter um histórico do ambiente, ações já tomadas, e dependendo da política de decisões até 
estados anteriores em que o robô se encontrava. Como exemplos podem ser citados os algo-
ritmos de mapeamento, localização e navegação, fundamentados na leitura do ambiente. 
Dessa forma esse planejamento pode acontecer por meio de mapas do ambiente (pré-
processados ou construídos em tempo real), bases de dados (estados anteriores do ambiente 
ou robô, ações tomadas) internas ou externas em relação ao robô, pré-processamento de sen-
sores por rotinas e algoritmos de alto nível, suporte a processamento de informações por nú-
cleos externos, entre outras formas. A 
Figura 2.15 ilustra um modelo de arquitetura deliberativa simplificado. 
 
Figura 2.15 Arquitetura de controle deliberativa. 
Na arquitetura deliberativa subentende-se a adição de inteligência ao robô que pode 
aumentar conforme a necessidade e complexidade exigida pelas tarefas e o ambiente. 
2.4.3 Arquitetura de controle híbrida 
A arquitetura híbrida integra às arquiteturas reativa e deliberativa. Sendo que a arqui-
tetura reativa fica responsável pelas respostas de curto prazo que são imediatas, e a arquitetura 
deliberativa produz um planejamento de longo prazo nas ações de um robô. 
Nesse tipo de arquitetura se realiza um planejamento sobre a definição e seleção de 
comportamentos reativos individuais (RIBEIRO et al., 2001). 
36 
 
Um terceiro módulo geralmente é necessário para gerenciar a comunicação entre o 
modulo reativo e o planejador. Assim tem-se uma arquitetura chamada de três camadas onde 
o comportamento reativo individual é controlado por meio de um planejamento (Mataric, 
2001) apud (PEREZ, 2006). O raciocínio é realizado sobre modelos internos do mundo. 
Nessa arquitetura a união intrínseca entre as arquiteturas anteriores (reativa e delibe-
rativa) ocorre por situações em que a resposta ao estímulo deve ser imediata, sacrificando-se o 
planejamento em um primeiro momento, mas mantendo registro de informações para planejar 
futuras ações, ou em condições que exijam comportamentos simples pelo robô. Um modelo 
da arquitetura híbrida é ilustrado na Figura 2.16. 
 
Figura 2.16 Arquitetura de controle híbrida. 
Uma comparação simples pode relacionar esta arquitetura ao funcionamento de or-
ganismos mais desenvolvidos. Pode-se observar, por exemplo, na natureza animais que agem 
por instinto, a exemplo, de situações emergenciais como reagir a situações de perigo, mas 
aprendem com a situação para se posicionar em relação a acontecimentos futuros. 
37 
 
3 COMPARTILHAMENTO DE TAREFAS EM ROBÓTICA MÓVEL 
Em sistemas onde a cooperação entre robôs deve existir o compartilhamento de tare-
fas torna-se um aspecto fundamental. Neste capítulo serão definidos os conceitos de tarefas 
em robótica móvel e das técnicas que permitam seu compartilhamento, tais como, decomposi-
ção e alocação, bem como a taxonomia MRTA (Multi Robot Task Allocation) para classifica-
ção de problemas de alocação de tarefas. O capítulo também aborda o conceito de acordos em 
sistemas com falhas bizantinas. 
3.1 Sistemas distribuídos 
Na realização de tarefas por um grupo de robôs móveis deve ser considerada uma ar-
quitetura distribuída, para que este grupo possa trabalhar conjuntamente. A distribuição está 
inerente à necessidade de o robô trabalhar em conjunto com outros robôs na solução de um 
problema. Segundo García et al. (2013), neste caso os robôs devem cooperar de forma expli-
cita e o sistema deve prover condições para que esses robôs apresentem comportamentos so-
ciais. 
Segundo Brumitt (1998) através da computação distribuída uma equipe cooperativa 
de robôs é mais capaz do que a simples soma de suas partes, esta equipe apresentará maior 
confiabilidade e a capacidade para completar tarefas distribuídas fisicamente. 
Lidar com sistemas de múltiplos robôs significa explorar problemas complexos em 
ambientes dinâmicos e imprevisíveis utilizando recursos escassos (ZLOT, 2006). A Computa-
ção distribuída possui diversos estudos e técnicas que fundamentam os sistemas de múltiplos 
robôs. 
38 
 
3.2 Tarefas em robótica móvel 
Uma forma de descrever uma tarefa em robótica móvel e definí-la como uma ativi-
dade a ser iniciada com requisitos mínimos e um objetivo específico, que pode ser realizada 
por uma ou mais entidades. Os requisitos mínimos de uma tarefa podem ser descritos como 
habilidades necessárias a sua execução, tal como, a detenção de uma ou mais ferramentas 
específicas, a capacidade de atender a um limite de tempo, um estado especifico da entidade 
executora, etc. 
Algumas habilidades básicas de robôs móveis são mapeamento, navegação e locali-
zação (SIEGWART, 2004). Estas capacidades são largamente estudadas em robótica móvel 
sobre diferentes abordagens e técnicas. A navegação condiz com a capacidade de um robô de 
se locomover em um ambiente seja ele fechado (indoor – salas, prédios, etc.) ou aberto (ou-
tdoor – campos, oceano, cidade, etc.). A localização é a descoberta pelo robô de sua posição 
no ambiente, seja local (parte do ambiente visível pelo robô) ou global (ambiente total em que 
o robô está imerso). Já o mapeamento refere-se a construção de mapas do ambiente e sua rela-
ção com o que o robô percebe a sua volta, um mapa pode ser conhecido a priore ou construído 
pelo robô a medida que navega e visualiza o ambiente. Para uma abordagem mais completa, 
essas três habilidades são combinadas. 
Além das três habilidades básicas citadas pode ser adicionado a robôs uma grande 
variação de capacidades para o cumprimento de atividades específicas. Robôs podem ter a 
capacidade de reconhecer objetos, manipular objetos (carregar, arrastar, agarrar, arremessar, 
absorver, etc.), subir escadas, voar, aquaplanar, mergulhar, perfurar materiais. Enfim, a uma 
enorme variação devido aos componentes computacionais, as ferramentas (sensores e atuado-
res), o sistema de controle, e os propósitos e problemas que o robô deve resolver. 
Dessa forma, como mencionado por Nehmzow (2003), há uma interdependência en-
tre robô, tarefa e ambiente. A tarefa de pegar um objeto situado a certa distância necessitará 
de um robô as capacidades de locomoção, reconhecimento e manipulação do objeto. A tarefa 
poderá ser dividida na sequência, localizar o objeto, se locomover até o objeto e pegá-lo. Se 
um robô não possuir essas três habilidades ele poderá solicitar auxílio para outros robôs que 
contemplam esses requisitos, isso pode ser entendido como um caso em que as capacidades 
estão distribuídas entre mais de um robô, mas nenhum possui as três ao mesmo tempo, sendo 
necessário cooperarem de alguma forma para a realização da tarefa. 
39 
 
As três habilidades para realizar a tarefa de pegar o objeto seriam suficientes para um 
robô em um ambiente estático, no entanto, se no percurso há movimentação de pessoas ou 
objetos ou até mesmo outros robôs, é necessário a habilidade de desvio de obstáculos. Assim 
pode-se reconhecer uma tarefa básica como uma única ação (locomoção de um ponto a outro), 
mas que pode exigir mais de uma capacidade. 
Existem capacidades que permitem a realização de uma enormidade de tarefas, assim 
como existem tarefas que só são realizáveis por mais de uma ação, como, por exemplo, pegar 
um objeto a certa distância ou arrastar uma caixa por uma determinada distância. Para o pro-
blema da caixa seria necessário localizar e reconhecer a caixa, ir até a caixa, e arrastar a caixa 
por uma distância determinada. A simples tarefa de reconhecer e localizar objetos em um am-
biente compreende mais de uma ação. A tarefa o robô e o ambiente são determinantes para 
solução de um problema. 
Robôs geralmente são construídos com propósitos específicos, sendo praticamente 
impossível construir um robô de propósito geral. Robôs móveis vêm sendo construídos para 
incluírem e superarem níveisde habilidades que os predisponham a realização de mais tare-
fas, apesar disso as tecnologias disponíveis e os custos ainda remetem os robôs a tarefas espe-
cificas e bem definidas. Como citado neste trabalho algumas tarefas são mais complexas e 
requerem múltiplas habilidades e ações, sendo impossível sua execução por um único robô. 
A utilização de SMR (Sistemas de Múltiplos Robôs) incide sobre tarefas complexas 
que necessitam o uso de mais de um robô. Nesses sistemas o principal desafio é gerenciar o 
uso dos diversos recursos disponíveis através do grupo de robôs, que devem se comunicar e 
coordenar suas ações para a execução de uma tarefa (CAO et al., 2010). 
Em SMR uma tarefa pode ser definida como um objetivo parcial que pode ser alcan-
çado independentemente do objetivo global de todo o sistema. Uma tarefa pode ser discreta 
(locomoção de um ponto a outro) ou continua (monitoramento de um objeto), e variar em 
escala de tempo, complexidade e especificidade, entre outras formas (GERKEY; MATARIC, 
2004). 
Um exemplo do uso de múltiplos robôs é o projeto científico Swarmanoid fundado 
pela Comissão Européia. O principal objetivo do projeto foi de criar um sistema de múltiplos 
robôs heterogêneos, autônomos e interligados dinamicamente para desenvolverem um com-
portamento de enxame (swarm) (SWARMANOID.ORG, 2012). Swarm é um problema muito 
estudado em IA (inteligência Artificial) e geralmente é estendido para a robótica móvel. 
40 
 
Segundo Swarmanoid.org (2012), o projeto fez uso de três tipos de robôs: eye-bots 
(ver Figura 3.1 c), hand-bots (ver Figura 3.1 b), e foot-bots (ver Figura 3.1 a) em problemas 
reais. O projeto ganhou o prêmio de melhor vídeo na competição, “AAAI 2011 video competi-
tion”. Os três robôs possuem capacidades específicas que combinadas podem solucionar cer-
tos tipos de problemas. 
 
 
Figura 3.1 Robôs do projeto Swarmanoid. 
Extraído e adaptado de Swarmanoid.org (2012). 
Tarefas complexas podem ser decompostas em tarefas menores e independentes 
sempre que possível, desta forma elas podem ser distribuídas para um grupo de robôs visando 
melhor aproveitamento dos recursos disponíveis. 
3.2.1 Utilidade na execução de tarefas 
A utilidade na realização de uma tarefa qualquer é um valor que quantifica a predis-
posição para sua execução. A utilidade pode ser calculada através de modelos de custos, 
grandezas que mensuram propriedades na execução de uma tarefa, tais como, o custo na utili-
zação de recursos, o fitness (aptidão para a execução da tarefa), uma recompensa para o de-
sempenho de um robô, ou prioridade de execução da tarefa (MOSTEO; MONTANO, 2010). 
O valor de utilidade pode surgir da combinação desses modelos de custos, comumen-
te listados na forma de (MOSTEO; MONTANO, 2010): 
 Utilidade = Recompensa – Custo 
 Utilidade = Fitness - Custo 
Em sistemas de múltiplos robôs a medição de utilidade pode ser usada para otimizar 
a realização de tarefas e consequentemente o desempenho do sistema. Conceitos comuns de 
utilidade propõem um valor único não negativo atribuído a um robô na execução de uma tare-
fa específica (GERKEY; MATARIC, 2004). 
http://aivideo.org/
http://aivideo.org/
41 
 
Gerkey e Mataric (2004) propõem uma inter-relação entre qualidade na execução da 
tarefa com os equipamentos disponíveis (ex: precisão na manipulação de um objeto), e o cus-
to no uso de recursos (ex: consumo de energia). Assim, é calculado o valor da utilidade na 
execução de uma tarefa por um robô supondo que este saiba sua aptidão. 
Formalmente essa inter-relação é definida, como: dado um robô R capaz de executar 
uma tarefa T, com uma qualidade esperada QRT e um custo CRT, tem-se uma utilidade URT co-
mo um valor resultante não negativo (GERKEY; MATARIC, 2004): 
Equação 1 Utilidade na Execução de uma Tarefa. 
URT = { 
QRT – CRT 
0 
se R é capaz de executar T 
e QRT > CRT 
 
Sob o ponto de vista da otimização a mensuração de utilidade tem por objetivo o al-
cance do melhor desempenho para um sistema fazendo a correta relação entre as capacidades 
e habilidades dos robôs, as condições e estados do robô e ambiente, os requisitos das tarefas e 
regras de alocação de tarefas impostas para o sistema. 
3.2.2 Tratamento de tarefas 
Existe uma diversidade de tarefas que podem ser executadas por robôs. Essa diversi-
dade leva a uma variedade de formas, entre os requisitos necessários e execução das tarefas. 
Segundo Dias et al. (2005), a forma mais comum entre as abordagens de atribuição 
de tarefas para robôs é delegar uma lista com tarefas em sua forma primitiva, ou seja, tarefas 
simples. Porém em sistemas de múltiplos robôs é mais natural o uso do termo missão, que é 
uma descrição de alto nível para uma tarefa complexa, que pode ser decomposta em sub-
tarefas. 
O tratamento de tarefas é realizado na forma de um planejamento sobre a questão do 
que deve ser feito. Geralmente isso envolve a decomposição de tarefas em partes. Para um 
melhor entendimento desta decomposição as seguintes terminologias para representação de 
tarefas são apresentadas (Zlot, 2006): 
 Decomposição e decomponibilidade – uma tarefa t pode ser decomposta se 
puder ser representada por um conjunto de sub-tarefas σt, que satisfazem al-
guma combinação (relação) específica (ρt) de sub-tarefas. O conjunto de rela-
42 
 
ções ρ pode definir restrições ou regras entre tarefas. O par (σt, ρt) é chamado 
decomposição de t; 
 Multiplas decomponibilidades – uma tarefa t que apresenta mais de uma 
forma de ser decomposta; 
 Tarefas Simples – pode ser uma tarefa atômica ou uma tarefa simples de-
componível; 
o Tarefa atômica – é uma tarefa que não pode ser decomposta, geral-
mente referida por uma única ação; 
o Tarefa simples decomponível – uma tarefa que pode ser dividida em 
passos e executada por uma única entidade; 
 Tarefa composta – é uma tarefa que pode ser decomposta em um conjunto 
formado por tarefas simples ou compostas, sendo que deve existir ao menos 
uma tarefa simples decomponível; 
 Tarefas complexas – uma tarefa que possui múltiplas decomponibilidades, 
em que ao menos existe um conjunto de tarefas alocadas entre várias entida-
des. Cada tarefa no conjunto pode ser simples, composta ou complexa. 
A Figura 3.2 ilustra a representação dos tipos de tarefas (KORSAH; DIAS; STENTZ, 2012). 
 
Figura 3.2 Representação de tarefas. 
Adaptado de Korsah, Dias e Stentz (2012). 
Na Figura 3.2 os círculos pontilhados representam possíveis alocações de tarefas pa-
ra robôs, os círculos preenchidos são tarefas atômicas, os retângulos são tarefas decompostas 
que formam uma estrutura de árvore. No primeiro quadro é ilustrada uma tarefa atômica sen-
do atribuída a um robô; o segundo quadro ilustra uma tarefa atômica e uma tarefa simples 
decomponível cada uma sendo atribuída a um robô; o terceiro quadro ilustra uma tarefa com-
posta formada por uma tarefa simples decomponível e sendo atribuída a dois robôs; o quarto 
quadro ilustra uma tarefa complexa alocada a múltiplos robôs e com várias possíveis decom-
posições (KORSAH; DIAS; STENTZ, 2012). 
Segundo Cao et al.(2010), a diferenciação entre os tipos de tarefas é necessária, pois 
no desenvolvimento de um algoritmo de alocação, tarefas complexas requerem uma modela-
gem de abstração em vários níveis, isso ocorre pois uma tarefa atômica não pode ser delegada 
43 
 
a múltiplos robôs e uma tarefa composta formada por uma única decomposição é predetermi-
nada e não alterável, sem a flexibilidade requerida por uma tarefa complexa. 
Um algoritmo de alocação para tarefas complexas deve lidar com atribuições dinâ-
micas para produzir resultados de execução melhores, nele a decomposição (planejamento) de 
tarefas deve ser flexível, pois alterações podem ser necessárias (ZLOT, 2006). Isso ocorre 
devido a dinamicidade no ambiente dessas tarefas, a quantidade de caminhos para soluções, 
as capacidades dos robôs e a quantidade de atribuiçõesentre robôs e tarefas. Soluções melho-
res não são predeterminadas, mas ocorrem dinamicamente em resposta a demanda do sistema. 
3.2.3 Modelo e ambiente da tarefa 
A descrição de uma tarefa no domínio de uma aplicação pode ser dada como um con-
junto de variáveis (duração, início e termino, habilidades necessárias), quando trata-se de tare-
fas simples a tendência é uma execução sequencial, em contrapartida tarefas complexas re-
querem mais flexibilidade na ordem de execução. 
A realização de uma tarefa está fortemente ligada a capacidade de um robô e as con-
dições do ambiente que permeiam a tarefa. 
O ambiente de uma tarefa é um conjunto que inclui tudo que envolve e interage com 
um sistema de controle. Segundo Russel e Norvig (2004), o ambiente, os sensores e atuadores 
de um agente (robô) e medidas de desempenho que qualifiquem a execução de uma tarefa por 
um agente podem ser agrupados no ambiente da tarefa. 
Ainda segundo Russel e Norvig (2004), algumas propriedades desses ambientes são 
úteis para compreensão da tarefa, tais como: 
 Completamente observável vs parcialmente observável – se todos 
os aspectos relevantes para a execução de uma ação são captados pe-
los sensores em cada instante de tempo o ambiente é completamente 
observável, porém se existe imprecisões de leitura ou estados do am-
biente inalcançáveis o ambiente torna-se parcialmente observável. 
 Determinístico vs estocástico – se um estado futuro é determinável 
pelo estado e ação atual do agente, o ambiente é determinístico, do 
contrário ele passa a ser estocástico, ou seja, sem qualquer previsibili-
dade diante da dinâmica de um ambiente. 
 Episódico vs sequencial – no ambiente episódico ações são atômicas 
e independem de ações anteriores. No ambiente sequencial ações atu-
ais influenciam nas posteriores afetando o resultado final. 
44 
 
 Discreto vs contínuo – ações no ambiente discreto são ponderadas 
em intervalos de tempo com uma sequência de fim determinado, já no 
ambiente contínuo as ações variam em intervalos distintos e contí-
nuos. 
 Único agente vs multi-agente –a presença de apenas um agente ou 
duas ou mais entidades convivem no ambiente e agem de forma coo-
perativa ou competitiva. 
Um projeto de sistema de controle deve levar em consideração o ambiente e suas 
propriedades. Sistemas de múltiplos robôs geralmente envolvem ambientes parcialmente ob-
serváveis, estocásticos e sequenciais com níveis exponenciais de complexidade. 
3.3 Métodos de alocação de tarefas entre múltiplos robôs 
Segundo Gerkey e Mataric (2004), um aspecto importante em sistemas de múltiplos 
robôs é a coordenação, em especial Problemas de Alocação de Tarefas entre Múltiplos Robôs 
(MRTA - do inglês Multi-Robot Task Allocation). 
Sistemas de múltiplos robôs geralmente envolvem soluções para tarefas de caráter 
complexo e nível exponencial caracterizado como NP-difícil (ZLOT, 2006). São sistemas que 
envolvem uma multiplicidade de formas de atribuição entre robôs e tarefas. O problema de 
alocação de tarefas refere-se a determinação de qual robô deve executar qual tarefa para al-
cançar um objetivo global (GERKEY; MATARIC, 2004). 
A alocação é necessária para tarefas que exijam um grupo de robôs detentor de re-
cursos limitados e dispersos entre seus membros. A alocação pode ser descrita como um mé-
todo que melhor faça uso desses recursos alcançando a execução da tarefa, levando em consi-
deração a interação dos membros do grupo e as alterações no ambiente. 
Gerkey e Mataric (2004) propõem uma taxonomia para classificar problemas comuns 
de MRTA facilitando pesquisas e trabalhos na área de Sistemas de Multi-Robôs. As seguintes 
definições são dadas: 
 Robôs de única tarefa (ST - Single-task robots) vs Robôs de múltiplas ta-
refas (MT - Multi-task robots): 
o ST: cada robô pode executar apenas uma tarefa em um intervalo de 
tempo. 
o MT: cada robô pode executar mais de uma tarefa no mesmo intervalo 
de tempo. 
45 
 
 Tarefas de único robô (SR - Single-Robot tasks) vs Tarefas de múltiplos 
robôs (MR - Multi-Robot tasks): 
o SR: cada tarefa requer apenas um robô para ser completada 
o MR: cada tarefa requer mais de um robô para ser completada. 
 Atribuição instantânea (IA - Instantaneous Assignment) vs Atribuição de 
tempo estendido (TA Time-Extended Assignment): 
o IA: a informação disponível sobre os robôs, as tarefas, e o ambiente 
somente permite a alocação instantânea de tarefas para cada robô, não 
há planejamento para futuras alocações. 
o TA: existe mais disponibilidade de informação, como conhecimento 
de todas as tarefas que precisam ser atribuídas, ou um modelo de co-
mo às tarefas iram chegar ao longo do tempo. Há a possibilidade de 
um planejamento sobre alocações de tarefas. 
A combinação dos itens acima descritos forma uma taxonomia onde os problemas de 
MRTA podem ser incluídos permitindo a classificação de seus domínios, facilitando assim, o 
desenvolvimento de uma abordagem de solução, seja a aplicação de algoritmos ou compreen-
são do nível de complexidade (GERKEY; MATARIC, 2004). A Tabela 1 ilustra as combina-
ções que podem representar campos de problemas. 
Tabela 1 Taxonomia de problemas de MRTA. 
 
Para cada campo da taxonomia podem ser descritos problemas comuns em MRTA. 
Dado um problema onde a atribuição é de um para um, seja uma condição entre ro-
bôs e tarefas (R¹ x T¹). As tarefas são procuradas por robôs de forma preferencial e cada robô 
possui habilidades específicas. Para cada robô postulante, aplica-se uma medida de nível de 
habilidade na execução de cada tarefa (GERKEY; MATARIC, 2004). 
Segundo Gerkey e Mataric (2004), o problema anterior pode ser descrito em termos 
da tripla taxonômica ST-SR-IA (Single-task robots-Single-Robot tasks- Instantaneous Assig-
nment). O objetivo de um sistema para essa tripla é atribuir para cada robô uma tarefa levando 
 ST-SR ST-MR MT-SR MT-MR 
IA ST-SR-IA ST-MR-IA MT-SR-IA MT-MR-IA 
TA ST-SR-TA ST-MR-TA MT-SR-TA MT-MR-TA 
46 
 
em consideração as prioridades de cada tarefa e as habilidades de cada robô de modo que se 
alcance um desempenho geral otimizado. Este problema simples pode ser solucionado por um 
programa linear, que a partir do nível de habilidade resolva a atribuição de robôs e tarefas por 
meio de busca. 
3.4 Acordos em sistemas com falhas 
Acordos entre processos em sistemas distribuídos é um requisito fundamental em um 
grande número de aplicações. Existem formas de coordenação entre processos que requerem a 
troca de informações para uma negociação em busca de entendimento em comum ou acordo 
(KSHEMKALYANI; SINGHAL, 2008). 
A tolerância a falhas indica que um sistema é capaz de prover seus serviços mesmo 
na presença de falhas. As falhas são ignoradas enquanto o sistema funciona normalmente 
(TANENBAUM; STEEN, 2008). 
Um processo de acordo é executado para se chegar a uma concordância entre um 
grupo de processos sobre um valor específico ou um conjunto de valores, que deve ser equi-
valente para todos os processos confiáveis. Essa concordância deve anteceder a realização de 
ações em um sistema (KSHEMKALYANI; SINGHAL, 2008). 
A utilização de acordos entre processos em sistemas distribuídos pode aumentar a to-
lerância a falhas, ao introduzir-se a capacidade de identificação de componentes faltosos e dos 
componentes capazes de dar continuidade ao sistema. 
Em contraste, geralmente com sistemas presentes em uma única máquina onde uma 
falha pode levar a uma parada total, sistemas distribuídos podem evitar danos maiores por 
falhas isolando e ignorando um componente faltoso (TANENBAUM; STEEN, 2008). 
Para uma melhor compreensão das falhas que tem importância em determinados sis-
temas são necessários modelos de falha. Existem classes de modelos de falha massivamente 
estudados, que especificam maneiras em que componentes de um sistema podem falhar 
(KSHEMKALYANI; SINGHAL, 2008). 
Alguns modelos de falhas podemser (TANENBAUM; STEEN, 2008): 
 Falha por queda – parada abrupta e prematura de um componente em um 
sistema. 
47 
 
 Falha por omissão – omissão no envio ou recebimento de mensagens inde-
pendente de suas funcionalidades. 
 Falha de temporização – um desvio do intervalo de tempo real especificado 
para prover um serviço corretamente. 
 Falha de resposta – o nó envia uma resposta com valor incorreto. 
 Falha bizantina – ocorre de maneira arbitraria em um componente que pro-
duz respostas inadequadas, muitas vezes de maneira maliciosa. 
A melhor forma para tornar um sistema tolerante a falhas é utilizando redundância, 
que pode ser (TANENBAUM; STEEN, 2008): 
 Redundância de informação: são adicionados bits extras com a intenção de 
permitir a recuperação de bits de dados deteriorados por meio de alguma téc-
nica, a exemplo do código de Hamming. 
 Redundância de tempo: se necessário, uma ação realizada é executada no-
vamente. 
 Redundância física: pode ser tanto de hardware como de software, sendo 
que são adicionados equipamentos ou processos extras para que um sistema 
tolere a falha em alguns componentes. 
Um objetivo ao se utilizar modelos de erros é tornar um sistema resiliente. A resili-
ência é descrita como a propriedade em que um objeto abstrato ou físico retorna a forma ori-
ginal ou posição após sofrer alterações ou perturbações. Representa a capacidade de regresso 
a forma original de equilíbrio após recuperação e superação contra adversidades. 
Segundo Tanenbaum e Steen (2008) uma boa forma de tornar um processo resiliente 
é o uso de processos redundantes (redundância física). É importante ter-se ciência de quanta 
redundância é necessário, para tonar um sistema tolerante a falhas o suficiente para ser consi-
derado K-tolerante. 
Um sistema é K-tolerante a falhas se este puder sobreviver a falhas em K componentes 
cumprindo suas especificações, como entendido para alguns casos (TANENBAUM; STEEN, 
2008): 
48 
 
 Falhas silenciosas: K componentes param sem propagar mensagens com er-
ros para outros componentes, nesse caso é necessário K+1 de redundância pa-
ra manter o sistema tolerante a falhas. 
 Falhas bizantinas: é necessário 2K + 1 de redundância de componentes que 
funcionam corretamente, para manter o sistema tolerante a falhas de um total 
de 3K +1 componentes. 
Um aspecto chave para contornar falhas de processos é organizar vários processos 
idênticos em um grupo no qual todos os processos recebam mensagens enviadas por qualquer 
membro do grupo (TANENBAUM; STEEN, 2008). 
Por diversos fatores relativos a sistemas distribuídos o alcance de um acordo só é 
possível levando-se em conta premissas que envolvem o sistema e suas características, a fim 
de garantir uma terminação ao algoritmo de acordo (FISCHER, 1985). 
Premissas diferentes sobre o sistema requerem soluções diferentes: se o atraso de 
comunicação é limitado ou não; se a entrega de mensagens é ordenada ou não; se a transmis-
são de mensagens é feita em unicast ou multicast (TANENBAUM; STEEN, 2008). 
Se em um sistema distribuído a comunicação não é confiável, mesmo que seus pro-
cessos não falhem, a concordância entre estes é impossível, pois não há limite para chegar a 
uma decisão comum devido a possível perda de mensagens. 
Algumas premissas em sistemas distribuídos são elencadas: 
 Comunicação síncrona/assíncrona - em uma comunicação assíncrona o 
alcance de um acordo é impossível, pois a garantia de entrega de mensagens 
entre processos não é alcançada tornando um processo de negociação inter-
minável. Na comunicação síncrona, o não recebimento de uma mensagem 
pode ser ignorado pelo uso de uma mensagem padrão pelo processo destina-
tário, permitindo que a negociação continue e eventualmente chegue ao fim 
(KSHEMKALYANI; SINGHAL, 2008). 
 Rede de comunicação - todos os processos em um sistema estão aptos a 
participarem de uma rede e trocarem mensagens (KSHEMKALYANI; SIN-
GHAL, 2008). 
 Canal confiável - considera-se que o canal de comunicação é confiável, ou 
seja, somente os processos podem falhar. Neste caso, um acordo pode ser im-
possível ou solucionável de maneira complexa (KSHEMKALYANI; SIN-
GHAL, 2008). 
 Identificação de emissor - o processo que recebe uma mensagem pode iden-
tificar o emissor. Essa premissa é importante em falhas bizantinas, pois mes-
49 
 
mo em virtude de um pacote de dados enviado com erros por um processo 
pode-se descobrir a identidade do emissor (KSHEMKALYANI; SINGHAL, 
2008). 
 Mensagem autenticada vs não autenticada - em mensagens não autenti-
cadas ou sem assinatura, um processo faltoso pode alterar a identificação do 
real emissor de uma mensagem, antes de reenviá-lá a outros processos. Em 
mensagens autenticadas por técnicas como assinatura digital, uma mensagem 
com identificação alterada e reenviada por um processo malicioso pode ser 
detectada por outros processos (KSHEMKALYANI; SINGHAL, 2008). 
3.4.1 Acordo bizantino 
Sistemas com vários nós processadores, dentre esses os sistemas multi-robôs, podem 
falhar de maneira arbitrária, sendo que, uma falha é vista como um comportamento incomum 
ao especificado para um sistema, e é oriunda de um ou mais erros no estado do sistema 
(KSHEMKALYANI; SINGHAL, 2008). 
As falhas podem ser oriundas de defeitos de software ou hardware, de erros de proje-
to, ou ainda por motivos alheios (ex. queima de componente eletrônico, incêndio, invasões 
etc.) (LUIZ, 2009). 
Por sua vez uma falha é caracterizada como a causa que originou um erro em um sis-
tema, que pode ser de razão física (hardware) ou algorítmica (fluxo de execução de um sof-
tware) (TANENBAUM; STEEN, 2008). 
A falha arbitrária (ou bizantina) e o tipo de falha mais severa e o menos restritivo, 
pois encapsula todos os modelos de falhas conhecidos (LUIZ, 2009). 
Portanto, segundo Honorato (2009), a falha bizantina engloba qualquer comporta-
mento diferente do considerado correto para um sistema por parte de um componente, e técni-
cas que toleram esse tipo de falha não assumem modelos sobre comportamentos do compo-
nente, tolerando qualquer comportamento fora do correto. 
Segundo Luiz (2009), cresce o número de pesquisas para desenvolvimento de solu-
ções práticas de suporte a aplicações distribuídas tolerantes a faltas bizantinas nos últimos 
anos como desafio a criação de protocolos que forneçam robustez, confiabilidade e segurança 
em sistemas distribuídos. 
O clássico problema de falha bizantina foi inspirado pelas longas batalhas pelo impé-
rio de Bizantino na idade média. Considera-se que quatro exércitos dispostos para batalha ao 
redor da cidade de Bizâncio, cada qual controlado por um general devem coordenar um ata-
50 
 
que. O ataque só terá sucesso se for simultâneo pelas quatro armadas, dessa forma o horário 
exato do ataque tem de ser negociado por meio de mensagens (KSHEMKALYANI; SIN-
GHAL, 2008). A Figura 3.3 ilustra o clássico problema de falha bizantina, na qual, quatro 
generais apresentam comportamento arbitrário e enviam mensagens confusas. 
 
Figura 3.3 Clássico problema bizantino. 
Extraído de Kshemkalyani; Singhal, (2008). 
Três modelos de falha para o problema são apresentados por Kshemkalyani; Singhal, 
(2008): 
 um modelo assíncrono indica um tempo ilimitado para a transmissão de men-
sagens; 
 um modelo onde ocorre perda de mensagens é descrito como um mensageiro 
sendo capturado; 
 um modelo bizantino é descrito como um general traidor, que tenta corrom-
per o processo de acordo enviando informações erradas. 
Considerando o modelo assíncrono no simples cenário do ataque a Bizâncio, se um 
general enviar um mensageiro a outro esperando uma resposta de confirmação da chegada da 
mensagem, uma vez que o tempo é indeterminado, a troca de mensagens não terá fim e con-
sequentemente não haverá acordo. 
Para os demais modelos um acordo será possível em se tratando de um sistema sín-
crono. Uma negociação