0: Так, через 5 минут будем начинать трансляцию финала конкурса роботы в городе.

1: Ждём чение всех участников.

2: Итак, всем здравствуйте. Я приветствую вас на финале конкурса роботы в городе. Меня зовут Разорвин Андрей Дмитриевич. Я являюсь руководителем конкурса роботы в городе. И сегодня мы посмотрим, как выступает студенчес.

3: И школьные команды. Так, давайте для начала я

4: Ещё раз расскажу правила, по которым мы будем оценивать участников нашего конкурса. Итак, задачей участников конкурса является выполнить проезд по всем целевым точкам по кратчайшему

5: Пути вот на рисунке представлена схема макета, сейчас участники будут выполнять движение по реальному макету.

6: Напомню, 1 этапом было движение робота в симуляции, а сейчас они тоже самое делают в реальном мире. Итак, у нас есть 15 точек и робот. Также есть дополнительные роботы, которые могут блокировать пути.

7: Это в студенческом треке, в школьном треке, у нас блокирующих

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

9: Вот робот стартует из случайного начального положения, определённого организаторами перед началом попытки.

10: Далее выполняется движение робота и подсчёт баллов. Подсчёт баллов происходит по следующей схеме. То есть мы находим процент от оптимального пути. Соответственно, если робот участник

11: По оптимальному пути он получает 100% за проезд, максимум можно получить 7 баллов за проезд и 3 балла за презентацию, соответственно, после проезда.

12: 1 участник от команды выступает с презентацией решения перед жюри, и, соответственно, жюри будут оценивать его. Также давайте я представлю жюри, которые будут

13: Сегодня.

14: Присутствовать на конкурсе.

15: Итак, жюри у нас сегодня Анучин Павел Юрьевич, генеральный директор компании сутура медтехнологии, занимается оными протезами Галуев Игорь Борисович сотрудник кафедры ртс.

16: Участник проекта пирс, а также Мартынов Антон ильич, руководитель проекта робо принт.

17: Так, давайте продолжим по регламенту.

18: Соответственно, самый максимальный балл, который может получить команда в ходе попытки, это 10, то есть 7 баллов за проезд по оптимальному пути и 3 балла за наивысшую оценку жюри за презентацию решения.

19: Также хочу показать, каким образом будет оцениваться заезд.

20: Там будет вводиться путь, по которому реально проехал робот участников, и вводиться входные данные перед началом я объявляю команду, которая сейчас должна подключаться. Они

21: С помощью нашего веб интерфейса подключаются к роботу и загружают свой код по готовности капитан команды говорит, что они готовы начать поездку.

22: Так, если вопросов нет у участников, мы можем приступать.

23: Итак, 1 команда от вузов короли задних парт сгту имени Гагарина.

24: Сейчас покажу вашу начальную позицию и робота робот номер 5. Можете подключаться к нему.

25: Дай секунду.

26: Заходить также, когда на тренировках было. Да, да, все правильно.

27: Как будете готовы, скажите, я вам продиктую стартовую точку стартовый угол.

28: Флаги и блоки.

29: Флаги это точки, по которым нужно проехать блоки это участки дороги, по которым проехать нельзя.

30: Давайте я.

31: Герой в чат.

32: Неудобно будет, лучше продиктую.

33: Также напоминаю участникам, что на трансляции

34: Выводиться трансляция с камер и т. Выступления будет

35: Оказывается, выступающие участникам.

36: Так, да, код загрузили. Какие старт? Так, стартовая точка. 1. Стартовый угол 0.

37: Флаги, по которым нужно проехать, это точка 2, 15 и 9.

38: 2:15 9 и заблокирована дорога 10 9. То есть из 10 в девят.

39: Так, робот установлен на стартовую позицию. Как будете готовы, можете

40: Все готово. Запускаем. Угу.

41: Робот начал движение на камерах можно.

42: Вернул в сторону 2 точки.

43: Доехал до 13 точки.

44: Повернул в сторону 15.

45: Доехал до

46: Едет в сторону 8.

47: Повернул в сторону 7.

48: Повернул в сторону 14.

49: Так, повернул в сторону 15.

50: Так и остановился. Ну, заканчиваем попытку. Капитан команды может включить презентацию и объяснить ваше решение, а также отключайтесь от робот.

51: Капитана команды в данный момент нет, у него военная кафедра не смог присутствовать в данный момент, поэтому мы составом Егор Серенко и Владимиров Александр, будем презентовать. Ага.

52: Приглашаю, тогда включайте демонстрацию и

53: Роботы в городе навигация. Безопасность. Мы получается, сразу по презентации идти или сразу приступаем?

54: Коду. Ну, в целом у вас есть 5 минут. Можете оказывать, как вы планировали.

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

56: Динамичном окружении. Инициализация графа и начальные параметры. Структура данных графа граф состоит из узлов рёбер, весов и угла поворота. Данные импортируются из модуля басик, контрол, модуль

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

58: Если что, мы не видим, как у вас слайды меняют. У вас пауэрпоинт.

59: Сейчас.

60: А почему? Сейчас? Секунду тогда.

61: Можете пауерпоинт показывать вообще. Да? Сейчас, секунду, я остановлюсь, ещё раз перезапущу.

62: Есть, да.

63: Сейчас есть.

64: Да, сейчас есть. Угу. Вот сейчас тоже есть, да.

65: Можем продолжать. Да, да, конечно.

66: Ага, тогда ещё раз. Инициализация графика и начальные параметры. Структура данных, а состоит из узлов рёбер, весов и Углов поворота. Данные импортируются из модуля b. Контрол, модуль, начальные параметры указываются стартовая точ.

67: Угол поворота, целевые флажки и позиции других машин, алгоритмы поиска оптимального пути. Мы использовали флоут. Вошёл расчет кратчайшего расстояния между всеми узлами графа жадный алгоритм, построение приближённого маршрута через заданные

68: И восстановление пути определён определение точной последовательности переходов, проверка безопасности маршрута, обнаружение угроз, сравнение маршрута с позициями других машин, корректировка графа, удалённое описание.

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

70: Поворота. Основной цикл выполнения проверка данных убедиться в существовании стартовой точки флажков. Построение маршрута, генерация пути с помощью алгоритма. Граф ауж. Запуск движения после

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

72: Изация маршрута с помощью бисиэм трау Резо, остановка двигателей и сохранение данных.

73: Ключевые особенности системы адаптивность, динамический пересчёт маршрута при появлении препятствий, точность учёта Углов поворота и длины рёбер для точного перемещения, надёжность, проверка связанности графа после изменений.

74: Все.

75: Ага, спасибо. Так, приглашаю жюри задать вопросы команде.

76: Так, ну давайте я задам вопрос. Угу. Так, у вас робот, мы сейчас после презентации, я забыл посчитать баллы. В общем, у вас робот не поехал в целевую точку номер 9, да? А, повернул.

77: Другую сторону. Как думаете, почему произойти?

78: Мы думаем, что по идее все должно было пойти как надо. Мы вот проверяли, все работало, и вот данный маршрут мы не

79: Проверяли. И вот в связи с чем возникла такая проблема, мы думаю, может быть это ошибка в жадном пути, либо в жадном алгоритме, то он посчитал её не как самую корот.

80: Неоптимальную, не знаю, в чем беда. Ну то есть пути, по которым вы не тренировались, он у вас корректно проехать не может. Нет, он проезжал все. То есть мы, ну, мы проверяли разные пути и

81: Все проезжало хорошо. Вот.

82: Так, ну хорошо, ещё вопросы?

83: Так, если нет вопросов, давайте, коллеги, есть вопрос, есть, что бы вы улучшили, да, что бы вы улучшили в своём алгоритме, помимо того, что было сказано только, что улучшили?

84: В нашем алгоритме была улучшена точность движения по кольцу, потому что у нас, ну, была такая проблема.

85: Ну, у нас была улучшена точность, что мы хотим, а что мы хотим улучшить?

86: Это что, мы улучшили? Зачем нам?

87: Мы же что мы улучшили, да? Какой? Давай ещё раз, можно вопрос?

88: Чтобы вы улучшили, ну, в плане не то, что вы уже сделали, а то, что вы могли бы сделать, чтобы это работало ещё лучше.

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

90: Хорошо, принято. Андрей, попрошу озвучить результаты заезда. Да, давайте, давайте.

91: Калькулятор, соответственно, маршрут, который проехал участники, это 1, 2, 12, 13, 15.

92: 8, 7, 14, 15.

93: Стартовая позиция 1 у поворота блокировки.

94: 10 9 флаги.

95: 2.

96: 9 проверяем выполнение. Оценка 34 и 535/1000 процента. Оптимальный путь у нас 1, 2, 12, 13:15.

97: А это путь, который из оптимального проехали участники. Оптимальный путь вот указан. То есть нужно было повернуть перекрёстке в сторону 8, ой, в сторону 9. Все на этом команда.

98: И партий завершает попытку и приглашается команда спецназ.

99: Хорошо, спасибо.

100: Здравствуйте. Так, команда спецназ. Можете подключаться к 5 роботу. Как будете готовы, я вам продиктую стартовую позицию.

101: Ориентацию.

102: Готовы? Так, у вас стартовая точка 6, стартовый угол 180.

103: А флаги там, блоки, флаги 2, 15, 10.

104: Угу. И блоки 12 2 из 12 во 2.

105: Так, 6, 182, 15, 10, 12 2. Да, все правильно.

106: Как будете готовы, можете запускать.

107: Ну, вроде запущен.

108: Да, робот начал.

109: Так, робот проехал у нас из 6 в 7, из 7 8.

110: Далее робот повернул в сторону 15.

111: Далее повернул в сторону 10.

112: Далее повернул в сторону 1.

113: Повернул в сторону 2.

114: Так, и все это окончание. Все, спасибо далее сейчас я сразу давайте покажу, проверю выполнение. У нас путь получился.

115: 6 7 8.

116: 15, 10, 1, 2.

117: Так, запускай проверку выполнения. Оценка 100%. Вы проехали по оптимальной и приглашаю капитана команды выступить с решением.

118: Ну, сейчас запущу демонстрацию.

119: Оценка 100%. Правильно? Да, правильно.

120: Видно? Да, да, все видно.

121: Ну, соответственно, мы с прошлой программы изменили не так уж и много. Вот мы использовали алгоритм дестра, как и в прошлый раз. Конкретно код этого алгоритма мы меняли. Он также читает стартовую позицию, конечную позицию, и он учитывает предыдущую точку. И вот

122: Строит кратчайший маршрут между 2 точками. Дальше мы использовали функцию ру, ну она работает, что в неё подаётся массив флагов и она, соответственно, строит наикратчайший маршрут по флагам. То есть если там были флаги 3, 4, 5, то там точно строится маршрут.

123: Там из тройки в четвёрку, из четвёрки в пятёрку. Вот так вот. Соответственно, дальше у нас есть

124: Функции. Ну вот единственное, что поменялось, там же изменилась библиотека, там не вот это все рсг рсд, а бсм. И ещё раньше, когда инициализировалась игра, ну, инициализировалось поле, там учитывались и блоки, и флаги в этот раз.

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

126: По большей части это все, что мы измени, могу показать.

127: А если нужно, конечно.

128: Видно. Так, сейчас видно только пока экран телемостом. Угу. Сейчас.

129: Вот, вот так видно. Да, да, видно.

130: Ну, в общем, здесь мы импортируем вот модуль бсм, вот эта наша функция, блоки, которую мы написали, она просто удаляет путь. Вот тут подаётся список из 2 элементов, и она удаляет путь между этими 2 элементами. Тут все тоже самое. Вот эта функция декстра.

131: Root вот best ruth я не рассказал она получает массив флагов и она различные перестановки берет, чтобы найти наиболее оптимальный путь потому что, как я и говорил, функция root она использует вот именно чётко по флагам находится. То есть если 3 4 5, то она построит чёт.

132: 3, 4, 4, 5. Ну, здесь блоки, точнее, флаги переставляются и находятся оптимальные. Ну вот эта функция нужна для особых точек, в которых угол сопоставляется. Ну и, соответственно, функция для управления. Мы написали перемещение между 2 точкам.

133: Перемещение по массиву точек.

134: И вот оставшаяся программа, блоки передаются. И вот здесь мы проходимся по блокам и выставляем их по факту. Это все. Угу. Спасибо. Команда спецназ, живи.

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

136: Он не мог двигать робота в неправильном направлении, грубо говоря. А в реальном мире у нас роботы могут ехать не в том направлении, вот как вы это решили. То есть вы как бы продублировали функционал

137: Был в симуляторе, то есть для проверки или как-то по другому сделать. Ну вообще мы все наши тесты проводили только на вот реальной машинке мы не использовали симулятор. Просто в 1 этапе мы написали программу, и она вроде как не ошибалась, то есть там

138: Не было такого, что она могла в принципе куда-то неправильно поехать, поэтому мы просто перенесли этот функционал полностью на машинку и там сразу все нормально работало.

139: Угу. Ну, в целом, да, алгоритм декстра здесь, наверное, наиболее эффективен.

140: Так, ещё вопросы?

141: Так, если вопросов больше нет, спасибо команде спецназ из неми и далее приглашается команда сон в механическом городе из кубанского государственного университета.

142: Да, мы тут, нас слышно. Ага. Да, подключайтесь к 5 роботу. Сейчас заходим на

143: Так, ошибка ввода данных так же.

144: Мы пытаемся на рабовик войти, и у нас тут ошибка ввода данных при логинизации. Да, попробуйте вот по тому паролю, который я вам скидывал.

145: Да, да, да, я его скопировал прям с телеги. Возможно пробелы какие-то.

146: Не, не так. Сейчас кое-что попробую к другому интернету переподключиться. Если не оно, значит.

147: Не, у нас проблема сейчас. Так, ну, участники сейчас подключались, поэтому интерфейс работает. Сервер рабо. Сейчас, секундочку.

148: Так, алло.

149: Да, нас слышно. Да, да. Дело было в интернете. К другой сети подключились, все заработало. Так подключайтесь к 5 роботу, и я сейчас продиктую стартовую точку.

150: Сегодняшний.

151: Когда мы готовы. Так, стартовая точка 3, стартовый угол 270, флаги 8, 10, 14.

152: Блоки, блоки 15 10 из 15.

153: Как будете готовы, можете запускать.

154: Так, сейчас, сейчас вставляем код. Да, да, да.

155: Все. Угу. Так, проверь.

156: Дубляция. Главное, что да, дубляция. Вот это что за здесь перед строчкой? Нормально, нормально. Да ладно.

157: Так, камеру мы не должны видеть, правильно?

158: Вы не видите трансляцию? У нас в самом веб интерфейсе нету камеры, мы не видим камеру.

159: Так попробуйте запустить, если он поедет.

160: Значит, запускаем. Угу.

161: Сейчас, секундочку.

162: Что происходит? Нет. Так, сейчас тогда попрошу отключиться от робота сейчас.

163: Перезапустим. Угу. Подключаемся. Можем вам код скинуть. Да. Может, мы вам его скинем? Да нет, в принципе, можете его сейчас запустить. Просто у вас, возможно, выбралось неправильно.

164: Бывает такое сейчас быстро. Угу. А можно пока такая небольшая заминка, послушать решение?

165: Команда и после решения будем. Давай, если готовы, можете включить презентацию.

166: Демонстрация окна, окно его. Угу. Так, ну, наше решение остаётся прежним. Мы все также используем муравьиный алгоритм поиска пути, суть которого представлена на 1 слайде.

167: То есть этот это эвристический алгоритм, который ищет путь по вероятностным переходам из 1 точки в другую точку слева представлена схема вложенных циклов, справа представлен пример.

168: Матрицы, которую мы используем. То есть это матрица градиента выбора. Мы используем пакет, а соответственно, реальная матрица выглядит немного не так. Она это вот мт матрица, какие мы провели модернизации, чтобы алгоритм находил

169: Именно проход из точки а в точку б самый оптимальный мы внедрили. Во первых, мы разделили алгоритм на 2 класса на класс генерации энд дженерейшен. Ну вот здесь написано не и на класс Муравья.

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

171: Муравей мог выходить. То есть итерация могла выходить из плохих маршрутов, а плохие маршруты это те маршруты, которые там, например, итерации, часто заходили в круги смерти. То есть они ходили из из 1 точки.

172: Другую по кварталам, то есть по 4 точки, либо вот по круговому движению. Очень часто муравьи ходили по кругу и, соответственно, это очень сильно сбивало феромон и следующие операции путались, не могли найти оптимальный маршрут с помощью генетической модификации. Мы избавились от этого, то есть

173: Если муравей заходил в смертельный путь, то следующие операции уже запоминали этот путь и больше его не повторяли, что очень сильно ускорило алгоритм. И у нас сейчас он выполняется вот здесь. Вот просто 0 5 секунд. Сейчас у нас он выполняется за 0,1 секунду.

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

175: На каждой точке сравниваем текущий поворот машинки с необходимым поворотом и, соответственно, выполняем поворот на - 90 либо на + 90 градусов. В зависимости от того, на какую точку мы поворачиваем по круговому движению. Немного по другому выглядит алгоритм. Здесь он

176: Предоставлен. Ну, мы просто проверяем, ну, вручную изменяем поворот машинки. Если, например, она там повернулась в точке 13, точку 11, то есть она должна быть повёрнута на - 90 градусов. Мы так, соответственно, её вручную поворачивае.

177: Вот данный алгоритм достаточно универсальный, то есть его можно использовать в графах очень, ну, с большим количеством точек тесты пока не проводились, но в теории можем повысить вычис, ну, мощности до

178: 15 на 3, то есть до 45 точек. Вот будем тестировать в свободное время. Песня. Ага, спасибо. Все, да.

179: Спасибо. И вопросы к решению участников. Да, хотелось бы задать вопрос. Вот вы сказали, что выбрали определённый алгоритм. Могли бы подробнее раскрыть, по каким причинам был выбран?

180: В сравнении с остальными, ну, которые вы рассматривали, соответственно, данный алгоритм был выбран с расчётом на то, то, что измене в конкурс в конкурсе могли быть изменения в условиях конкурс

181: То есть, если у нас будет, например, расширяться макет, или если у нас вдруг там на этапе может появиться задача коммивояжёра, то есть данный код решает эту задачу. То есть мы написали достаточно универсальный инструмент, который можно использовать в разных условиях.

182: Да, в нашем алгоритме есть масштабируемость. Главная особенность нашего алгоритма это его универсальность и масштабируемость. То есть он в главной своей, в главном своём образе может быть представлен для управления машин.

183: С автопилотом для роботов, с искусственным интеллектом. Дело в том-то, что эта вещь очень хорошо масштабируется под очень большие карты с сложными путями.

184: Спасибо большое. Ответ получен. Итак, у нас робот номер 5 готов. Можете подключаться и запустить вашу программу.

185: Остановить сначала. Угу.

186: Убери, пожалуйста, команду.

187: Что ещё раз ты, команда, не объявил, объявил это со в механическом городе кубанский государственный университет. Так, камеру видим на этот раз. Угу.

188: Запускаем.

189: Угу, странно, но a close давай-ка попробуем с телефона, чтобы я зашёл на мобильный интернет сейчас.

190: Если пишет close, он, значит, завершил выполнение, просто у нас тут правда, проблемы с интернетом есть, а возможно не отправил файл, да?

191: Да, да, я сейчас с мобильного попробую подключиться ко всему этому делу. Просто фаерволл может блокировать что-то 1 секундочку.

192: Да, это особенность нашего макета. У нас роботы. Я сейчас расскажу для слушателей, любителей нашего. У нас наш макет работает полностью через

193: Веб интерфейс, то есть роботы подключаются к серверу и участники и

194: Участники могут получить доступ к роботу к движению, управлению движением и к программированию можно жене телефона, так у вас получилось зайти напро.

195: Пробуем. Женя, говорю, попробуй с телефона, пожалуйста. Так, робот поехал, поехал. Угу.

196: До 4 точки.

197: До 5 точки.

198: Повернул в сторону 14.

199: Так, повернул в сторону 15.

200: Угу.

201: Повернул в сторону 8.

202: Повернул в сторону 9.

203: Доехал до 9, так поворот в сторону 10.

204: 5 точка.

205: Все это коне. Угу. Да. Так, отлично. Теперь проверим процент выполнения. 3, 4, 5.

206: 14, 15, 8, 9, 10.

207: Так, проверяем оценка 100%. Вы проехали по оптимальному пути.

208: Отлично, на этом все. Если у жюри больше нет вопросов, можно пригласить следующую команду.

209: Спасибо команде сон механическом городе. Далее приглашаем команду железный разум из

210: Здравствуйте, меня слышно? Да, здравствуйте. Можете подключиться к 5 роботу. Предыдущая команда. Да, отключитесь.

211: Пока ещё занят.

212: Можете обновить страницу, может сейчас появится.

213: Я обновляю каждые 3 секунды. Пока так. Команда сон в механическом городе. Отключитесь, пожалуйста, от 5 робота.

214: На кнопку отключиться, просто закрыть интерфейс будет пытаться, что

215: Ну, пока сейчас ещё занят, а другого робота нет.

216: Команда сон в механическом городе.

217: Вы отключились от робота?

218: Так если он ещё занят.

219: Да, да, да. Так, тогда давайте вы сейчас будете расскажете ваше решение, а коллеги переподключат его на 4.

220: Можете включить презентацию и рассказать ваше решение.

221: Так, вам видно? Да, все видно прекрасно. Так вот, сейчас я вам представлю адаптацию решения команды. А вот я её капитан, а также у меня были то помощник.

222: Можете видеть на экране, на вот задачи, с которыми мы столкнулись при подготовке к финальному этапу. Таковы. Нам нужно было адаптировать решение, которое мы, ну, из за начального этапа для

223: Работа на настоящих реальных роботов на роботах. Дальше пройти тренировочные заезды, оттестировать код, посмотреть, работает ли он правильно, если что, отладить его и предоставить итоговый результат. Вот для того,

224: Чтобы наш код работал.

225: А вам видно переключение слайдов? Нет, не вижу, у нас открыто.

226: Так, я понимаю. А вот если я так буду просто щёлкать? Да? Да, хорошо.

227: Просто я, когда демонстрацию слайдов дела. Ладно, хорошо, тогда заново начнём. В общем, задачи расскажу, с которой мы столкнулись. Нам нужно было адаптировать решение с 1 этапа для задачи роботов, пройти тренировочные заезды, протестировать код, если он неправильно выполнял.

228: Задачу его отладить и предоставить решение жюри для того, чтобы наш код работал на настоящем на новом, нам нужно было его реструктурировать.

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

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

231: Её не было в библиотеке модулям, нам нужно было написать её. Вот мы просто, ну, я думаю, как и все, удаляли связи из графа, что и значит, что препятствии существует на дороге дальше.

232: Функция main основная функция, где мы придаём значение для графа стартовые точки блоки, угол поворота, начальный флаги и запускаем нашу функцию draw собственно, которая у нас отрисовывает движение.

233: Ну и в ней также заключён, заключена функция, поиск, кратчайшее расстояние. Дальше. Вот дальше у нас написано алгоритм, который просто ищет кратчайшее расстояние между 2 точкам.

234: Ну, с учётом ограничений, которые у нас были в данной задаче, это то, что нельзя разворачиваться. В общем, угол поворот, так как он не весь, вот это его последний кусочек с

235: Реконструирование пути. Также мы решили использовать для упрощения, для увеличения производительности кода заранее подготовленные предрасчитанные дистанции кратчайшее.

236: Расстояние между любыми парами точек в графе. Вот для этого у нас существует такая функция. Далее у нас есть функция поиска, ну самая главная, которая так как счёт всего лишь

237: 2 точками, то нам нужно было запускать дестру по всем точкам, то есть от стартовой и по всем флагам. Ранее мы использовали банальную функцию, то есть использовали все перестановки флагов. Что значит

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

239: Число в двоичном виде и, допустим, у нас 15 точек, значит, может быть 15 флагов, значит у нас 15 цифр в этом числе и 0. Либо 1 отвечает за посещение данной точки. Если 0, то мы не посетили это

240: 1. Вот это значительно увеличило производительность программы в разы то, что мы делали, спросил, были ли какие-то числе начисления. Вот тут были и это даже

241: Позволило убрать кэширование, потому что оно даже не требовалось, потому что у нас алгоритм никогда не запускался повторно. Всегда все считалось с 1 раза. Вот. Далее, ну, опять же, не вся функция влезла на той, поэтому это её

242: Окончание и тоже с реконструкцией пути. И вот она функция сама дро, которая была в мейне. Тут мы, получается, считаем оптимальный путь и отрисовываем, ну тут уже не отрисовываем получаетс

243: Даём движение роботу. Вот далее, после написания этой программы, мы

244: Присутствовали, так скажем, участвовали в тренировочных заездах. Как это выглядело? Получается, мы вставляем свой код и смотрим по камерам, по радару, как у нас двигается робот. Каковы были итоги

245: Смогли, получается, отредактировать алгоритм для работы с реальным программным обеспечением. Вот также алгоритм был успешно модифицирован, её задача решается при помощи масс, что значительно улучшает его производительность. Вот, в общем,

246: Спасибо за внимание, это наша администрация. Спасибо команде железный разум и жюри.

247: Так, если нет вопросов, давайте я задам, насколько ваш алгоритм будет эффективен, если мы

248: Будем его тестировать в городе с не с пятнадцатью перекрёстками, пятистами, перекрёстками. Насколько сложно будет это адаптировать?

249: Ну, я бы сказал, что адаптация не требуется, потому что этот алгоритм уже рассчитан на большое количество входных данных. Для этого у нас как раз и существует битовая, она заменила

250: Перебор сложности. Вот поэтому.

251: Адаптировать его не надо, не следует, он уже адаптирован, а не нужно будет прописать эти битовые маски для всех этих.

252: Точнее, не городов битовые маски не не прописываются, они пересчитываются в условии, они изменяются при условии прохождения через флаг. И в любом случае, даже если это будет просто перебор по энному количеству.

253: То у него сложность будет просто, н что точнее даже перебор, по моему, является алгоритмом со сложностью единица, что в разы меньше, чем

254: Спасибо. Так, мне коллеги сказали, что можно подключаться. 4 робот, правильно? 4 роботу 5. Все сейчас.

255: Мне демонстрацию вам нужно или не нужно? Да нет, не нужно. Сейчас я вам продиктую, а я продиктовал уже стартовую точку.

256: Нет, нет, нет. Так, стартовая точка 7, стартовый угол 180.

257: Угу. Флаги 10, 8, 5. Угу. И блоки из 9 в 10, 9, 10.

258: Как будете готовы, можете.

259: Вроде как все о.

260: Вроде запустим.

261: Только у меня робот сейчас в точке 3 стоит, он говорили 7, и он не едет. Нет, он стоит в точке 7.

262: То вы говорили ещё раз, что робот

263: Robot под номером 4 da robot под номером 4.

264: Ну, у меня показывает просто радара то, что робот находится в точке e и надпись присутствует, что робот неактивен.

265: Вы изображение с камеры видите?

266: Нет.

267: Я могу вам сейчас, допустим, так, сейчас тогда перезапустим комнату.

268: Отключить от него.

269: Да, включается.

270: Отключился.

271: Говорят, что он работает.

272: Давайте тогда я подключусь ещё раз.

273: Ну, я опять сейчас, мне нужно, тогда продиктуйте, пожалуйста, ещё раз своё стартовое значение. Точка 7. Угол 180, флаги 10.

274: 5.

275: Блок 9, блок 9 10.

276: Угу. Попробуйте в начале подвигать. Попробуйте в начале подвигать с пульта управления, просто проверить, он на команды.

277: Ну, вот я сейчас жму на, ну, мне коллега подсказывает, что робот не занят, и вы к нему не подключились. А вы на какой market зашли? Нужен макет 1. О, это, кстати, хоро.

278: Вопрос, ну, вроде как 1, давайте посмотрим. Ну, у вас как называются логины, я перезашел 1, давайте вот камеры вижу. Видимо, я и правда зашёл не на тот макет, да, там сейчас появилось 3 макета. 1 у нас.

279: В сириусе находится 2, точнее, 1 у нас, 2 в сириусе и 3 он сейчас в главном корпусе ми. Там сейчас демонстрационный макет 2 на 2. Вот как будете готовы, можете записать или ещё раз?

280: Тогда нужны. Да, да, да. Так. Стартовая. 7 80, угол 180, флаги 10, 8, 5. Угу. Блок 9, 10, да.

281: Так, робот начал робот, поехали.

282: Так едет в сторону 8.

283: Поворот в сторону 15.

284: Так, поворот в сторону 10.

285: Поворот в сторону 9.

286: Город в сторону 8.

287: Поворот в сторону 15.

288: Поворот в сторону 14.

289: Так, ну все это финиш, потому что всем

290: Точка, а он по 5 ещё не проехал, а ещё, ещё впереди. А ещё 5, прошу прощения, да, робот едет сюда. Так доехал до 5.

291: Ну все, я остановился. Вот это финиш. Так, все отлично. Сейчас включаем, включим.

292: Так, маршрут, по которому он поехал, у нас получается 7, 8, 15, 10, 9, 8, 15.

293: 5 так, стартовая позиция была 7, угол 180 блокировки.

294: 9 10, lady 8.

295: 10, 8.

296: Так, проверка выполнения, оценка 100% здесь. Ну да, вы проехали по оптималь.

297: Так, понял. Спасибо. Спасибо, если у жюри больше нет.

298: Дальше. Далее приглашается команда техники сбн из кубанского государственного университета. Добрый день. Мы здесь коман.

299: Предыдущая, железный разум. Отключитесь от 4 робота и да, на кнопку нужно. И если, если он освободился техники сбн, можете так.

300: К 4 вроде подключились. Камера есть камера есть. Стоим в точке 1, судя по всему. Так, да, стартовая точка 1 угол 0.

301: Флаги 2:15, 9 секунду.

302: Угу. Блоки из 10 в 9 и 2 блок из 13 в 15.

303: Так, хорошо. Поворот 0.

304: Его.

305: Как будете готовы, можете запускать.

306: Ну, в принципе, готово. Угу.

307: Пропускаем.

308: Робот начал движение.

309: Остановился в точке.

310: В сторону 3 точки.

311: Поворот в сторону 4.

312: В сторону 5.

313: Поворот в сторону 14.

314: Проезд в сторону пятна.

315: Поворот в сторону 8.

316: Поворот в сторону 9.

317: А, все, на этом все, да? Так, отлично. Давайте сейчас берём.

318: Программа так, стартовая позиция 1 угол 0 блокировки.

319: Из 10.

320: 9 и из 13 в 15. Так, целевые то

321: 2:15.

322: Путь, по которому проехали 1, 2, 3, 4, 5, 14, 15.

323: 8 9.

324: Оценка 100% по оптимальному пути. И приглашаю данной команды выпить. Отключитесь, да, от машин заранее. Угу. Все отключились. Так.

325: Да, все видно отлично. Так, ну, теперь рассмотрим алгоритм нашего решения немного о нашей команде. Мы команда кубанского государственного университета из 3 человек стал Евгений, собственно.

326: Беляев Максим и Ненашев Дмитрий. Задача, которая была перед нами, поставлена на языке алгоритмов, это задача камера, то есть было необходимо из какой-то стартовой точки попасть в несколько целевых. При этом

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

328: Так, немного. Собственно говоря, как мы решали задачу, наше решение основывается на алгоритме дейкстра. Это алгоритм, который позволяет найти кратчайший путь между 2 точками, но так как у нас целевых точек не 1, а несколько. Соответственно, мы использовали

329: К этому алгоритму ещё и перебор перестановок, который попарно в алгоритм дейкстра передавал целевые точки справа представлен словарь dictionary, который описывает связи между точками.

330: На данном слайде представлен непосредственно алгоритм дейкстры, который теперь является методом класса роудс. Стоит сказать, что возвращает он длину наименьшего найденного пути между точками 2, а также путь, то есть

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

332: Вместе, то есть поворот на 180 градусов в принципе запрещён, также у нас фиксировано задан начальный угол, и так как 1 действием у нас идёт go forward, то есть обязательно машинка поедет вперёд, соответственно, она поедет в ту точку.

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

334: Для нахождения оптимального пути. И при его условии, что он меньше уже существующего. То есть функция анализирует последовательность точек и находит недопустимые, то есть из точки 10 поехать в 9, а потом обратно вернуться в десятку. Это

335: Некорректный маршрут, который будет отбракован нашей функцией, соответственно, ограничения на постановку были решены с помощью добавления ещё 1 переменной инейшн, которая вычисляет ту точку, в которую поедет наша машинка из стартовой позиции.

336: То есть ту точку, на которую она направлена. И непосредственно эту точку мы уже используем в качестве стартовой в алгоритме декстра. А действительный старт, да, с которого мы стартовали, мы просто плюсуем слева в финальный массив.

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

338: Делает все тоже самое, только теперь мы обходимся в принципе без использования сторонних библиотек, так как код должен запускаться на одноплатном компьютере.

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

340: В общий массив и суммируется общий путь если найденный путь окажется меньше, чем уже существующий, и путь окажется корректным без разворотов, то мы переприсвоил значение i mean, patt ленс и mean patt.

341: После того, как мы нашли маршрут, по которому необходимо двигаться, в принципе, можно по нему проехать. Для этого есть в цикле фор мы пробегаем по найденному массиву целевых точек, ну, тех точек, по которым необходимо двигаться, и вычисляем углы поворота. На какие углы.

342: Нужно повернуться, чтобы попасть в следующую точку. Вызываем модел ротейт, то есть поворачиваемся на определённый угол и двигаемся вперёд, в нужную точку. На данном слайде представлена в принципе инициализация.

343: Ритма, задание стартовых точек, блоков, угла, поворота, функция ремут рот, в принципе, удаляет заблокированные дороги из нашего словаря графа, чтобы алгоритм в принципе даже не пытался их рассматривать. Мы таким

344: Образом облегчаем в принципе задачу алгоритму и, естественно, пропускаем эти дороги. Соответственно, инициализируем гра модул функция не истеннен. Это та следующая точка, в которую мы поедем, про которую я говорил и вызываем

345: Функция нахождения минимального пути. Далее идёт функция go оо, то есть обязательно модель 1 действием едет вперёд. Ну и в принципе, результат работы алгоритма может выглядеть вот таким образом. Это массив тех точек, по которым нам необходимо двигаться. Далее мы

346: Просто в цикле двигаемся по найденному массиву.

347: Вот таким образом работает алгоритм. Если есть вопросы, готов ответить.

348: Спасибо жюри, предлагаю задать вопрос.

349: Anton вас не слышно.

350: Нет.

351: Так, ну давайте пока Антон готовит микрофон. Вот вопрос вам нужно для, для каждого, грубо говоря, города, городской среды. Вам нужно заранее прописать весь этот

352: Граф вручную правильно понимаю? Так, ещё раз вручную. Что конкретно, ну, прописать весь граф, то есть все связи прописать вручную, да? Ну да, конечно. Как, каким образом алгоритм, в принципе, будет знать.

353: Плане маршрутов, если их как бы не задать. То есть в симуляторе программы тоже граф был задан в формате словаря. В принципе, это является оптимальным способом задания.

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

355: Насколько сложно было бы переделать так же, вот как

356: Ну то есть к большому городу перекрёстков и так далее. Возможно там пришлось бы как-то по другому составлять графики, писывать там связи.

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

358: Возможно, даже с помощью каких-то сервисов более наглядного построения, которые из, так скажем, наглядного построения генерируют непосредственно словари, которые можно использовать в коде.

359: Да, понятно. Так, уважаемое жюри. Есть ли ещё вопросы?

360: Понял у антона.

361: Ну хорошо, тогда благодарю команду техники сбн. Далее приглашается команда 0 закон сгту имени Гагарина.

362: Есть представители команд.

363: 0 закон сгту имени Гагарина.

364: Можно, извиняюсь, нас, проблема с этим, с микрофоном возникла, а все хорошо, да, так вы можете подключаться к 4 роботу так 4 роботу?

365: И я вам продиктую позицию. Хорошо?

366: Секундочку.

367: Он.

368: Я вас внимательно слушаю. Стартовая точка 3, стартовый угол 270, флаги 8, 10, 14.

369: Так, 8, 10, 14, 14. Блоки 15, 10.

370: И 14:15 пу пу секундочку.

371: Блоки, блоки, блоки.

372: Из 15 в 10 и 14:15.

373: Секундочку, потерял, здесь же они оказывались

374: 1 ровер старт пост старт оо.

375: Вообще эти данные, ну то есть о блоках они в библиотеке без control module они не предусмотрены.

376: Ваша задача нужно самим определить заблокированный и нужно туда ехать, потому что робот туда, в принципе, может поехать. У него нет ограничений физических.

377: Так, надо было сделать так, ну давайте проверим то, что у вас есть сейчас уже в любом случае, да, так как будете готовы, можете запускать, в принципе, готовы. Угу.

378: Угу.

379: Запись.

380: Sit запускаем.

381: Остановите программу там. Угу. Остановили. Перезапустим. Продолжить отключиться. Пока что. Да, отключитесь. Контрол, контрол.

382: Отключиться.

383: То есть, да, вот отличие полуфинала от финала в том, что робот может ехать как угодно. Ну, в пределах дорог. То есть вы должны верхнеуровнево были планировать.

384: Без учёта, естественно, движения по линии и так далее. Это не была ваша задача было самим искусственно ограничить его вот с учётом, ну посмотри.

385: Там сейчас возможно. А возможно я сейчас пока вы его перезагружаете, найду кусок кода, который у нас это делает.

386: Не исключена такая вероятность.

387: Пу пу пу пу пу

388: Когда же мы это могли?

389: Куда-то сюда, что ли?

390: Точно, вот отсюда сейчас сворую.

391: Скорость адаптации уровень божественный. Так где она?

392: Не то светофор, и вот он, наш чудо это.

393: Открыть с помощью

394: Блокнот

395: Светофор, схватить контрол.

396: Куда-нибудь вот сюда, контрол б.

397: И получается все, что мне нужно сделать, это, это

398: Вот здесь вот.

399: Поступить.

400: Так там почти что подготовили робота.

401: Угу.

402: Имп. Нижнее подчёркивание, граф равно света.

403: Вращать либо true, либо

404: Реал он не перестраивал.

405: Это я потом делал, чтобы он перестраивал косяк тогда.

406: Передают, пока ещё не включили. Давайте вы продемонстрируете решение с презентацией. Установит. Хорошо, включайте демонстрацию.

407: Угу. Так, где вы тут? У меня телемост так, телемост, демонстрация.

408: Где?

409: Окно.

410: Так, вам видно демонстрацию, да?

411: А, 5 минут. Угу. Хорошо. Здравствуйте, уважаемые жюри и коллеги, мы команда 0 закон из саратовского государственного технического

412: Университет имени Гагарина. Выступаем. Ну, участвуем в составе 4 человек. Максимов Андрей занимался построением оптимального пути алгори, основными алгоритмами для хода графа Абаренов Александр.

413: Ну, занимался, ну, анализом этих всяких помех на дороге и тому подобного. Станислав и Саров Алексей занимались как бы связкой всего этого для того, чтобы

414: По построенному маршруту, при помощи графа робот мог проехать по, ну соответственно, по точкам и так далее, что мы изменили из предыдущего

415: Нашего у нас на экране сейчас 1 слайд, то есть у вас пауэрпоинт открыт.

416: Ага, странно. Тогда, скорее всего, он странно как-то относится к

417: Мои трансляции. Сейчас я её перезапущу, то скрыть, остановить. Демонстрация, окно, да, он почему-то подразделяет демонстрации. Это так.

418: Теперь вам видно, да, все видно, да? Вот я на всякий случай покажу предыдущие слайды были, да, что мы изменили? Мы ранее строили.

419: Оптимальный путь по алгоритму флойда уоршелла и использовали жадный алгоритм для полного восстановления пути. Затем мы на этом этапе решили отказаться от жадного алгоритма и перед

420: И после использования алгоритма флойда уоршелла на основе данных, которые он обработал нам алгоритм алгоритм хельда карпа берет и на, ну, уже достраивает маршрут.

421: На кратчайшем, наикратчайшем пути. Вот здесь описание работы алгоритма флойда вошла, зачитывать не буду слишком долго. Да, алгоритм хельда карпа, что он делает на основе тех данных, которые ему, ну, подал.

422: Этот вошёл, он создаёт энное, ну, он берет, перебирает все возможные подмножества, и в результате этого у обходит полный перебор, дабы не

423: Перебирать все возможные пути из точки а в точку б он перебирает подмножество и переиспользует схожие подмножества, дабы сократить количество перебора и как бы оптимизировать алгоритм. И в итоге из этих

424: Множественно выбирается наикратчайшее, которое будет являться кратчайшим путём, да, далее для восстановления всего

425: Восстановление пути. Был использован алгоритм дестра пу пу пу. Далее для того, чтобы обнаружать, ну, типа, если на пути препятствия, ну, это алгоритм был в предыдущем этапе, мы использовали

426: Ну, такой вот простой алгоритм, который тупо перебирает графы, если в этом графе есть, точнее не графы, а пути, путь перебирает, если в этом пути есть

427: Как бы на пути встречаются те самые блоки, то, значит, путь не подходит. Надо удалить из графа этот путь это соединение на дороге. И потом, значит, запустить опять построе.

428: Оптимального маршрута, уже не учитывая эту связь между этими 2 точками. Движение по маршруту мы далее для того, чтобы связать вот это все, все алгоритмы обнаружи построения оптимального маршрут

429: Алгоритм нахождения помех. Мы тупо перебором списка тех точек, по которым надо проехать, написали алгоритм, который будет ехать максималь.

430: Ну, не, не нарушая правила того, что нельзя поворачивать на 180 градусов, в принципе, и то, что нельзя. Время заканчивается ещё 40, да.

431: И нельзя стартовать при старте, разворачиваться также перед тем, как запустить этот, ну, подать алгоритм, ну, путь в этот финальный связывающий алгоритм, мы перебираем опять же, все невозможные.

432: Повороты, то есть не более 100 градусов, нам нужны повороты. Заключение. Мы изучили проблему нахождения оптимального пути маршрута и перебрали множество вариантов и разработали решение прохождения оптимального маршрута.

433: Точки, а в точку б.

434: Все, спасибо на этом.

435: Да, да, спасибо. Спасибо, жюри. Предлагаю задать вопросы.

436: Так, если вопросов сейчас нету, давайте я задам ещё раз. Напомните, какой алгоритм. Название алгоритма его использовали для нахождения оптимальных. Мы использовали 2 алгоритма.

437: Floyd ворола и хельда карпа.

438: То есть 1 он находил у нас оптимальный путь.

439: Ну оптимальные, ну да, оптимальный путь. A2 находил оптимальные пути он находил, а карпа находил из них кратчайшие, дабы исключить ошибку.

440: А как же тогда 1 находил оптимальный, по какому параметру?

441: Если кратчайший выбирать 2 алгоритм.

442: Ну, флойда Орла в 1 нашем этапе по какой-то причине зачастую

443: Мог выбрать при, ну, из 2 псевдо оптимальных путей, не тот, который был нам нужен, и

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

445: Понадобится. И просто сверху на него навесили ещё 1 алгоритм, который, ну, довольно-таки оптимизированный, чтобы не менять флойда оо. По какой-то причине он

446: Давал непра неоптимальный маршрут. Хорошо. Угу. Я понял. Так, если нет больше вопросов, можете подключаться к 4 роботу и

447: Программа. Ну, я вам продиктую.

448: Стартовую позицию занять.

449: Можно. Угу. Сейчас скопирую.

450: Контрол а контрол ц.

451: Контрол в.

452: Демонстрация выключить.

453: Так, подключились к роботу. Угу. Да, подключился. Диктуйте, да. Видео есть. Так, стартовая точка 3, стартовый угол 270.

454: Флаги 8, 10, 14, блоки из 15 в 10, из 14 в 15.

455: Угу. Запускаем.

456: Робот начал движение точка.

457: Поехал до 5 поворот в сторону 14.

458: Так он поехал по пути из 14 в 15 и столкнулся с роботом, который был

459: Заблокирован. По сути, на этом попытку можно завершать, потому что робот врезался.

460: Так, нажмите остановить.

461: Нажали. Угу. И отключайтесь. Так, сейчас посмотрим процент выполнения.

462: Так, маршрут был 3, 4, 5 и 14, стартовая позиция 3, угол 270.

463: Блоки 15 14.

464: 14, ой, из пятна, да, правильно сказал. Из 15 в 10, 14, в 15.

465: 14, 15.

466: Лаги 8.

467: 14. Так, оценка 33 и 3%. И врезались.

468: На этом спасибо команде 0 закон из сгту имени Гагарина. Следующая команда энергия из филиала неми в городе Смоленске.

469: От робота команда 0 закон. Подключайтесь.

470: По свободный.

471: Отключились. Спасибо. Так, команда энергия, филиал нумы в Смоленске.

472: Так кто-то пишет нет звука.

473: Возможно, тайны.

474: Так, напишите в чат, если это вы.

475: Команда энергия. Нас слышно? Да, слышно. Теперь слышно отлично. Итак, подключайтесь к роботу номер 4.

476: Так, занима.

477: Работает.

478: Камера не запустилась. Ну, обычное дело. Так, а попробуйте подвигать моторами вперёд назад.

479: Двигать? Да, работает. Ну, можно без видео. Думаю. Хорошо. Давайте попробуем. Стартовая точка 15. Подождите. 15. Стартовый угол 270.

480: 270, флаги 1 2 3.

481: 1, 2, 3 и блоки 8, 9.

482: Простите, я неправильно. А, стоп, я продик. Я продиктовал. Стартовая точка 15, стартовый угол 270. Правильно? Верно? Да. Флаги 1, 2.

483: И да. Угу. И блоки 8, 9.

484: Да, да, все, все, как будете готовы, можете запустить. Ой, можно заново я запустить нажал, да, остановить.

485: Он на месте стоит? Да, да, он на месте.

486: Угу. Так, робот начал движение, поехал.

487: До точки 8.

488: Поворот в сторону си.

489: Можете остановить, нужно перезапустить робота. Он неправильную камеру выбрал.

490: Хорошо читаться. Перезапусти. Отключитесь от роботов, пожалуйста. Сейчас скопирую код. Отключились. Давайте тогда тоже.

491: Вначале презентацию и запустим не задерживаться.

492: Да, все видно, все нас видно. Да, да. Итак, всем ещё раз доброго дня на связи. Команда энергии из смоленского филиала ми. И сегодня речь пойдёт о том, как был доработан алгоритм дейста для решения нашей задачи.

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

494: Позволяет знать кратчайшее расстояние до каждой вершины, но, во первых, мы должны помнить, что оптимальный маршрут не должен проходить через 1 участок 2 раза, то есть, по сути, такие варианты

495: Мы сразу должны отметать, и мы должны как бы использовать жадный алгоритм, но немного его доработать, потому что они могут приводить иногда не к оптимальным. Решён.

496: В нашем случае мы берём маршрут по жадному дейкстре, собираем все пройдённые точки и запускаем его заново, но уже с новым набором и потом уже.

497: Смотрим, повторился ли наш маршрут или нет, то есть у нас дейст это стандартный алгоритм, который прохо находит кратчайший путь от текущей ноды до каждой другой ноды и возвращает последовательность кратчайшего.

498: Пути от ноды к ноде. У нас же, соответственно, в отличие от стандартного алгоритма дестра, так называемый алгоритм редекса это функция, которая вызывает алгоритм дейкстра из каждой следующей ноды.

499: По алгоритму дейкстры она возвращает новый полученный маршрут и его длину, например, такой ситуацией может быть, если начальная точка 10, конечная 1, а угол 270 градусов.

500: Итак, у нас блок схемы, можно выделить 4 как бы основных этапа. То есть у нас есть алгоритм реестры, то есть отличается он тем,

501: Что учитываем мы пройдённые точки или нет. Вот на правой картинке наш реестра и также экстру используют так.

502: Фильтр генсек от английского дженнера сиквенс на входе этому генсеку выдают текущую ноду, угол и ноды, по которым нужно пройти, использует алгоритм генсек среди спи.

503: Нужных нот ищет ближнюю. Далее он двигается к ней и удаляет из списка. И повторяется все так до тех пор, пока список не остаётся пуст. На выходе у нас, соответственно, выдаётся путь, по которому

504: Прошли бы тестовый генсек, он ломает, он исключает проблему, когда маршрут неоптимален, и заглядывания в будущее он заведомо подсовывает генсеку большее число нот что?

505: Изменяет выбор следующей точки, если это необходимо. И он использует маршрут, полученный генсеком, и пробует дать список требуемых нот ещё и те, по которым он проходил во все маршруты. Ну что?

506: Было нагляднее. Мы посмотрим на тестирование. Итак, у нас есть справа наш модифицированный алгоритм, а слева классический алгоритм, жадный, так жадный алгоритм, дойдя до точки, например,

507: 15 он может увидеть некоторую сложность с тем, что 15 до 8 он поедет, а из восьмёрки он может попасть только в девятку и разворачиваясь по этому.

508: Он пройдёт из 15 8 путь 2 раза, что делает маршрут наш неоптимальным. Соответственно, наш алгоритм это, эту проблему решает, чем

509: Он отличается от классического алгоритма дейкстры. У нас, как мы сказали, оптимальный маршрут. Он не проходит по рёбрам 2 раза, но по точке 10. В принципе, она же стартовая.

510: Мы прошли 2 раза и тем самым сильно сократили путь. Нам не пришлось вот объезжать это кольцо. И, соответственно, длина маршрута стала намного меньше. Вот, например, ещё какой-нибудь марш.

511: Если у нас 1 точка на кольце, соответственно, мы должны поехать в 4, чтобы не пройти 2 раза, и вот получаем наш оптимальный

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

513: Спасибо за внимание, если есть какие-то вопросы, готов на них ответить.

514: Спасибо, энергия. Очень интересное решение. У меня вопрос, насколько сложнее или легче стал вот этот вот модифицированный алгоритм? Ну, именно по вычислительным

515: Легче и он стал достаточно сложнее, но тем самым увеличи улучшилось качество маршрута а какой порядок примерно?

516: Так, ну насколько он увеличился там, а вычисления, да, значительно. Алгоритм екстри стандартный стал вызываться. Ну,

517: Вот мы тестировали, скажем, раз, 4, 5 больше стандартный алгоритм. У меня это в целом, это не настолько, значит.

518: Ну, то это будет увеличиваться количеством точек, по которым это проходит. Ну да, да, конечно, города это

519: Есть ли ещё вопросы?

520: Итак, у нас освободился робот. Можете к нему подключаться.

521: Robot, car 4.

522: Запускаем точки такие.

523: Так, я вам диктовал уже? Да, да. 15, 278, 9, 1, 2, 3. Да, все правильно. Можете запускать.

524: Запустили.

525: Так доехал до точки, ну, верхушку повернул в сторону точки 7.

526: Доехал до точки.

527: Это другое едет в сторону точки 6.

528: Едет в сторону точки 5.

529: Ты.

530: Так он повернул.

531: Так он доехал до точки 4, проехал её, едет в сторону точки 3.

532: Поехал.

533: Далее поворот в сторону точки.

534: Доехал до точки 2.

535: Едет в сторону точки 1.

536: Да, все доехал. Ну все, в принципе, это, я думаю, это финиш. Так, давайте посчитаем баллы, которые у вас были за проезд. Ваша стартовая позиция, 15.

537: Угол 270, блоки 80 и

538: Точки 1, 2. Так, а не видим проехал у вас.

539: 15, 8 7 (765) 432-13-21. Проверяем. Оценка. 100% проехали по оптимальному пути.

540: Все, спасибо команде энергия. Далее приглашается команда bts из и команда энергия, отключитесь от роботов.

541: Здрасьте. Отключились.

542: Ага, спасибо. Команда bts. Н да, да, тут, да, мне коллега советует перед тем, как подключиться к роботу, обновите страничку, то есть вот где выбор роботов.

543: Обновите страницу и подключайтесь. Угу. Да, да. Обновил. И к 4.

544: A4.

545: Да, все, видео есть, есть. Так, отлично. Тогда диктую стартовую позицию. Сейчас, сейчас, секунду загружу. Код только давайте так. Позиция стартовая. Точ.

546: 7. Стартовый угол 0. Флаги. Угу. 10, 8, 5, 10, 8, 5. Блоки. Блоки 9.

547: С 9 8. Ага. Запускать. Если да, да, сейчас закину. А конечная какая?

548: Ну, у вас флаги 10, 8, 5. Угу.

549: Так, сейчас, секунду.

550: Так. Угу.

551: Так, ещё раз проверю. Стартовый 7, угол 0, флаги 10, 8, 5, блоки 9, 8. Да, все правильно. Угу.

552: Так.

553: Отключитесь, а точнее, выключите робота и отключитесь от него. Ага. Отключился. Неправильно завершили программу. Угу. Я нажал остановить, отключился. Сейчас его перезапустят и

554: Давайте также пока презентацию, презентацию сначала. Да? Так, сейчас демонстрация.

555: Видно.

556: А, прогружается есть, да? Угу.

557: Так, ну, в общем, была такая же задача найти оптимальный путь с учётом стартовой ориентации обязательных точек, ну, флагов из запечённых рёбер и из за машин того, что не может поворачиваться на 180, ограничить это

558: Также ещё через дестро создали граф в виде точек, из откуда, куда можно ездить, и их расстояние с их весами, и добавили блокированные ребра также, так как

559: Машинка должна ну робот должен ездить только обязательно начинать с go over то есть с движения то было написано выбор 1 шага, то есть мы определяли по стартовой позиции и углу какой следующий шаг должен быть.

560: Ну e используем модифицированную, ту, которая входит обязательно флаги не делает разворот на 180 и учитывает запрещённые ребра, то есть мы просто удаляли.

561: А вот сам код.

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

563: И переводили до 90 так машинка может двигаться только 90 градусов.

564: И также так как была интересная особенность проезда машинки по кругу, то, что она въезжала под определённым углом, а могла выехать, ну, когда проезжала на какую-то точку, повернуться на определённый другой, поэтому было составлено исключение.

565: В виде графа, ой, в виде массива, где было задано положение, под которым нужно въезжать в какую точку угла и какой угол становится при проезде. Ну и вот просто пример запуска.

566: В целом, вот мы улучшили алгоритм по сравнению с прошлым, то, что, например, там была функция ненужная нормализации угла, которая там 2 сам делал, она была удалена. Алгоритм был сведён в 1 и

567: Вот этот разворот на 180, он был более лаконично реализован. Раньше у нас с проверял, ну, создавал путь, а потом проверял, есть ли он там бесконечно, пока они не будут, пока не, пока полностью не уберёт.

568: На 180. Сейчас же он пока составляет, проверяет, не сделал ли он разворот на 180 во время своего просчёта.

569: Спасибо жюри, предлагаю задать вопросы. Там у некоторых есть. Ага, да, слушаю. Да, подчинялся микрофон.

570: Такой вопрос. Соответственно, вот как и предыдущая команда, вы использовали алгоритм дейкстра, вот, и они говорили об том, что неоптимальные пути выбираются. Вот у вас с этим, я так понимаю, проблем не было с неоптималь.

571: Путём, да, то, что проезд нет, с этим проблем не было. Ну, то есть хорошо предыдущая команда разговаривала, говорила то, что он была ошибка, то, что он не может в своей логике проезжать несколько раз по 1 и тому же маршруту. Вот, а у нас

572: Может. То есть, если там я это имел. Угу. Хорошо. Соответственно, тогда поясните, что вы написали поверх этого алгоритма, чтобы выполнять условия конкурса. Ну вот все вместе, если собрать

573: В плане, то есть запрет разворотов, проезд по точкам и поддержка блокировок. Вот все очень ааг.

574: Так, спасибо. Робот готов. Вы можете подключаться. 4 робот. Демонстрацию включить. Да, да. Можете выключить.

575: Так, 4 робот. Угу.

576: Так, стартовый. Ещё раз проверю. Стартовый. 7, угол 0, флаги 10, 8, 5, блоки 9, 8. Так, да, все правильно. Угу.

577: Так, робот поехал.

578: Доехал до точки 6.

579: Далее повернулся в сторону точки 5.

580: Use.

581: Поворот в сторону точки 14. Угу.

582: В сторону точки 15.

583: Поворот в сторону точки.

584: Когда?

585: Поворот в сторону точки 9, поворот в сторону точки 9.

586: Так, на этом все, да. Остановить код? Да, да. Останавливайте код на кнопку остановить. Потом отключай. Да, да. Все. Угу. Закрывай.

587: Окно браузера. Ну, на всякий так, проверяем. Маш. 7, 6, 5, 14, 15.

588: 9 10.

589: Угу. Оценка 100%. Отлично. Да, можно отключаться, да, спасибо команде втс. Далее команда робо кодера. Это крайняя команда студенчес.

590: Треки робокод ры не умные. Да, здравствуйте. Нас слышно, да, если робот освободился, можете подключаться к нему 4.

591: Так, так, да, робот свободен. Подключился. Стартовая позиция. 15. Угол 270, да? Угу.

592: Целевые точки. 1, 2, 3. Так, да, есть блоки 8, 9. Угу. И

593: 8, 9 и 6 5.

594: 6, 5, да, если готовы, можете.

595: Тогда готовы? Запускаем.

596: Так он доехал до точки 9, поворот в сторону точки 1.

597: Точки рот в сторону точки 2.

598: Проезда точки 3.

599: Все. Ну, в целом все, да.

600: Да, можно останавливать, отключаться, да. Ну, в смысле остановить, отключиться и закрыть браузер.

601: Угу. Да, готово.

602: Так, а у вас стартовая позиция была 270?

603: Да, а как вы проехали в точку?

604: Вы же робот развернули на наших глазах.

605: То есть он, он у вас должен проехать из 15 8.

606: У вас есть путь, который он должен был пройти?

607: Давайте перезапустим. Просто здесь, возможно, коллеги, кто следит за проездом роботов, они подумали, что вы направлены в другую сторону. Давайте сейчас пере, да, подскажите тогда ещё раз 4 машину, да, на 4.

608: Так, ещё раз можно точки так.

609: Стартовая, 15, стартовый. Так, 207.

610: Так, да.

611: Флаги 1, 2, 3.

612: Блоки 8, 9. Угу. 6, 5.

613: Так можно запускать? Да, да.

614: У вас немного не по правилам едет робот, он не может на месте развернуться.

615: У вас 1 действие. Обязательно должен быть проезд до точки следующей. Остановите.

616: Верните робота обратно.

617: Это какая-то ошибка или у вас так работает алгоритм?

618: Вероятно, ошибка какая-то.

619: Давайте вам 3 попытку, просто непонятно, почему так.

620: Ну, в начале робот не может поворачиваться.

621: Так, ну он опять, ну, вероятно, да, на нашей стороне.

622: Видите роботы?

623: То есть проезда нету.

624: Быть может можно какой-то другой маршрут. Ну, маршрут.

625: Мы не можем дать, потому что здесь уже варианты.

626: Присвоено, то есть. Угу.

627: Так, ну если у вас не может проехать, значит, проезд 0%.

628: Странно, почему вы на тренировочных заездах выполняли?

629: Да, естественно, и все сразу хорошо работало. Ехал он сначала прямо, потом только поворачивал.

630: Робот у вас в самом начале поворачивает.

631: Давайте тогда перейдём к презентации.

632: Так, подскажите, видно ли презентацию? Да, все видно.

633: Так, в рамках данной презентации я хочу рассказать о решении, которое мы разработали в рамках участия роботы в городе в конкурсе роботы в городе. Цель всего этого заключается в следующем. Написать алгоритм оптималь.

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

635: Блок схема нашей программы. Видно, что на вход в программы у нас подаётся начальное положение нашего робота. Целевые точки, некоторые заблокированные участки и начальный угол поворота. Далее эта информация идёт на 1 наш блок.

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

637: Выполняет движение, ну и, соответственно, двигается. Соответственно, вот так вот, как уже было сказано, 2 основных класса в нашем алгоритме представлено, которые е звучат вот так. Рут оптимайзер отвечает за

638: Поиск оптимального маршрута с учётом блокировок. А смарт навигатор управляет движением робота по построенному маршруту и собирает целевые точки. В начале мы задаём наше стартовое положение, точку старта, угол, на который

639: Изначально повёрнут робот точки, которые обязательно нужно проехать, и некоторые целевые, некоторые заблокированные участки.

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

641: То в нашем алгоритме учитывается цена поворота и блокировка рёбер графа, что вообще из этого понимается. Допустим, у нас существуют такие маршруты, которые занимают 1 и то,

642: Расстояние робот проезжает одно и то же расстояние, но разное количество Поворотов при этом может сделать, соответственно, для того, чтобы уменьшить время проезда, меньше нагрузить робот, ему нужно проехать данный маршрут.

643: С учётом меньшего количества Поворотов, меньшего перекрёстков, меньшего количества перекрёстков. Из этих соображений мы ввели такое понятие в наш код. Ну, блокировка рёбер графа используется для того, чтобы учесть тот факт.

644: Так что на нашем маршруте могут находиться другие роботы и не проезжать через данный участок.

645: Далее у нас происходит движение робота в классе оптима. В методе оптимайз роуд. Соответственно, на каждом шаге у нас вызывается метод экстра значения, оттуда берутся и таким образом прокладывается маршрут и робот.

646: Двигается на данном слайде, представлена картинка робот останавливается перед QR кодом, смотрит, в какой он точке находит, находится и принимает решение, куда ему двигаться дальше спасибо так, спасибо.

647: Команде робо кодеры, а можно нам ещё 1 раз попытку дать? Мы целевую точку ещё 1 поставим промежуточную.

648: Так как считает жюри, ну, я считаю, можно, учитывая, что не совсем объяснимые условия того, почему робот сразу разворачивался, команда уверяет, что не вписал.

649: Это условие, возможно, какая-то особенность. Ну хорошо, тогда давайте перезапустим. То есть опять же целевые точки. Те же самые 1, 2, 3 блоки в тех же местах, стартовая 15 и 270.

650: Он направлен в сторону точки 8. Давайте попробуем перезапустить.

651: Все робота установили? Можете.

652: У вас получилось подключиться к роботу? Да, робот, к роботу мы подключились?

653: Так, да, робот начал, движение едет в сторону точки.

654: Он не останавливается на перекрёстке у вас неправильно.

655: Да, он считает, что он едет в другую сторону, поэтому остановите робота.

656: Угол остаётся 270. То есть он смотрит в сторону точки 8, если вы ему указываете, а, простите, пожалуйста, мы с 1 точки начали. Можно ещё раз с 15, мы начинаем, да, вы 15.

657: То есть он на неправильном перекрёстке, он останавливаться не будет.

658: Остановился, да, вот теперь правильно.

659: Но он врезается в блок, который у вас был. Этом попытка завершается. Ну, здесь уже.

660: Устанавливайте программу, да, все. И правильно. Там отключитесь от робота, чтобы он не звонил. Угу. Так, ну давайте подсчитаем тогда маршрут, который он проехал из 15 8.

661: Да, он выдаёт, если мы уберём.

662: Так, у вас показывает это не 0%. 1 точку он проехал, правильно?

663: А как должен был он? Стоп, стоп, стоп. Нет, он не проехал ни 1 из оптимальных точек. Сейчас я, получается, у него оптимальный маршрут в данном случае.

664: Вот для вашей дорожной ситуации это 15, 8, 7 14 5, 4, 3, 2, 1. То есть он должен был поехать в другую сторону, а он вас. А как это так, если у нас 1, 2, 3 маршрут стоит, как он должен

665: Ехать у нас стоит маршрут 1, 2, 3, 1, 2, 3. Это целевые точки, это не маршрут по очереди все команды проезжали не в том порядке. Ну это необязательно было.

666: Итак, 0% прохождения и отмечаем баллы за защиту. Вопрос можно задать, да, соответственно, команде по поводу того, что вот если исправить

667: Ошибки в коде. Насколько масштабируется данный код, вот насколько он оптимизирован для быстрого взаимодействия с роботом.

668: Позвольте уточнить, а что под вашим подразумевается быстрое взаимодействие? Ну, я имею ввиду, насколько быстро выполняется код принятия решения, то есть, насколько возможно увеличивать скорость робота, грубо говоря, и при этом успевать?

669: Ориентироваться.

670: Быстродействие кода.

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

672: Хорошо, а масштабируемость?

673: То, что это

674: Ну, в любом случае, можно его масштабировать, конечно же, дополнительные какие-то условия создавать, например, там динамическое расположение препятствий, все это можно, конечно, делать. И не думаю, что какие-то проблемы возникнут. Спасибо у меня

675: Вопросов нет. Так, тогда завершаем оценку студенческих команд конкурса роботов в городе команда робокод. Прошу отключиться от робота и мы

676: Переходим к

677: Оценки школьных команд немного выбились из регламента на 17 минут, поэтому презентация школьников будем отслеживать, чтобы было 5 минут на выступление, 3 минуты на вопрос.

678: Вопросы от жюри и запуск робота.

679: Так, давайте я ещё раз.

680: Озвучу правила выполнения заездов для школьных команд.

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

682: То есть участникам достаточно проехать просто оптимальный путь с учётом начальных условий, то есть точки и угла поворота. Также все ограничения на разворот на месте и так далее здесь присутствуют.

683: Подсчёт баллов будет точно таким же, будет высчитываться процент прохождения оптимального пути, максимум за проезд можно получить 7 баллов.

684: При проезде 100% и далее оценивается выступление с презентацией решения максимум в 3 балла, то есть суммарно можно получить 10 баллов.

685: Если вопросов нету, мы приступаем к оценке школьных команд.

686: Итак, 1 команда, которая у нас подключается, это команда паяльники из школы номер 20 89.

687: Здравствуйте. Подключаться к 4 машинке, да, к 4 машинке.

688: Как будете готовы, я вам продиктую вашу стартовую точку.

689: Я готов. Итак, стартовая точка 1 стартовый угол 0.

690: Флаги 9:15.

691: 9:15.

692: Если готово, можете.

693: Команда паяльники у вас получилось перезапустить. Сейчас, подождите, подождите. Да я просто изменяю. Ну, ввожу.

694: Сейчас, извините, выдаёт ошибку при запуске. Подождите.

695: А видео с робота есть?

696: Видео с робота нет, а видео нет.

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

698: А какая ошибка.

699: Сейчас отправлю в чат.

700: Я не могу отправить.

701: Так, ну ошибка, понимаю, быть ошибкой в вашей программе.

702: Попробуйте демонстрацию экрана показать, возможно, мы поймём, в чем проблема.

703: Так, ну вообще ошибка у вас входе.

704: А ошибка в

705: Табах. Возможно, вы где-то вместо таба пробел поставили или что-то подобное. Попробуйте редакторе.

706: Да, это особенности программирования питон, где обязательно должны быть правильные отступы во всех циклах.

707: Да, подождите сейчас, извините, тогда минуту я исправлю буквально. Давайте тогда следующей команды.

708: Отправляйте белые табы, давайте послушаем команду. Акселераторы одинцовский 5 лицей.

709: Так вы че то говорили, я вас не слышу.

710: Я не слышу капитана или представителя команды.

711: Так я не слышу представителей команды.

712: Так вижу, так пишут.

713: Проблемы с микрофоном. Хорошо, сейчас подождём тогда.

714: Если паяльники будете готовы, можете сказать об этом.

715: Alone?

716: Здравствуйте, это команда акселераторы. Да, здравствуйте. Так, можете подключаться к роботу.

717: А нас на сайт не пускает, выдаёт ошибку web socket connection.

718: Попробуйте с другого интернета или с другого, как сегодня.

719: Получается подключиться.

720: Пока нет.

721: Так, *** паяльники, может быть, у вас получится.

722: В целом, если вы предоставили код, можно запустить туда и посмотреть, как будет выполняться проезд, нет возможности подключиться. В принципе, для этого это и было.

723: Сделано. Давайте тогда команда паяльники. Вы скидывали же код.

724: Сейчас, подождите, я вроде исправил, я могу снова подключиться, попробовать?

725: Ну, попробуйте подключиться. Робот тот же самый.

726: Вы подключились?

727: Да, да, я ввожу точки тогда сейчас я попрошу её поставить в нужную точку. Пожалуйста, поставьте робота в точку паяльники.

728: И вам продиктовать стартовую позицию, флаги или все есть?

729: Продиктуйте, пожалуйста.

730: Так, команда, поехали. Стартовая точка 1. Стартовый угол 0, флаги 9, 15, 10.

731: Как будете готовы, запускайте.

732: Молчите, пожалуйста, говорите, если есть проблемы.

733: Сейчас я вроде исправил пробелы и табы, но все равно не работает, робот едет.

734: Он поехал из точки 1 в точку 2.

735: Доехал до точки 2.

736: Проезжает до точки 3.

737: Останови.

738: Итак, поворот сейчас был в правильную сторону.

739: Поворот не в правильную сторону все останавливается, он врезал

740: Остановите программу, пожалуйста.

741: Ясно. И отключитесь от работы.

742: Так, проезд 1, 2, 3. Посчитаем у нас. Можете пока включать презентацию.

743: Так, ну это 0%, потому 1 из точек.

744: Так, смотрим презентацию.

745: Звука нету, мы вас не слышим.

746: А, извините.

747: Сначала расскажу про библиотеки, которые мы использовали, помимо базовых, которых нам дали. 1, это итертулс. Это модуль для работы с итерируемыми объектами. Мы использовали его для нахождения всех вариаций путей между точка.

748: И использовали библиотеку нетворкс для нахождения кратчайшего пути между 2 отдельно взятыми точками.

749: Сам алгоритм выполнения задания сначала мы создаём граф с указанием смежных вершин и расстояние между ними.

750: Дальше задаём 4 списка с разной последовательностью точек, которые мы должны проехать.

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

752: Поэтому путём перестановок и сравнения полученного полученной длины маршрута с предыдущей мы находим 4 кратчайших дистанции для каждой последовательности точек, в которых стоят флаги.

753: Далее ветвлением мы проверяем, сколько из 4 допустимых маршрутов могут быть выполнены в зависимости от начального угла разворота робота. Если таких маршрутов несколько, то мы берём

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

755: Спасибо за внимание, спасибо команде, поники из школы 8 20 89 и прошу жюри задать вопрос.

756: Давайте я задам вопрос. Получается у вас, я так понял, все пути, которые, в принципе, есть, вы их прописали как бы вручную или нет? Просто там условие было на последнем слайде. Вы имеете ввиду цикл движения? Нет, там прописан.

757: Только условия для перекрёстков, так как робот движется почти по всем прямым по последовательным точкам, где индекс которых отличается на 1.

758: Почти все дороги можно записать 1 2 строчками, просто условием, что если индекс следующей точки на больше, на 1 либо меньше на 1, то он едет вперёд и нужно было прописать только для перекрёстков условия.

759: Немного непонятно. То есть у вас все? У вас же есть граф со связанными, где прописаны все связи для перекрёстков. Для чего тогда это условие?

760: Условия нужны для определения, какое именно действие совершит робот всего у него есть 3 всего, у него есть 3 паттерна движения за 1 итерацию цикла это проезд вперёд, проезд вперёд и поворот направо либо проезд вперёд и поворот налево.

761: И условия нужны для того, чтобы по определению индекса точки, которая будет через, которая должна быть пройдена через

762: Точки, которая должна быть пройдена в будущем по найденному маршруту, чтобы робот мог определить разворот, какой он должен сделать.

763: Хорошо, спасибо. Есть ещё вопросы?

764: Да, есть меня слышно, да, наконец то. То есть у вас получается, движение по кругу вообще никак не реализовано, реализовано.

765: Просто вы же сказали, что с определяет только движение прямо или прямо и налево, прямо и направо. Нет, ну я забыл добавить, ну, движение погруженности в это действие входит так, как там прописано в базовой библиотеке, то, что робот

766: Поворачивается ещё дополнительно на определённое количество градусов, но условия для круга тоже прописаны. Хорошо? Понял, да.

767: Спасибо команде паяльники. Далее приглашается команда акселераторы.

768: Из одинцовского 10 лицея.

769: Так, команда акселератора. У вас получилось подключиться?

770: Нет.

771: У вас есть возможность с другого компьютера. Пытались уже, а вы можете запустить? Да, можем запустить.

772: Сейчас, сейчас запустим ваш код. Так, от робота номер 4. Предыдущая команда. Отключи.

773: Так, сейчас подключимся, пустим ваш.

774: У команды акселераторы стартовая точка 7.

775: Стартовый угол 180.

776: И флаги 2, 8, 10, 15.

777: Сейчас.