Pull to refresh
21
0.1
Send message

Много-агентное планирование траекторий в децентрализованном режиме: эвристический поиск и обучение с подкреплением

Level of difficulty Medium
Reading time 17 min
Views 1.3K

Привет! Меня зовут Константин Яковлев, я научный работник и вот уже более 15 лет я занимаюсь методами планирования траектории. Когда речь идет о том, чтобы построить траекторию для одного агента, то задачу зачастую сводят к поиску пути на графе, а для этого в свою очередь обычно используют алгоритм A* или какие‑то из его многочисленных модификаций. Если же агентов много, они перемещаются в рабочем пространстве одновременно, то задача (внезапно) становится несколько более сложной и применить напрямую A* не получится. Вернее получится, но лишь для небольшого числа агентов (проклятье размерности, куда деваться). Тем не менее для централизованного случая, т. е. для случая, когда есть один (мощный) вычислитель, с которым связаны все агенты и который всё про всех знает, решить задачу много‑агентного планирования можно достаточно эффективно. Можно даже находить оптимальные решения для умеренного количества агентов за относительное приемлемое время (например, порядка 1 секунды на современном десктопном PC для 30–50 агентов).

Если же говорить о децентрализованном случае, т. е. о том случае, когда агентам необходимо действовать индивидуально (например, нет устойчивой связи с центральным контроллером), опираясь лишь на собственные (локальные) наблюдения и опыт, то с хорошими решениями задачи становится гораздо сложнее. Когда я говорю «хорошие решения», я имею в виду прежде всего такие алгоритмы, которые бы давали стройные теоретические гарантии в общем случае. Хотя бы гарантии того, что каждый агент дойдёт (за конечное время) до своей цели. Тем не менее, задача интересная и специалисты из индустрии и академии её пытаются решать.

В этом посте я расскажу о наших свежих наработках в этой области, а именно о гибридном методе, которые сочетает в себе принципы классического эвристического поиска (A*) и обучения с подкреплением (PPO). Метод получился неплохим, превосходящим многие современные аналоги по результатам экспериментов, а соответствующая статья была принята на The 38th AAAI Conference on Artificial Intelligence (пока доступен только препринт). Это одна из топовых академических конференций по искусственному интеллекту, которая в этом (2024) году проходила в Канаде (спойлер: я сам визу получить не успел, но моим коллегам и со‑авторам, кто имел ранее выданные Канадские визы, удалось принять личное участие и достойно представить нашу науку на мировом уровне).

Итак, поехали!
Total votes 25: ↑25 and ↓0 +25
Comments 5

Как эффективно самостоятельно изучать английский язык

Level of difficulty Easy
Reading time 8 min
Views 29K

Читатели Хабра, категорически вас приветствую! В этой статье я хочу поделиться с вами моделью эффективного изучения английского языка, которую я постарался сформировать исходя из своего n-летнего опыта его изучения.

Расскажу вам насколько это актуально, с чего начать, какие ресурсы и приемы использовать и как эффективно достичь результата.

Читать далее
Total votes 25: ↑24 and ↓1 +23
Comments 27

Книги, которые нас выбирают

Level of difficulty Easy
Reading time 6 min
Views 15K

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

Я не планировал продолжать эту тему, но сейчас вижу, что кое в чем, статью надо дополнить. Это дополнение не будет повторять или расширять статью очередными мыслями и наблюдениями; все это в ней уже есть и добавить мне нечего. Просто, читая комментарии, я понял, что об одной детали я упомянул, но толком не рассказал. Из‑за чего у части комментаторов возникли сомнения в сегодняшней ценности книг, доступных мне в то время, когда я начинал карьеру программиста. Мне кажется, это не очень справедливо и хотя я, бесспорно, не объективен, но, тем не менее, решил немного об этом рассказать.

Я расскажу о тех книгах, что были мне доступны в 1987–1993 гг., т. е. тогда, когда я совмещал работу инженера с программированием. Конечно, я упомяну только те книги, что мне действительно помогли; полный список литературы слишком обширен и упоминание их всех больше походило бы библиотечный каталог, чего я делать не намерен. Условно эти книги можно отнести к одной из нижеследующих категорий. Итак — вот мой «золотой фонд».

Читать далее
Total votes 34: ↑34 and ↓0 +34
Comments 12

Людям важно внимание. История хоторнского эксперимента

Level of difficulty Easy
Reading time 2 min
Views 7.7K

Как проект повышения производительности труда на фабрике навсегда изменил наши представления о «рабочих» и «человеческих» отношениях

Читать далее
Total votes 35: ↑25 and ↓10 +15
Comments 8

Как распаковать айтишника и настроить цикл управления знаниями

Reading time 10 min
Views 5.5K

О преимуществах управления знаниями уже много написано, но вот выстраивание этого процесса — настоящий вызов...

Привет, Хабр! Меня зовут Лена, я архитектор продуктовых знаний. В этом тексте я сосредоточусь на тиражировании знаний и расскажу, как их эффективно «перекладывать» из голов экспертов. Также разберу реальный кейс Selectel — технический курс по сетям для всех сотрудников компании. Подробности под катом!
Читать дальше →
Total votes 33: ↑32 and ↓1 +31
Comments 4

Как калькуляторы вычисляют синус?

Level of difficulty Easy
Reading time 3 min
Views 53K

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

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

Читать далее
Total votes 98: ↑96 and ↓2 +94
Comments 52

Настоящее предназначение OpenAI SORA: как и зачем симулировать «Матрицу» для ChatGPT

Level of difficulty Medium
Reading time 41 min
Views 81K

Ну что, уже успели прочитать восхищения небывалым качеством видео от нейросетки SORA у всех блогеров и новостных изданий? А теперь мы вам расскажем то, о чем не написал никто: чего на самом деле пытается добиться OpenAI с помощью этой модели, как связана генерация видео с самоездящими машинами и AGI, а также при чем здесь культовая «Матрица».

Войти в симуляцию →
Total votes 289: ↑285 and ↓4 +281
Comments 120

ППА: Прямые Платежи Авторам

Level of difficulty Easy
Reading time 5 min
Views 2K

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

Читать далее
Total votes 19: ↑17 and ↓2 +15
Comments 38

Фуршет сентября

Level of difficulty Easy
Reading time 2 min
Views 5.5K

В недавней публикации (AMA) я рассказывал об основных функциональных изменениях, произошедших на Хабре за год. И в самом начале упомянул, что хочется попробовать возобновить ещё одну старую рубрику. Тогда я не стал называть её, но сделаю это сейчас: «Фуршет». Кому-то это о чём-то говорит? Даже если и нет, то заходите под кат, пятнично пообщаемся.

Читать далее
Total votes 60: ↑59 and ↓1 +58
Comments 106

Made at Intel

Level of difficulty Easy
Reading time 2 min
Views 8.1K

Всем привет. Спешу сообщить, что книжка «Made at Intel» увидела свет. Она по большей части состоит из обработки одноименного цикла статей на Хабре. Но, также, включает некоторое количество Bonus Tracks. 😉

Читать далее
Total votes 70: ↑68 and ↓2 +66
Comments 14

Неожиданное взаимодействие предсказания ветвлений и подсистем памяти

Reading time 10 min
Views 6.5K

Это 15-я статья в серии, посвящённая оптимизации подсистем памяти. Остальные доступны здесь (англ.).

В ней мы изучим взаимодействие механизма предсказания ветвлений с подсистемой памяти. В повествовании мы будем исходить из предположения, что вам знаком принцип предсказания ветвлений и работы подсистем памяти в современных процессорах.
Читать дальше →
Total votes 45: ↑43 and ↓2 +41
Comments 6

Поговорим об оптимизирующих компиляторах. Сказ восьмой: размотка циклов

Level of difficulty Medium
Reading time 12 min
Views 8.5K

Есть оптимизации, польза от которых очевидна всегда или почти всегда. Например, не делать лишнюю проверку лучше, чем делать. Не считать два раза одно и то же обычно лучше, чем считать (если только мы не упёрлись в нехватку регистров или имеем другие подобные проблемы на нижнем уровне). Вычислять выражения вне цикла выгоднее, чем в цикле. И так далее.

Но есть оптимизации, применение которых имеет как плюсы, так и минусы. Выиграв в одном месте, мы можем получить отрицательные эффекты в другом. Например, сэкономив на количестве проверок, мы можем раздуть общий объём кода и поломать микрооптимизации. Каноничным примером такой оптимизации, решение вопроса об использовании которой больше похоже на искусство, чем на науку, является размотка циклов (Loop Unrolling), о которой мы сегодня поговорим. В статье я попробую осветить как можно больше (хотя, наверное, и не все) соображения о том, почему эту оптимизацию может быть нужно или не нужно применять.

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

Читать далее
Total votes 55: ↑55 and ↓0 +55
Comments 6

Быстрое пополнение словарного запаса иностранного языка методом «Ознакомление-забывание-вспоминание»

Level of difficulty Medium
Reading time 6 min
Views 38K

Привет, Хабр!

В этой статье мы описываем полную методику быстрого пополнения словарного запаса при чтении неадаптированной литературы на иностранном языке. Статья будет интересна тем, кто владеет иностранным языком на уровне B2-С1 и столкнулся с необходимостью увеличить словарный запас на 5000-10000 новых слов за относительно короткий срок, напр. за полгода-год.

Методика опробована на английском языке и мобильном приложении Яндекс.Переводчик, однако может быть использована для любого другого языка и/или мобильного приложения.

С уважением,
Владимир

Читать далее
Total votes 13: ↑11 and ↓2 +9
Comments 35

Иероглифы — хаос или система? Разбираемся из чего они состоят, как работают и в чём их сила

Level of difficulty Easy
Reading time 15 min
Views 35K

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

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

Заходите, будет интересно
Total votes 150: ↑149 and ↓1 +148
Comments 183

Как я пережил смерть друга-кофаундера и переехал в лес ради стартапа

Reading time 6 min
Views 4.1K

На фото я, дизайнер, и мой друг Миша, сисадмин (и Мишина собака).

Эта статья как будто бы не по теме. Но у нас у всех есть друзья и близкие. Еще есть устремления, планы, цели и всякое такое.

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

Предыстория

Краснодарский край, Кавказское предгорье. Тут на северном склоне холма, в лесу, стоит небольшая пасека и Мишин дом в 20-30 метрах от неё. А еще пруды, банька, небольшая левада для лошадей — все это на участке, площадью чуть больше гектара.

До ближайшего города около 4 км, связь средней стабильности и полное отсутствие инфраструктуры. Дорога — лесная, электричество — солнечное, водоснабжение — дождевое с крыши + родник в 500 м.

Читать далее
Total votes 30: ↑25 and ↓5 +20
Comments 14

Как рисовать мозаики типа «эйнштейн»

Level of difficulty Medium
Reading time 39 min
Views 2.3K

На немецком «эйнштейн» звучит как «один камень». Один - «ein», камень - «Stain». Всем известно, что под этой фамилией жил один замечательный человек, и звали его ... Но в статье речь не о нём. Речь о математической задаче по поиску одной плитки, такой чтобы составленная из неё мозаика была непериодической. «Один камень» - это про плитку. В мозаике Пенроуза таких плиток две, а хотелось бы возможности использовать только одну. Не вдаваясь в детали можно сказать, что задача одной плитки в этом году (2023) решена. Получены интересные красивые мозаики.

Сначала была найдена «шляпа эйнштейна» - плитка, похожая на шляпу. Или, по моему скромному мнению, на рубашку. Из неё можно сделать отличную непериодическую мозаику. Только, для построения используются как сами шляпы, так и их зеркальные отражения. Считать ли это одной плиткой? Можно и не считать.

Дальше была найдена плитка «черепаха». Из неё тоже можно сложить непериодическую мозаику, по тем же самым правилам. Эти два вида плиток могут, плавно меняя форму, переходить друг в друга, меняя размер граней и при этом не меняя их направление. Ещё можно сложить непериодическую мозаику одновременно из этих двух плиток. Дальше больше. У такого плавного преобразования существует средний вариант, в котором длина граней одинакова.

Оказалось, такая мозаика, в которой есть одновременно и шляпы и черепахи, при обмене формой в момент, в котором длина граней становится одинаковой, составлена из плиток полностью одинаковой формы. То есть, существует ещё одна непериодическая мозаика, в которой плитка используется уже без своего зеркального отражения. Плитка, у которой грани модифицированы так, что она позволяет только непереодическое сложение названа «Spectre» (призрак). Задача решена, теперь уже точно.

Читать далее
Total votes 25: ↑25 and ↓0 +25
Comments 1

Книги, которые помогут прокачать писательские скилы

Reading time 4 min
Views 4.7K

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

Начать лучше с основополагающих вещей – книги «Я, редактор», где изложена суть современного подхода к подготовке интересных публикаций, а также объясняется смысл редакторской работы. Многие думают, что она связана лишь с правкой текстов, но это не так.

Читать далее
Total votes 30: ↑26 and ↓4 +22
Comments 21

Как я потратил 250 миллионов в деревне

Level of difficulty Easy
Reading time 9 min
Views 61K

Я получил экономическое образование, торговал на фондовой бирже, а 1 ноября 2009 года начал брать молоко, мясо в деревне и продавать в Москве. 2 года вставал в 4 утра, чтобы забрать продукты, а до 2-х ночи с женой варили компоты и пекли запеканки. Позже купил 20 Га в Тульской области у своего поставщика баранины. А в ковид окончательно перебрался жить на землю.

В статье рассказал, как построил сельскохозяйственное производство за 250 млн, как 5 раз перестраивал коровник, почему курятник нельзя отапливать коровником, как работают поилки для кур, как разместить поросят, чтобы свиноматка их не раздавила. А еще посчитал экономику коровы, свиньи 🐽 и бройлеров.

Читать далее
Total votes 236: ↑218 and ↓18 +200
Comments 176

Незаконченная история о море Дирака

Reading time 8 min
Views 12K

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

Читать далее
Total votes 53: ↑49 and ↓4 +45
Comments 11

Как мы строили ИТ-кампус, часть 1

Level of difficulty Easy
Reading time 9 min
Views 10K

Привет, я снова с вами, и сегодня вниманию почтенной публики представляется первая глава нового цикла. Он будет посвящен уникальному проекту, на который сейчас направлено 90% моих усилий. И еще — этот цикл будет сильно отличаться от предыдущего. Made at Intel был осмыслением прошедших событий спустя довольно продолжительное время. Здесь же мы имеем дело с живым проектом, где множество сложных решений приходится принимать в режиме реального времени. И порой очень трудно сказать, где ты попал, а где промахнулся. Наступить на грабли можно прямо сейчас, а по лбу тебе прилетит лишь спустя годы. Поэтому здесь будет гораздо больше «размышлений вслух» и дискуссионных вопросов. Кроме того, я проведу для вас небольшую экскурсию в мир госпроектов, который (к моему вящему удивлению) оказался совсем не таким скучным, как представлялся. Также любознательный читатель сможет почерпнуть некоторое количество деталей о нижегородском и российском айти‑ландшафте. И еще для меня это очень личная история. История поиска и в каком-то смысле перерождения. И надеюсь, она тоже покажется вам небезынтересной.

Итак...
Total votes 67: ↑65 and ↓2 +63
Comments 38

Information

Rating
2,368-th
Registered
Activity