Войти
ФлеймФорумПрограммирование

Russian AI Cup 2018: CodeBall 3D (4 стр)

Advanced: Тема повышенной сложности или важная.

Страницы: 13 4 5 68 Следующая »
#45
23:15, 31 дек. 2018

}:+()___ [Smile]
> На мой взгляд, надо наоборот: стараться держать скорость как можно меньше.
Из теории оптимального управления, правда для линейного и непрерывного по времени случая, наименьшее время пути тогда, когда идет разгон с максимальным ускорением, движение с постоянной скоростью и торможение с максимальным ускорением
правда, для дискретного случая надо округлять до целых время движения, не так быстро выходит

я всё же считаю, что лучше всего приезжать за минимальное время, в худшем случае - можно немного подождать, и начать двигаться со следующего тика

а так да, у меня пока что кривовато сделано.


#46
3:31, 1 янв. 2019

cArmius
> движение с постоянной скоростью
Такое возможно только если скорость ограничена, иначе невыгодно.
Но про минимальную скорость я написал именно для случая, когда время с запасом.
Если тратить это время на болтанку поперек траектории, то можно зацепить края.
Поэтому лучше просто ехать медленнее основную часть времени.

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

#47
(Правка: 4:57) 4:53, 1 янв. 2019

Походу реально можно ПВО сделать:
1) ставим два робота почти рядом
2) один робот чуть подпрыгивает, а второй отправляет его в дальний полёт сбивать мяч/противника.


ud1
> А закругления вы учитываете?
да

#48
18:55, 1 янв. 2019

Сколько тиков вам удается просимулировать за 20мс? Получается что не на с++ не уместить хороший перебор?

#49
12:03, 2 янв. 2019

s-a--m
С учётом простой симуляции поля - чисто симуляция уходит примерно на 600 тиков вперед
Если подключать дополнительные алгоритмы, то уже конечно меньше

#50
13:10, 2 янв. 2019

У меня на jvm за 20мс получается максимум 4 тика вперёд, при этом стимулируется 6 направлений для каждого тиммейта и выбирается лучшее по алгоритму а*. И ещё их система выключает мою стратегию после ~600 тиков. Вот и думаю, как-то слишком тесно по времени для других языков...

#51
14:14, 2 янв. 2019

s-a--m
Со всеми алгоритмами за 20 мс я ухожу вперед на 60 тиков

А вот симуляция разных направлений наверное и правда затратно по времени. Я думаю, потенциальные поля имеют больший потенциал

#52
17:28, 2 янв. 2019

}:+()___ [Smile]

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

Добрый день. А какая логика стоит за цепной линией в пространстве скоростей? Если стояние на месте - это движение с постоянной скоростью, дуга - это поворот с постоянной по модулю скоростью (видимо имеется в виду достигнутая максимальная). А вот с цепной линией не совсем ясно...

#53
20:00, 2 янв. 2019

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

#54
20:23, 2 янв. 2019

mortido
> А какая логика стоит за цепной линией в пространстве скоростей?
Я честно решал вариационную задачу (причем даже не для этого чемпионата, а раньше), но попробую на пальцах.

Механический эквивалент задачи:
Представим круг в пространстве скоростей (это наше ограничение скорости).
В этом круге есть две точки подвеса — начальная и конечная скорости.
И у нас есть нитка, длина которой — это бюджет изменения скорости.

Наибыстрейшая траектория имеет максимальную среднюю скорость по некоторому направлению.
Если мы подвесим нитку в поле тяготения, то ее форма будет минимизировать среднюю высоту.
Соответственно, в пространстве скоростей это будет средняя скорость по вертикали.
Ну и известный факт, что нитка висит по цепной линии.

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

#55
12:10, 3 янв. 2019

}:+()___ [Smile]
> И у нас есть нитка, длина которой — это бюджет изменения скорости.
А какой бюджет изменения скорости?

#56
14:10, 3 янв. 2019

PlayerDark

А какой бюджет изменения скорости?

Если я правильно понял, то это то насколько ты можешь изменить скорость за N тиков. В космонавтике еще есть понятие дельты V, только там больше на топливе завязанно.

}:+()___ [Smile]
Спасибо, потратил вечер пытаясь разобраться с ответом :) Интересное свойство линии цепи. Если я правильно понял, то направление тяготения для нее нужно брать противоположное направлению желаемого движения (чтобы максимизировать среднюю скорость, для случая когда мы не доходим до максимальной скорости и желаем добраться до нужной точки с нужной скоростью как можно быстрее)?

Теперь бы еще понять для дискретного случая. Похоже нужно еще несколько вечеров.

#57
15:04, 3 янв. 2019

mortido
> Если я правильно понял, то это то насколько ты можешь изменить скорость за N
> тиков.
N тиков это время для достижения нужной точки?

Кстати, мы же не можем в модели управлять скоростью, а только ускорением в нужную сторону.

#58
23:00, 3 янв. 2019

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

mortido
> направление тяготения для нее нужно брать противоположное направлению желаемого движения
К сожалению, нет. Надо перебрать все направления и выбрать наилучшее.
Собственно, поэтому задача нормально не решается даже для непрерывного случая.

#59
(Правка: 23:23) 23:07, 3 янв. 2019

}:+()___ [Smile]
А почему не применить твой подход из хоккея? Управление здесь вроде такое же?

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

Страницы: 13 4 5 68 Следующая »
ФлеймФорумПрограммирование