roboforum.ru

[Виталий]

И что дальше? =)
При чем тут ошибка в измерениях?

Возможно, фильтр Калмана может помочь и в решении задачи в тех условиях, какие есть. Предположительно измерение расстояний до каждого из передатчиков происходит с НЕКОРЕЛИРОВАННОЙ ошибкой. У меня, пока, мозга не хватает, что-бы описать и решить такую систему.

Ну это я думаю просто проверить. =)

[=DeaD=]

И что дальше? =)
При чем тут ошибка в измерениях?

Это оба вопроса ко мне были?

Дальше - больше

Добавлено спустя 4 минуты 16 секунд:
Теперь собственно судьба аналитического решения IMHO зависит от достоверности следующего утверждения:

При наличии в любых координатах третьей окружности с начальным радиусом r3 (которая при t=0 максимум - касается каждой из наших окружностей), обязательно ли она при росте t в какой-то момент времени встретится с хотя-бы одной точкой пересечения первых двух окружностей).

Есть идеи? Я пока на этом остановился

Если утверждение верно и она встретится обязательно, тогда можно попробовать искать эту точку пересечения 3 окружностей делением пополам по t.

Добавлено спустя 17 минут 27 секунд:
Из первичных рассуждений и набросков утверждение верно, но строго доказывать реально лень

Вообще какая перспективность этого решения по мнению присутствующих тут математиков?

[Виталий]

Ага оба тебе.
Забыл про радиусы ты окружностей учесть, что они измеряются с ошибкой и эту ошибку итеративный алгоритм пытается убрать. А как ты собрался ее убирать я честно говоря пока что не понял...

[mandigit]

Вообще какая перспективность этого решения по мнению присутствующих тут математиков?

Пока смотрится слабовато.
Допустим, две окружности пересекаются.
Мы хотим из третьего центра окружности построить окружность такого радиуса, что он окажется на точке пересечения двух предыдущих окружностей - это возможно.

Собственно эти три окружности , если мы оперируем (подгоняя время) их радиусами вообще-то никогда не пересекутся в одной точке (если использовать целочисленную арифметику, такая ситуация - возможна).

[=DeaD=]

А что именно слабовато? Разве это не качественный метод, когда у нас есть непрерывная функция имеющая разные знаки на концах известного нам отрезка и нам нужно найти координаты точки в которой эта функция =0?

Особенно если производная этой функции ограничена (а пока не вижу почему ей не быть ограниченной).

В этом случае метод сходится всегда и задача решается поиском делением пополам.

Причем ввиду ограниченности производной сведя интервал к некоторому микроинтервалу мы можем гарантировать что на его середине искомая функция должна оказаться не более верхней границы производной умноженной на половину его интервала.

Добавлено спустя 1 минуту 36 секунд:
Так что при подходе "деление пополам" не вижу никаких проблем с целочисленной арифметикой...

А текущий алгоритм за сколько итераций решает задачу в среднем? А то у меня формулы получаются не самые тривиальные - может просто неэффективным быть по этому параметру алгоритм...

Добавлено спустя 16 минут 8 секунд:

PS: Пока непонятно - необходимо отнимать dB от B, иначе алгоритм расходится, требуется поиск проблемы

А вот если бы выкладки были полными, можно было бы покопаться, что не так...

[mandigit]

А что именно слабовато?

Наверное я недостаточно хорошо понял идею.
Для проверки работоспособности алгоритма я рисовал на бумаге в клеточку пример и решал по нему. Если решение оказывалось верным - можно дальше рассуждать, иначе - надо думать дальше.

PS: Пока непонятно - необходимо отнимать dB от B, иначе алгоритм расходится, требуется поиск проблемы

А вот если бы выкладки были полными, можно было бы покопаться, что не так...

Так это - полные выкладки!

[=DeaD=]

Так это - полные выкладки!

Не выписано решение линейного уравнения по приращениям. Вдруг там ошибка?

А что по итерациям - сейчас алгоритм их сколько делает? А то может смысла нет мой метод дальше копать, вдруг он тупо дольше будет...

Блин, дорвусь до домашнего своего компа со всеми средами разработки - надо будет область сходимости изучить будет...

[mandigit]

Так это - полные выкладки!

Не выписано решение линейного уравнения по приращениям. Вдруг там ошибка?

Решение СЛАУ это хорошо известная задача, выходящая за рамки алгоритма

А что по итерациям - сейчас алгоритм их сколько делает? А то может смысла нет мой метод дальше копать, вдруг он тупо дольше будет...

Я был удивлен мощностью итерационного алгоритма.
Первичное приближение происходит за 5-6 итераций, потом, поскольку положение не меняется так сильно, достаточно 1-2 итераций.

[=DeaD=]

Тогда смысла нет копать более сложный метод, у меня в 5-6 итерациях будет раз в 10 больше вычислений...

Вообще конечно ньютон быстро сходится, но одно напрягает - его сходимость не гарантируется никак в нашем случае поэтому нужно будет провести немного исследований практических по сходимости метода - запускать его при разных конфигурациях маяков и с тучей тестируемых положений робота.

Кстати, расположение маяков в вершинах тупоугольного треугольника тестировалось? Или только остроугольные?

[boez]

Пусть r1, r2, r3 - расстояния до маяков, реальные.

Известные величины: r1', r2', r3' - расстояния с неким смещением, одинаковым.

расстояния:
r1 = r1'+d
r2 = r2'+d
r3 = r3'+d

Координаты маяков: (x1,y1),(x2,y2),(x3,y3)

Искомые величины: x,y,d - координаты и приведенное к расстоянию смещение во времени.

Уравнения окружностей (расстояния до маяков):

r1^2 = (x1-x)^2 + (y1-y)^2 (1)
r2^2 = (x2-x)^2 + (y2-y)^2 (2)
r3^2 = (x3-x)^2 + (y3-y)^2 (3)

Вычтем из первого уравнения второге и третье

(r1'-r2')(r1'+r2'+2*d) = (x1-x2)(x1+x2-2*x) + (y1-y2)(y1+y2-2*y) (4)
(r1'-r3')(r1'+r3'+2*d) = (x1-x3)(x1+x3-2*x) + (y1-y3)(y1+y3-2*y) (5)

А это уже линейная по x, y и d система. Объявив d известным, решаем ее и находим линейные же выражения x=x(d), y=y(d). Подставляем например в (1), получаем квадратное уравнение с одним неизвестным d (ну лень мне щас выписывать многоэтажные формулы - но вполне достаточно что я знаю как их выписать).

Квадратное уравнение имеет 2 корня. То есть, кроме реального решения, есть еще какое-то второе, тоже удовлетворяющее системе. Не исключено, что там получатся отрицательные расстояния - тогда его можно смело отбросить. А может и реальное будет второе - ведь наша точка искомая - это точка пересечения двух половинок (одиночных ветвей) двух разных гипербол. Они могут в 1 точке пересечься, а могут и в 2...

Если честно - сначала пытался просто d исключить (оно же вроде как определено с точностью до произвольной постоянной???) - система сразу запутывается. А так выходит наглядно.

Проверяйте решение, мог ведь и напутать

[mandigit]

Проверяйте решение, мог ведь и напутать

Нельзя-же такое под вечер писать

На первый взгляд - интересное решение. Если дозавершить описание алгоритма и проверить на нескольких примерах - можно брать в копилку алгоритмов.
Остается так-же неясным, каково будет поведение алгоритма с учетом ошибки измерения.

[=DeaD=]

Попробуем дописать:

(r1'-r2')(r1'+r2'+2*d) = (x1-x2)(x1+x2-2*x) + (y1-y2)(y1+y2-2*y) (4)
(r1'-r3')(r1'+r3'+2*d) = (x1-x3)(x1+x3-2*x) + (y1-y3)(y1+y3-2*y) (5)

A1*x+B1*y=C1, где A1=2*(x1-x2), B1=2*(y1-y2), C1=(x1+x2)*(x1-x2)+(y1+y2)*(y1-y2)-(r1'-r2')*(r1'+r2'+2*d) = D1 + k1*d
A2*x+B2*y=C2, где A2=2*(x1-x3), B2=2*(y1-y3), C2=(x1+x3)*(x1-x3)+(y1+y3)*(y1-y3)-(r1'-r3')*(r1'+r3'+2*d) = D2 + k2*d

D=A1*B2-A2*B1=4*(x1-x2)*(y1-y3)-4*(x1-x3)*(y1-y2) - не ноль, т.к. маяки не на 1 прямой.

x=(C1*B2-C2*B1)/(A1*B2-A2*B1)
y=(A1*C2-A2*C1)/(A1*B2-A2*B1)

[Виталий]

Все бы хорошо, но во-первых d - не одинаковое, а во вторых - неизвестно.

[=DeaD=]

Все бы хорошо, но во-первых d - не одинаковое, а во вторых - неизвестно.

d - неодинаковое - это как? с точностью до накапливаемой за 1/10 сек погрешности d как раз одинаковое.

Добавлено спустя 4 минуты 8 секунд:
Дальше:

x=(C1*B2-C2*B1)/(A1*B2-A2*B1) = ((D1+k1*d)*B2-(D2+k2*d)*B1)/(A1*B2-A2*B1) = P1+m1*d
y=(A1*C2-A2*C1)/(A1*B2-A2*B1) = (A1*(D2+k2*d)-A2*(D1+k1*d))/(A1*B2-A2*B1) = P2+m2*d

Получается что точка пересечения вообще параметризованная прямая?

Добавлено спустя 6 минут 44 секунды:
Ну и наконец:

(r1'+d)^2 = (x1-x)^2 + (y1-y)^2 = (x1-P1-m1*d)^2 + (y1-P2-m2*d)^2

d^2 + 2*r1'*d + r1'^2 = m1^2*d^2 - 2*(x1-P1)*m1*d + (x1-P1)^2 + m2^2*d^2 - 2*(y1-P2)*m2*d + (y1-P2)^2

(1 - m1^2 - m2^2)*d^2 + (2*r1'+2*(x1-P1)*m1+2*(y1-P2)*m2)*d + (r1'^2 - (x1-P1)^2 - (y1-P2)^2) = 0

a = 1 - m1^2 - m2^2
b = 2*r1'+2*(x1-P1)*m1+2*(y1-P2)*m2
c = r1'^2 - (x1-P1)^2 - (y1-P2)^2

корни d1,d2 = (-b +/- sqrt(b^2-4*a*c))/(2*a)

Добавлено спустя 14 секунд:
Кого не сломает проверить?

[Duhas]

ломает!

а чем нить типа маткада посчитать?!