roboforum.ru

Технический форум по робототехнике.

LPS (Локальная Система Позиционирования)

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

Re: LPS (Локальная Система Позиционирования)

Сообщение Виталий » 20 янв 2009, 21:26

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


Ну это я думаю просто проверить. =)
Все новости о моих проектах http://savethebest.ru
Аватара пользователя
Виталий
 
Сообщения: 2114
Зарегистрирован: 08 окт 2004, 16:43
Откуда: St. Petersburg
Skype: quark-bot
ФИО: Клебан Виталий

Re: LPS (Локальная Система Позиционирования)

Сообщение =DeaD= » 20 янв 2009, 21:50

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

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

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

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

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

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

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

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

Вообще какая перспективность этого решения по мнению присутствующих тут математиков? :)
Проект [[Open Robotics]] - Универсальные модули для построения роботов
Аватара пользователя
=DeaD=
 
Сообщения: 24218
Зарегистрирован: 06 окт 2004, 18:01
Откуда: Ебург
прог. языки: C++ / PHP / 1C
ФИО: Антон Ботов

Re: LPS (Локальная Система Позиционирования)

Сообщение Виталий » 20 янв 2009, 21:53

Ага оба тебе.
Забыл про радиусы ты окружностей учесть, что они измеряются с ошибкой и эту ошибку итеративный алгоритм пытается убрать. А как ты собрался ее убирать я честно говоря пока что не понял...
Все новости о моих проектах http://savethebest.ru
Аватара пользователя
Виталий
 
Сообщения: 2114
Зарегистрирован: 08 окт 2004, 16:43
Откуда: St. Petersburg
Skype: quark-bot
ФИО: Клебан Виталий

Re: LPS (Локальная Система Позиционирования)

Сообщение mandigit » 20 янв 2009, 22:12

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


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

Собственно эти три окружности , если мы оперируем (подгоняя время) их радиусами вообще-то никогда не пересекутся в одной точке (если использовать целочисленную арифметику, такая ситуация - возможна).
Аватара пользователя
mandigit
 
Сообщения: 583
Зарегистрирован: 28 ноя 2005, 12:05
Откуда: Москва

Re: LPS (Локальная Система Позиционирования)

Сообщение =DeaD= » 20 янв 2009, 22:47

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

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

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

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

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

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

Добавлено спустя 16 минут 8 секунд:
mandigit in http://imobot.ru/my_projects/lps/lps_pos_alg.pdf писал(а):PS: Пока непонятно - необходимо отнимать dB от B, иначе алгоритм расходится, требуется поиск проблемы

А вот если бы выкладки были полными, можно было бы покопаться, что не так... :oops:
Проект [[Open Robotics]] - Универсальные модули для построения роботов
Аватара пользователя
=DeaD=
 
Сообщения: 24218
Зарегистрирован: 06 окт 2004, 18:01
Откуда: Ебург
прог. языки: C++ / PHP / 1C
ФИО: Антон Ботов

Re: LPS (Локальная Система Позиционирования)

Сообщение mandigit » 20 янв 2009, 23:04

=DeaD= писал(а):А что именно слабовато?

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

=DeaD= писал(а):
mandigit in http://imobot.ru/my_projects/lps/lps_pos_alg.pdf писал(а):PS: Пока непонятно - необходимо отнимать dB от B, иначе алгоритм расходится, требуется поиск проблемы

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

Так это - полные выкладки!
Аватара пользователя
mandigit
 
Сообщения: 583
Зарегистрирован: 28 ноя 2005, 12:05
Откуда: Москва

Re: LPS (Локальная Система Позиционирования)

Сообщение =DeaD= » 20 янв 2009, 23:21

mandigit писал(а):Так это - полные выкладки!

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

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

Блин, дорвусь до домашнего своего компа со всеми средами разработки - надо будет область сходимости изучить будет...
Проект [[Open Robotics]] - Универсальные модули для построения роботов
Аватара пользователя
=DeaD=
 
Сообщения: 24218
Зарегистрирован: 06 окт 2004, 18:01
Откуда: Ебург
прог. языки: C++ / PHP / 1C
ФИО: Антон Ботов

Re: LPS (Локальная Система Позиционирования)

Сообщение mandigit » 20 янв 2009, 23:34

=DeaD= писал(а):
mandigit писал(а):Так это - полные выкладки!

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

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

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

Я был удивлен мощностью итерационного алгоритма.
Первичное приближение происходит за 5-6 итераций, потом, поскольку положение не меняется так сильно, достаточно 1-2 итераций.
Аватара пользователя
mandigit
 
Сообщения: 583
Зарегистрирован: 28 ноя 2005, 12:05
Откуда: Москва

Re: LPS (Локальная Система Позиционирования)

Сообщение =DeaD= » 20 янв 2009, 23:44

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

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

Кстати, расположение маяков в вершинах тупоугольного треугольника тестировалось? Или только остроугольные?
Проект [[Open Robotics]] - Универсальные модули для построения роботов
Аватара пользователя
=DeaD=
 
Сообщения: 24218
Зарегистрирован: 06 окт 2004, 18:01
Откуда: Ебург
прог. языки: C++ / PHP / 1C
ФИО: Антон Ботов

Re: LPS (Локальная Система Позиционирования)

Сообщение boez » 21 янв 2009, 00:04

Пусть 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 исключить (оно же вроде как определено с точностью до произвольной постоянной???) - система сразу запутывается. А так выходит наглядно.

Проверяйте решение, мог ведь и напутать :)
boez
 
Сообщения: 1981
Зарегистрирован: 27 авг 2008, 10:45
Откуда: Харьков
прог. языки: С/С++

Re: LPS (Локальная Система Позиционирования)

Сообщение mandigit » 21 янв 2009, 11:03

boez писал(а):Проверяйте решение, мог ведь и напутать :)


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

На первый взгляд - интересное решение. Если дозавершить описание алгоритма и проверить на нескольких примерах - можно брать в копилку алгоритмов.
Остается так-же неясным, каково будет поведение алгоритма с учетом ошибки измерения.
Аватара пользователя
mandigit
 
Сообщения: 583
Зарегистрирован: 28 ноя 2005, 12:05
Откуда: Москва

Re: LPS (Локальная Система Позиционирования)

Сообщение =DeaD= » 21 янв 2009, 11:13

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

boez писал(а):(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)
Проект [[Open Robotics]] - Универсальные модули для построения роботов
Аватара пользователя
=DeaD=
 
Сообщения: 24218
Зарегистрирован: 06 окт 2004, 18:01
Откуда: Ебург
прог. языки: C++ / PHP / 1C
ФИО: Антон Ботов

Re: LPS (Локальная Система Позиционирования)

Сообщение Виталий » 21 янв 2009, 11:26

Все бы хорошо, но во-первых d - не одинаковое, а во вторых - неизвестно.
Все новости о моих проектах http://savethebest.ru
Аватара пользователя
Виталий
 
Сообщения: 2114
Зарегистрирован: 08 окт 2004, 16:43
Откуда: St. Petersburg
Skype: quark-bot
ФИО: Клебан Виталий

Re: LPS (Локальная Система Позиционирования)

Сообщение =DeaD= » 21 янв 2009, 12:17

Виталий писал(а):Все бы хорошо, но во-первых 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 секунд:
Кого не сломает проверить? :)
Проект [[Open Robotics]] - Универсальные модули для построения роботов
Аватара пользователя
=DeaD=
 
Сообщения: 24218
Зарегистрирован: 06 окт 2004, 18:01
Откуда: Ебург
прог. языки: C++ / PHP / 1C
ФИО: Антон Ботов

Re: LPS (Локальная Система Позиционирования)

Сообщение Duhas » 21 янв 2009, 12:20

ломает! :crazy:

а чем нить типа маткада посчитать?!
«Как сердцу выразить себя? … Мысль изреченная есть ложь!»
В этом мире меня подводит доброта и порядочность...
"двое смотрят в лужу, один видит лужу, другой отраженные в ней звезды"
Аватара пользователя
Duhas
 
Сообщения: 6338
Зарегистрирован: 15 сен 2007, 13:03
Откуда: Красноярск
прог. языки: ASM(МК), C(PC)
ФИО: Гагарский Андрей Александрович

Пред.След.

Вернуться в Золотой фонд

Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 2