CGPlan: a scalable constructive path planning for mobile agents based on the compact genetic algorithm

Página do item simplificado
dc.contributor.advisor-co1Laureano, Gustavo Teodoro
dc.contributor.advisor-co1Latteshttp://lattes.cnpq.br/4418446095942420por
dc.contributor.advisor1Soares, Anderson da Silva
dc.contributor.advisor1Latteshttp://lattes.cnpq.br/1096941114079527por
dc.contributor.referee1Soares, Anderson da Silva
dc.contributor.referee2Laureano, Gustavo Teodoro
dc.contributor.referee3Camilo Junior, Celso Gonçalves
dc.contributor.referee4Osório, Fernando Santos
dc.creatorAssis, Lucas da Silva
dc.creator.Latteshttp://lattes.cnpq.br/9653117035626347por
dc.date.accessioned2017-03-28T11:39:32Z
dc.date.issued2017-02-16
dc.description.abstractbetween 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.eng
dc.description.provenanceSubmitted 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)eng
dc.description.provenanceApproved 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)eng
dc.description.provenanceMade 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-16eng
dc.description.resumoO 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.por
dc.description.sponsorshipCoordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPESpor
dc.formatapplication/pdf*
dc.identifier.citationASSIS, L. S. CGPlan: a scalable constructive path planning for mobile agents based on the compact genetic algorithm. 2017. 74 f. Dissertação (Mestrado em Ciência da Computação) - Universidade Federal de Goiás, Goiânia, 2017.por
dc.identifier.urihttp://repositorio.bc.ufg.br/tede/handle/tede/7030
dc.languageporpor
dc.publisherUniversidade Federal de Goiáspor
dc.publisher.countryBrasilpor
dc.publisher.departmentInstituto de Informática - INF (RG)por
dc.publisher.initialsUFGpor
dc.publisher.programPrograma de Pós-graduação em Ciência da Computação (INF)por
dc.rightsAcesso Abertopor
dc.rights.urihttp://creativecommons.org/licenses/by-nc-nd/4.0/
dc.subjectRobótica móvelpor
dc.subjectPlanejamento de rotaspor
dc.subjectComputação evolutivapor
dc.subjectAlgoritmo genético compactopor
dc.subjectMobile roboticseng
dc.subjectPath planningeng
dc.subjectEvolutionary computingeng
dc.subjectCompact genetic algorithmeng
dc.subject.cnpqCIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAOpor
dc.titleCGPlan: a scalable constructive path planning for mobile agents based on the compact genetic algorithmpor
dc.title.alternativeCGPlan: um planejamento de rotas construtivo e escalável para agentes móveis baseado no algoritimo genético compactopor
dc.typeDissertaçãopor

Arquivos

Pacote Original
Agora exibindo 1 - 1 de 1
Nenhuma Miniatura disponível
Nome:
Dissertação - Lucas da Silva Assis - 2017.pdf
Tamanho:
4.2 MB
Formato:
Adobe Portable Document Format
Descrição:
Baixar
Licença do Pacote
Agora exibindo 1 - 1 de 1
Nenhuma Miniatura disponível
Nome:
license.txt
Tamanho:
2.11 KB
Formato:
Item-specific license agreed upon to submission
Descrição:
Baixar

Coleções

Mestrado em Ciência da Computação (INF)