Planejamento Robusto de Caminho Mais Curto Estocástico via Amostragem Incremental Sensível ao Risco

Com a prevalência de problemas de Caminho Mais Curto Estocástico (SSP) em indústrias de alto risco, como entrega autônoma de última milha e gerenciamento da cadeia de suprimentos, algoritmos de planejamento robustos são cruciais para garantir a conclusão bem-sucedida das tarefas enquanto mitigam resultados perigosos. As técnicas tradicionais de amostragem incremental sob restrições de chance para resolver problemas de SSP tendem a ser excessivamente conservadoras e normalmente não consideram a probabilidade de eventos indesejáveis de cauda. Propomos uma abordagem alternativa sensível ao risco, inspirada no algoritmo de planejamento de Árvores Aleatórias Exploradoras Rápidas (RRT*), que seleciona nós ao longo de segmentos de caminho com Valor Condicional em Risco (CVaR) mínimo. Nossa motivação repousa na coerência passo a passo da medida de risco CVaR e na subestrutura ótima do problema SSP. Assim, otimizar em relação ao CVaR em cada iteração de amostragem leva necessariamente a um caminho ótimo no limite do tamanho da amostra. Validamos nossa abordagem por meio de experimentos numéricos de planejamento de caminho em um mundo de grade bidimensional com obstáculos e comprimentos de segmentos de caminho estocásticos. Nossos resultados de simulação mostram que incorporar risco no processo de crescimento da árvore produz caminhos com comprimentos significativamente menos sensíveis a variações no parâmetro de ruído, ou, equivalentemente, caminhos que são mais robustos à incerteza ambiental. Análises algorítmicas revelam complexidades de tempo de consulta e espaço de memória semelhantes ao procedimento RRT* de base, com apenas um aumento marginal no tempo de processamento. Esse aumento é compensado por uma sensibilidade ao ruído significativamente menor e taxas de falha do planejador reduzidas.