Константин Сергеевич Яковлев, к.ф.-м.н., ведущий научный сотрудник ФИЦ ИУ РАН и AIRI, доцент ВШЭ, МФТИ, СПбГУ

Робототехника стремительно развивается и активно трансформирует наш мир. Логистика, автоматизированные склады, поисковые и спасательные миссии — далеко не полный список областей, где уже активно применяются роботы. Для того, чтобы их внедрение давало нужный эффект, они должны быть максимально интеллектуальными. Но что означает «интеллектуальный робот»? Как добиться от него интеллектуальности (и всегда ли это нужно)? Какие классические и современные подходы используются сегодня для построения систем управления роботами? Эти вопросы мы и обсудим в рамках предстоящего доклада-дискуссии.

Николай Константинович Верещагин
– Профессор мехмата МГУ, ФКН ВШЭ и ШАД Яндекса.
– Лауреат премии имени А.Н. Колмогорова 2024 года РАН за цикл работ о колмогоровской сложности.
– Член Европейской академии по секции Информатика.

Дан конечный набор многоугольных плиток и некоторые локальные правила укладки этих плиток на плоскость. Рассмотрим замощения плоскости этими плитками, соблюдающие эти локальные правила. Обычно самый простой способ уложить плитки состоит в том, что плитки укладываются в какую-то простую ограниченную фигуру, сдвигами которой можно замостить уже всю плоскость. Такие замощения называются периодическими. Но бывают наборы плиток, не имеющих периодических замощений. Такие наборы называются непериодическими. Наиболее известные из них — наборы Пенроуза и Бергера – Робинсона.

Главный способ построения непериодических наборов - это так называемые подстановки. Подстановкой называется любой способ разрезания каждой из исходных плиток на многоугольники, каждый из которых подобен одной из исходных плиток с некоторым фиксированным коэффициентом подобия, меньшим 1. Каждой подстановке s, удовлетворяющей некоторому условию, сопоставляется семейство F_s замощений плоскости, состоящее только из непериодических замощений. Таким образом можно определить сотни интересных семейств непериодических замощений. Теорема Гудман Штрауса утверждает, что «почти для любой» подстановки s задаваемое семейство F_s может быть задано локальными правилами. Применяя эту теорему можно получить сотни интересных непериодических наборов

Недостатком теоремы Гудман-Штрауса является расплывчатость формулировки: слова «почти для любой» не уточняются в формулировке теоремы, а выясняются только в ходе ее доказательства. При этом доказательство очень сложное, содержит 38 страниц и мне не удалось найти человека, утверждавшего, что он понял его или хотя бы точную формулировку теоремы. Недавно мне удалось найти некоторые достаточно, видимо другие, общие условия на подстановку s, гарантирующие, что семейство F_s может быть задано локальными правилами. Обо этом и будет рассказано в докладе.