1 Formulação do problema
Uma pessoa perdida, na posição desconhecida \(p\in\mathbb R^2\), carrega um celular que emite sinal. Deseja-se determinar as posições horizontais \(q_1,\dots,q_N\) de \(N\) drones, voando à altitude \(h\), de modo que as medições de intensidade do sinal (RSSI) localizem a pessoa com a menor incerteza possível.
Cada drone mede a potência recebida segundo o modelo de perda de percurso log-distância:
Com ruído gaussiano, a informação de Fisher de uma medição é \(\frac{1}{\sigma^2}\nabla_p\mu\,\nabla_p\mu^\top\). Derivando (1), com \(v = p-q_i\):
Medições independentes somam informação, e um termo a priori fraco evita matriz singular:
Cada \(F_i\) tem posto 1: um drone informa apenas na direção da reta drone–pessoa, e é preciso olhar de direções diferentes para triangular. Pelo limite de Cramér-Rao, nenhum estimador não viesado tem covariância menor que \(F^{-1}\); a elipse de 95% é \(\{x : x^\top F x \le 5{,}991\}\). O problema consiste em determinar \(q_1,\dots,q_N\) que maximizam
sujeita às restrições
Na missão de busca entra ainda o deslocamento máximo por rodada:
Maximizar o determinante (critério D-ótimo) equivale a minimizar a área da elipse de confiança. Os dados do cenário padrão estão na Tabela 1.
| Grandeza | Símbolo | Valor |
|---|---|---|
| Potência de referência | \(P_0\) | −40 dBm |
| Expoente de perda de percurso | \(\eta\) | 2,5 |
| Ruído do sinal | \(\sigma\) | 4 dB (1 a 10) |
| Altitude de voo | \(h\) | 100 m (30 a 250) |
| Número de drones | \(N\) | 4 (1 a 8) |
| Medições por drone | \(n_i\) | 10 (1 a 50) |
| Área de busca | \(L\times L\) | 1 km × 1 km |
| Base dos drones | \(b\) | (90; 910) m |
| Separação mínima | \(d_{\min}\) | 40 m (0 a 150) |
| Informação a priori | \(\sigma_0\) | 1 km |
| Constante de (2), com σ = 4 dB | \(k\) | 7,3676 |
2 Classificação do problema
- Variáveis. As coordenadas \(q_{i,x}, q_{i,y}\), \(2N\) ao todo, são controladas e contínuas. Na aba de posicionamento a posição \(p\) da pessoa é dada e o problema é determinístico; na missão \(p\) é desconhecida e precisa ser estimada a partir das medições ruidosas, o que acrescenta um problema de estimação (seção 5).
- Restrições. A região \(\Omega\) é um subconjunto próprio de \(\mathbb R^{2N}\); trata-se de otimização condicional. As restrições (5) são diretas (regionais); (6), (7) e (8) são funcionais, não lineares, do tipo desigualdade. As restrições (5), (6) e (8) definem conjuntos convexos; a separação (7) não, pois exclui o interior de um disco.
- Tipo de modelo. A função objetivo e a restrição (7) são não lineares; logo, o problema é de programação não linear, e não convexa. A função objetivo não é separável: o termo \(F^{-1}\) acopla todos os drones.
- Subproblema de cobertura. Com um único drone e memória das células já vasculhadas, a escolha da rota é discreta e sequencial, com estrutura de etapas: é tratada pela programação dinâmica (seção 6).
3 Existência da solução e convexidade
3.1 Teorema de Weierstrass
- \(\Omega\) é não vazio: no cenário padrão (N = 4, \(d_{\min}\) = 40 m) basta tomar os drones em torno da base, separados de 40 m. Em geral, \(\Omega\) é não vazio enquanto a região permitida por (5) e (6) comportar \(N\) pontos separados de \(d_{\min}\); caso contrário, o problema é inviável.
- \(\Omega\) é fechado: todas as desigualdades (5)–(8) são não estritas.
- \(\Omega\) é limitado: pela caixa (5), \(\Omega\subset[0;L]^{2N}\).
- \(J(q)\) é contínua: pelo termo a priori, \(F(q)\succeq\sigma_0^{-2}I\), de modo que \(\det F > 0\) em todo ponto e \(\log\det F\) é contínua e diferenciável.
As quatro condições são satisfeitas, e \(J\) alcança o seu máximo em pelo menos um ponto de \(\Omega\).
3.2 Convexidade
A função \(\log\det\) é côncava em relação à matriz \(F\), mas \(F\) depende de \(q\) de forma não linear. A informação de um drone a distância horizontal \(r\) é proporcional a \(r^2/(r^2+h^2)^2\), que cresce até \(r=h\) e depois decresce: não é côncava. Além disso, a restrição (7) torna \(\Omega\) não convexo. Consequências:
- podem existir máximos locais que não são globais, e o método de gradiente pode parar neles (seção 4.6);
- o máximo global não é único: girar toda a formação em torno de \(p\) troca \(F\) por \(QFQ^\top\), com o mesmo determinante, de modo que há uma família contínua de soluções.
3.3 Solução de referência
Sem as restrições (6)–(8) ativas, o problema tem solução analítica, usada como referência para medir a precisão do método numérico. Derivando \(r^2/(r^2+h^2)^2\) em \(r^2\), o máximo ocorre em \(r=h\): um drone exatamente em cima da pessoa não informa nada na horizontal. As direções devem ser balanceadas, \(\sum_i u_iu_i^\top = \tfrac N2 I\), o que equivale a \(\sum_i e^{2i\theta_i}=0\) (o ângulo é dobrado porque \(uu^\top\) não distingue \(u\) de \(-u\)). Então
No cenário padrão: \(\log\det F^\star = -11{,}20707\), erro RMS mínimo \(\sqrt{\operatorname{tr}F^{-1}} = 23{,}30\) m e área da elipse de 95% igual a 5108 m². A solução não é única: quatro drones em cruz e quatro drones num semicírculo, a 45° um do outro, satisfazem igualmente \(\sum e^{2i\theta_i}=0\).
4 Solução pelo método do gradiente projetado
4.1 Princípio do método
O método do gradiente projetado é um método numérico de primeira ordem para problemas com restrições. A partir de um ponto permissível \(q^{(k)}\), dá-se um passo de subida pelo gradiente e projeta-se o resultado em \(\Omega\):
A projeção em (5), (6) e (8) é direta (corte na caixa e no disco). Na parte não convexa (7), ela é calculada iterativamente por pares: cada dupla a menos de \(d_{\min}\) é afastada simetricamente e reprojetada nas demais restrições, inclusive quando os dois drones começam sobrepostos. Os drones partem da base, e o processo termina quando nenhum drone se desloca mais de 1 mm numa iteração.
4.2 Gradiente da função objetivo
De \(\mathrm d \log\det F = \mathrm{tr}(F^{-1}\mathrm dF)\), com \(A = F^{-1}\) e \(D = \lVert v\rVert^2+h^2\):
O gradiente analítico foi conferido contra diferenças finitas, com erro relativo de \(2{,}8\times10^{-8}\) no ponto exato e \(4{,}9\times10^{-9}\) com o critério robusto.
4.3 Comprimento do passo
O passo \(t_k\) é escolhido pela regra de Armijo: parte-se do dobro do passo aceito na iteração anterior e divide-se por 2 até que
O deslocamento de cada drone é limitado a 30 m por iteração, como uma velocidade máxima, o que também deixa a animação legível. O app permite trocar por um passo fixo \(t\), para comparar.
4.4 Escala do passo
No gradiente puro todos os drones andam com o mesmo \(t\), mas o gradiente de um drone distante é muito menor, porque a informação cai com \(1/r^2\) e sua derivada com \(1/r^3\). Com o passo limitado pelo drone mais rápido, os mais distantes ficam para trás. É a fraqueza clássica do método do gradiente quando as variáveis têm sensibilidades muito diferentes, e a correção padrão é o pré-condicionamento por blocos: o gradiente de cada drone é ampliado por \(w_i=\min\!\left(20,\ \lVert g\rVert_{\max}/\lVert g_i\rVert\right)\). Como os pesos são positivos, a direção continua sendo de subida, \(\sum_i w_i\lVert\nabla_{q_i}J\rVert^2 > 0\), e perto do ótimo o método volta a ser o gradiente comum. A Tabela 2 mostra o efeito.
| Escala do passo | Iterações até parar | \(\log\det F\) final | Distância à pessoa |
|---|---|---|---|
| Passo comum (gradiente puro) | 147 | −11,20707 | 100,0 m (todos) |
| Por drone (pré-condicionado) | 49 | −11,20707 | 100,0 m (todos) |
| Referência (9) | – | −11,20707 | \(r=h\) = 100 m |
4.5 Restrições e condições de KKT
Com bateria limitada, o ótimo cumpre as condições de Karush-Kuhn-Tucker. Para o drone na fronteira \(\lVert q_i - b\rVert = R\),
e para o drone livre \(\nabla_{q_i}J = 0\). Quando a separação está ativa, aparecem também multiplicadores \(\mu_{ij}\ge0\) associados a \(\lVert q_i-q_j\rVert-d_{\min}\ge0\). A tabela de KKT da aba Posicionamento verifica essas condições para cada drone; como no método de Lagrange, o multiplicador \(\lambda_i\) mede quanto \(\log\det F\) aumentaria por metro adicional de alcance.
4.6 Ótimos locais: critério robusto e multistart
Como o problema não é convexo (seção 3.2), o gradiente sozinho pode parar num ótimo local, com os drones agrupados do lado da base. Há também o empate da seção 3.3: cruz e semicírculo dão a mesma \(F\), mas o semicírculo perde mais informação se a pessoa estiver alguns metros fora do lugar suposto. Por isso o app usa, por padrão, um critério robusto (projeto bayesiano), que maximiza a média de \(\log\det F\) sobre uma nuvem de posições plausíveis: o centro, com peso 1/3, e 8 pontos num anel de raio \(\rho\), dividindo os 2/3 restantes:
O empate desaparece e o arranjo simétrico passa a ser o melhor. Quando o gradiente converge, o app roda ainda um multistart: 16 otimizações a partir de arranjos iniciais diferentes (12 rotações da formação ideal e 4 aleatórios). Se alguma achar um valor melhor, os drones voam até essa solução, cada um para a posição mais próxima, e o gradiente refina o resultado.
5 Estimação pelo método de Gauss-Newton
5.1 Princípio do método
Na missão a posição \(p\) é desconhecida e é estimada por máxima verossimilhança, o que, com ruído gaussiano, equivale a minimizar a soma dos quadrados dos resíduos \(S(p)=\sum_j (y_j-\mu_j(p))^2\). O método de Fisher scoring troca a matriz de Hesse pela informação de Fisher:
Com ruído gaussiano isso é exatamente o método de Gauss-Newton, de segunda ordem aproximada: usa só as primeiras derivadas do modelo, mas aproveita a curvatura. O passo é reduzido à metade até que \(S\) diminua.
5.2 Ponto inicial por busca em grade
A verossimilhança não é convexa: com drones alinhados ela forma um anel ou uma meia-lua. Por isso o app faz primeiro uma busca em grade de 60 × 60 pontos e só depois refina com Gauss-Newton. Sem ruído, o método recupera a posição exata, (600,000; 300,000). O painel Estimador da aba Missão compara, partindo do mesmo ponto, o número de iterações do Gauss-Newton e da descida pelo gradiente com Armijo.
5.3 Planejamento da rodada seguinte
A cada rodada o ciclo é medir, estimar, planejar e voar. O planejamento resolve o problema (4) na estimativa atual \(\hat p\), somando a informação já coletada, com o critério robusto (14) sobre os pontos-sigma da elipse de covariância (limitados a 250 m):
6 Solução pelo método de programação dinâmica
6.1 Princípio do método
Um único drone também pode buscar a pessoa ao longo do tempo. O mapa é dividido em células e o conjunto \(E\) guarda as células já vasculhadas; uma célula só é eliminada quando entra no raio de inspeção direta do drone (90 m), pois sinal fraco, sozinho, não conta como exploração. A probabilidade \(P(c)\) de cada célula vem da verossimilhança das medições, normalizada.
Pelo princípio de otimalidade de Bellman, escolhida a próxima posição \(a\), o restante da rota deve ser ótimo a partir do novo estado. Para posição \(x\), cobertura acumulada \(E\) e horizonte restante \(b\):
\(C(a)\) é o conjunto de células cobertas ao visitar \(a\), \(\beta = 0{,}015\) é um pequeno bônus por célula nova, \(\lambda = 0{,}012\) penaliza a distância voada e \(d_{\max}\) = 150 m é o deslocamento máximo por rodada.
6.2 Discretização
- Grade de 10 × 10 células de 100 m; \(E\) é guardado como máscara de bits de 100 posições.
- Ações \(A(x)\): centros de células alcançáveis em uma rodada (\(d \le 150\) m), isto é, as oito vizinhas.
- Horizonte de quatro rodadas. Só o primeiro movimento da rota ótima é executado; na rodada seguinte, com novas medições, o plano é refeito.
6.3 Memoization
Estados iguais \((x,E,b)\) aparecem por caminhos diferentes (visitar \(a\) e depois \(a'\), ou o contrário). Cada valor \(V\) calculado é guardado numa tabela e reaproveitado, evitando recalcular subproblemas. O painel de telemetria da missão mostra quantos estados foram armazenados. Além da cobertura direta, as medições feitas em posições diferentes acumulam direções distintas na matriz de Fisher e tornam a localização bidimensional observável.
7 Comparação dos resultados
As estratégias de voo são comparadas na aba Comparação por simulação de Monte Carlo: para cada estratégia são sorteadas várias missões com a pessoa em posições aleatórias, e registra-se o erro de localização mediano a cada rodada.
- Maximizar a informação de Fisher: gradiente projetado (seção 4) aplicado a (16), com estimação por Gauss-Newton (seção 5);
- Cobertura com memória: programação dinâmica (seção 6), com 1 drone;
- Voar direto até a estimativa e voo aleatório: estratégias de referência, sem otimização.
A segunda comparação varia a quantidade de drones. De (9), \(\det F^\star \propto N^2\), e o erro RMS cai com \(1/\sqrt N\): dobrar o número de drones reduz o erro em cerca de 30%, não pela metade.
8 Resultado
- Gradiente projetado (Armijo, passo por drone, cenário padrão): os drones ficam a \(r=h\) = 100 m da pessoa, com direções balanceadas, e \(\log\det F = -11{,}20707\), igual ao valor de referência (9) em todos os dígitos exibidos. O mesmo vale para N = 2 (−12,59282) e N = 6 (−10,39632). Erro RMS mínimo de 23,30 m.
- Gauss-Newton: recupera a posição exata sem ruído; com ruído, o erro real é comparado na missão com a elipse de Cramér-Rao.
- Programação dinâmica: planeja rotas que alcançam regiões prováveis ainda não exploradas, respeitando o deslocamento máximo e preservando a memória das células já cobertas.
Com bateria limitada ou separação ativa, o ótimo fica na fronteira e as condições de KKT (13) são verificadas na aba Posicionamento. Todas as verificações numéricas podem ser repetidas com npm test.
9 Comparativo entre os métodos
Os três métodos resolvem partes diferentes do mesmo problema de busca. O gradiente projetado é um método numérico de primeira ordem, usado no posicionamento; Gauss-Newton é um método de segunda ordem aproximada, usado na estimação; a programação dinâmica é uma busca organizada em etapas, baseada no princípio de Bellman, usada na cobertura. A Tabela 3 resume as diferenças.
| Critério | Gradiente projetado | Gauss-Newton | Programação dinâmica |
|---|---|---|---|
| Natureza | Numérico, de primeira ordem | Numérico, de segunda ordem aproximada | Busca organizada em etapas (Bellman) |
| Informação usada | Gradiente analítico (11) | Jacobiano do modelo; \(J^\top J\) no lugar da Hesse | Somente valores de \(P(c)\) e distâncias |
| Restrições | Projeção em \(\Omega\) a cada passo; KKT no ótimo | Corte na área de busca | Embutidas no conjunto de ações \(A(x)\) |
| Parâmetros a escolher | Ponto inicial, \(c_1\), limite de 30 m, escala do passo | Ponto inicial (busca em grade) | Grade, horizonte, \(\beta\), \(\lambda\) |
| Garantia de ótimo global | Não (problema não convexo); multistart | Não (verossimilhança não convexa); grade inicial | Sim, sobre a grade e o horizonte |
| Principal limitação | Ótimos locais e sensibilidade à escala | Depende de bom ponto inicial | Custo exponencial no horizonte (maldição da dimensionalidade) |
9.1 Exatidão e esforço computacional
O gradiente projetado atinge a solução de referência (9), mas o número de iterações depende da escala do passo: 147 com passo comum contra 49 com passo por drone (Tabela 2). Gauss-Newton, por aproveitar a curvatura, converge em poucas iterações perto do ótimo; a descida pelo gradiente, partindo do mesmo ponto, costuma precisar de mais. A programação dinâmica não itera: resolve a recursividade (17) uma vez por rodada, e a memoization limita o esforço aos estados distintos.
9.2 Aplicabilidade e limitações
O sinal real de celular sofre sombreamento por relevo e vegetação, multipercurso e variação de antena, e é bem mais ruidoso que o modelo (1).
A Fisher depende da posição verdadeira, que não é conhecida. O planejamento usa a estimativa atual e pode errar nas primeiras rodadas; o critério robusto (14) atenua esse problema.
Cramér-Rao é um limite assintótico. Com poucas medições, o erro real pode ser maior que a elipse indica, e o app mostra os dois para comparar.
O planejamento de Fisher é guloso (uma rodada à frente) e o gradiente projetado encontra ótimos locais. A cobertura usa horizonte curto: evita o custo exponencial de planejar a missão inteira, mas pode deixar de enxergar rotas melhores além de quatro rodadas.
9.3 Conclusão do comparativo
Para o posicionamento, que é contínuo, diferenciável e com poucas variáveis, o gradiente projetado é o mais adequado: chega à solução analítica, trata as restrições pela projeção e fornece, pelas condições de KKT, a interpretação dos multiplicadores. Para a estimação, Gauss-Newton aproveita a estrutura de mínimos quadrados e converge rapidamente a partir da busca em grade. Para a cobertura, em que a decisão é discreta e depende de todas as células já visitadas, a programação dinâmica é a escolha natural, pois garante o melhor plano sobre a grade sem exigir derivadas. Os métodos se complementam: a busca em grade e o multistart localizam a região do ótimo, e os métodos de gradiente refinam a solução.