Submitted by Erika Demachki (erikademachki@gmail.com) on 2017-03-24T21:09:18Z
No. of bitstreams: 2
Dissertação - Lucas da Silva Assis - 2017.pdf: 4403122 bytes, checksum: b6716ca532c65ba98f07fab680e6569d (MD5)
license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Approved for entry into archive by Luciana Ferreira (lucgeral@gmail.com) on 2017-03-28T11:39:32Z (GMT) No. of bitstreams: 2
Dissertação - Lucas da Silva Assis - 2017.pdf: 4403122 bytes, checksum: b6716ca532c65ba98f07fab680e6569d (MD5)
license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Made available in DSpace on 2017-03-28T11:39:32Z (GMT). No. of bitstreams: 2
Dissertação - Lucas da Silva Assis - 2017.pdf: 4403122 bytes, checksum: b6716ca532c65ba98f07fab680e6569d (MD5)
license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5)
Previous issue date: 2017-02-16 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / between desired points. These optimal paths can be understood as trajectories that best achieves an
objective, e.g. minimizing the distance travelled or the time spent. Most of usual path planning techniques
assumes a complete and accurate environment model to generate optimal paths. But many of the real world
problems are in the scope of Local Path Planning, i.e. working with partially known or unknown
environments. Therefore, these applications are usually restricted to sub-optimal approaches which plan an
initial path based on known information and then modifying the path locally or re-planning the entire path
as the agent discovers new obstacles or environment features. Even though traditional path planning
strategies have been widely used in partially known environments, their sub-optimal solutions becomes
even worse when the size or resolution of the environment's representation scale up.
Thus, in this work we present the CGPlan (Constructive Genetic Planning), a new evolutionary approach
based on the Compact Genetic Algorithm (cGA) that pursue efficient path planning in known and unknown
environments. The CGPlan was evaluated in simulated environments with increasing complexity and
compared with common techniques used for path planning, such as the A*, the BUG2 algorithm, the RRT
(Rapidly-Exploring Random Tree) and the evolutionary path planning based on classic Genetic Algorithm.
The results shown a great efficient of the proposal and thus indicate a new reliable approach for path
planning of mobile agents with limited computational power and real-time constraints on on-board
hardware. / O planejamento de rotas é um recurso importante para agentes móveis, permitindo-lhes
encontrar caminhos ideais entre os pontos desejados. Neste contexto, caminhos ideais podem
ser entendidos como trajetórias que melhor atingem um objetivo, minimizando a distância
percorrida ou o tempo gasto, por exemplo. As técnicas tradicionais tendem a considerar um
modelo global do ambiente, no entanto, os problemas reais de planejamento de rotas
usualmente estão no âmbito de ambientes desconhecidos ou parcialmente desconhecidos.
Portanto, aplicações como essas geralmente são restritas a abordagens subótimas que
planejam um caminho inicial baseado em informações conhecidas e, em seguida, modificam o
caminho localmente ou até planejando novamente todo o caminho à medida que o agente
descobre novos obstáculos ou características do ambiente. Sendo assim, mesmo as estratégias tradicionais de planejamento de caminhos sendo amplamente utilizadas em
ambientes parcialmente conhecidos, suas soluções subótimas se tornam ainda piores quando
o tamanho ou a resolução da representação do ambiente aumentam.
Por isso, neste trabalho apresentamos o CGPlan (Constructive Genetic Planning), uma nova
abordagem evolutiva baseada no Algoritmo Genético Compacto (cGA) que almeja um
planejamento eficiente de caminho em ambientes conhecidos e desconhecidos. O CGPlan foi
avaliado em ambientes simulados com crescente complexidade e comparado a técnicas
comuns utilizadas para o planejamento do caminho, como o A*, o algoritmo BUG2, o RRT
(Rapidly-Exploring Random Tree) e o planejamento evolutivo do caminho usando clássico
Algoritmo Genético. Os resultados mostraram uma grande eficiência da proposta e indicam
uma nova abordagem confiável para o planejamento de rotas de agentes móveis com poder
computacional limitado e restrições em tempo real no hardware.
| Identifer | oai:union.ndltd.org:IBICT/oai:repositorio.bc.ufg.br:tede/7030 |
| Date | 16 February 2017 |
| Creators | Assis, Lucas da Silva |
| Contributors | Soares, Anderson da Silva, Laureano, Gustavo Teodoro, Soares, Anderson da Silva, Laureano, Gustavo Teodoro, Camilo Junior, Celso Gonçalves, Osório, Fernando Santos |
| Publisher | Universidade Federal de Goiás, Programa de Pós-graduação em Ciência da Computação (INF), UFG, Brasil, Instituto de Informática - INF (RG) |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | English |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/masterThesis |
| Format | application/pdf |
| Source | reponame:Biblioteca Digital de Teses e Dissertações da UFG, instname:Universidade Federal de Goiás, instacron:UFG |
| Rights | http://creativecommons.org/licenses/by-nc-nd/4.0/, info:eu-repo/semantics/openAccess |
| Relation | -3303550325223384799, 600, 600, 600, 600, -7712266734633644768, 3671711205811204509, 2075167498588264571 |
Page generated in 0.0025 seconds