Я написал скрипт Python (исключен, чтобы не загромождать этот пост), который вычисляет время, необходимое лучу света для распространения между две точки в некоторой сложной среде. Теперь я хочу использовать этот сценарий для решения проблемы Разницы во времени прибытия (TDoA) в этой среде. Постановка задачи следующая:
При известном местоположении некоторых N приемников (камер, датчиков, антенн и т.д.) и времени прибытия некоторых световой сигнал на каждом из этих приемников, я хочу определить координаты излучения сигнала. Поскольку время передачи сигнала неизвестно, все, что я действительно знаю, это попарные различия во времени прибытия (например, разница во времени прибытия сигнала между приемником A и приемником B).< /em>
Что я уже сделал
Я написал следующий скрипт в попытке чтобы решить эту проблему:
Код: Выделить всё
from dataclasses import dataclass
import numpy as np
from scipy.optimize import differential_evolution
from ray_tracer import RayTracer
from random import randrange
@dataclass
class Optimizer:
ice_model: np.ndarray # Parameters used by my RayTracer class to model complex medium
antenna_coordinates: np.ndarray
def __post_init__(self):
self.ray_tracer = RayTracer(self.ice_model)
def _objective(self, coords: np.ndarray, measured_times: np.ndarray) -> float:
"""Objective function to minimize the error between measured and predicted transit times."""
x, y, z = coords
predicted_times = np.array([
self.ray_tracer.transit_time([x, y, z], [nx, ny, nz])
for nx, ny, nz in self.antenna_coordinates
])
# Compute time difference matrices
measured_time_diff = np.abs(measured_times[:, None] - measured_times)
predicted_time_diff = np.abs(predicted_times[:, None] - predicted_times)
# Calculate error matrix and fill the diagonal with zeros
error_matrix = np.abs(measured_time_diff - predicted_time_diff)
np.fill_diagonal(error_matrix, 0)
# Return the maximum error
return np.nanmax(error_matrix)
def solve(self, measured_times: np.ndarray) -> np.ndarray:
"""Solve the optimization problem to find coordinates minimizing the objective function."""
bounds = [(-1000, 1000), (-1000, 1000), (-1000, 0)]
# Use differential evolution to minimize the objective function
result = differential_evolution(
self._objective,
bounds=bounds,
args=(measured_times,),
strategy='best1bin', # Strategy for optimization
maxiter=5000, # Maximum number of iterations
tol=1e-7, # Tolerance for convergence
popsize=30, # Population size
mutation=(0.5, 1), # Mutation factor
recombination=0.7, # Recombination constant
disp=True # Display convergence messages
)
if result.success:
return result.x # Return the optimized coordinates
else:
raise ValueError("Optimization failed: " + result.message)
# Example usage
if __name__ == "__main__":
# Define the ice model
ice_model = np.array([1.78, 0.454, 0.0132])
# Initialize RayTracer with the ice model
ray_tracer = RayTracer(ice_model)
# Generate random antenna coordinates
antenna_coordinates = np.array([[randrange(-100, 0) for _ in range(3)] for _ in range(10)])
# Generate random true coordinates and measured transit times
x, y, z = [randrange(-1000, 0) for _ in range(3)]
measured_times = np.array([
np.random.normal(ray_tracer.transit_time([x, y, z], [nx, ny, nz]) + 10, 1e-12)
for nx, ny, nz in antenna_coordinates
])
# Initialize the optimizer
optimizer = Optimizer(ice_model, antenna_coordinates)
# Attempt to find optimal coordinates
try:
optimal_coordinates = optimizer.solve(measured_times)
print("Optimal Coordinates (x, y, z):", optimal_coordinates)
print("True Coordinates (x, y, z):", x, y, z)
except ValueError as e:
print(e)
Код: Выделить всё
Optimal Coordinates (x, y, z): [-384.46240934 730.54140202 -612.43716286]
True Coordinates (x, y, z): -704 -408 -611
- Функция _objective вычисляет время прибытия сигнала в каждое из известных местоположений приемника для заданного предположения о координатах излучения сигнала. Класс RayTracer (вышеупомянутый скрипт Python) используется для вычисления времени прохождения. Затем я строю матрицы, содержащие попарные разницы во времени прибытия, вычитаю их друг из друга и возвращаю наибольшую абсолютную ошибку.
- Функцияsolve< /code> использует минимизатор дифференциальной эволюции SciPy (выбран просто потому, что это единственный минимизатор, который приблизился к решению этой проблемы) для определения неизвестных координат x,y,z.
- Основная «функция» генерирует некоторые примеры данных, выбирая случайные координаты приемника и источника, используя RayTracer для вычисления времени прибытия и передачи этих значений времени (вместе с некоторым гауссовским шумом и смещением 10, чтобы показать, что время прибытия не важно для этого алгоритма) решателю.
Мне нужно решение, которое эффективен с точки зрения времени выполнения, поскольку (в идеале) в конечном итоге найдет применение практически в реальном времени. К сожалению, хотя я попробовал применить почти все оптимизаторы SciPy (тщательно учитывая каждую из их сильных и слабых сторон и параметров), а также некоторые свои собственные конструкции, мне не удалось точно восстановить расположение источника. Это не улучшается ни при использовании дополнительных приемников, ни при уменьшении гауссовского шума.
Целевая функция сильно нелинейна, и я пробовал применять различные методы сглаживания (сглаживание по Гауссу, потери Хубера, фильтры Савицкого-Голея) безрезультатно. Никакая другая разумная целевая функция не страдает от этой проблемы. Рассмотрим следующий график цели в z, созданный с использованием данных примера (и с фиксированными истинными значениями x и y):
< img alt="введите описание изображения здесь" src="https://i.sstatic.net/lQw8XyD9.png" />
Код, опубликованный выше, использует дифференциальную эволюцию решатель довольно надежно восстанавливает координату z (попадая в пределах единицы или около того примерно в 2/3 случаев и в противном случае не приближаясь к результату), но надежно не может точно восстановить координату x< Координаты /code> и y. Мне приходит в голову, что, возможно, было бы полезно написать какой-нибудь алгоритм, который сначала решает координату z (впоследствии сводя задачу к одному в двух измерениях), однако мне не удалось его написать (я пробовал например, выборка нескольких точек из набора срезов z и выбор среза с наименьшей ошибкой по различным показателям, однако это было медленно и ненадежно).
Какие альтернативные алгоритмы я мог бы использовать, которые были бы быстрее, точнее и надежнее?
Я бы предпочел алгоритм с минимальным настраиваемых параметров, так как мне бы хотелось, чтобы этот алгоритм можно было легко применить к различным значениям Ice_model, границ и т. д.
Подробнее здесь: https://stackoverflow.com/questions/790 ... -many-loca
