Мы представляем метод решения задач планирования с использованием линейных моделей мышления для интерпретации качественных целей и алгоритмов оптимизации для учета количественных ограничений.
Многие реальные задачи планирования включают в себя как более жесткие «количественные» ограничения (например, бюджет или требования к графику), так и более мягкие «качественные» цели (например, предпочтения пользователей, выраженные на естественном языке). Рассмотрим человека, планирующего недельный отпуск. Как правило, такое планирование будет подчиняться различным четко измеримым ограничениям, таким как бюджет, логистика поездки и посещение достопримечательностей только в часы их работы, а также ряду ограничений, основанных на личных интересах и предпочтениях, которые нелегко поддаются количественной оценке.
Большие языковые модели (БЛМ) обучаются на огромных массивах данных и вобрали в себя впечатляющее количество знаний о мире, часто включая понимание типичных человеческих предпочтений. Таким образом, они, как правило, хорошо учитывают не столь поддающиеся количественной оценке аспекты планирования поездок, такие как идеальное время для посещения живописного места или подходит ли ресторан для детей. Однако они менее надежны в обработке количественных логистических ограничений, которые могут потребовать подробной и актуальной информации из реального мира (например, цены на автобусы, расписания поездов и т. д.) или сложных взаимодействующих требований (например, минимизация поездок в течение нескольких дней). В результате планы, сгенерированные БЛМ, иногда могут включать непрактичные элементы, такие как посещение музея, который будет закрыт к моменту вашей поездки.
Недавно мы представили функцию поиска с использованием ИИ, которая предлагает маршруты по дням в ответ на запросы по планированию поездок. В этом блоге мы описываем некоторые этапы работы по преодолению одной из ключевых проблем при запуске этой функции: обеспечение практичности и осуществимости предлагаемых маршрутов. Наше решение использует гибридную систему, которая применяет модель логистической регрессии (LLM) для предложения первоначального плана в сочетании с алгоритмом, который совместно оптимизирует сходство с планом LLM и реальными факторами, такими как время в пути и часы работы. Такой подход объединяет способность LLM обрабатывать нечеткие требования с алгоритмической точностью, необходимой для соблюдения жестких логистических ограничений.
Как это работает
Получив пользовательский запрос, мы сначала передаем его в LLM (Low Linear Model), которая в нашей системе представляет собой версию наших последних моделей Gemini. LLM предлагает первоначальный план поездки, состоящий из списка мероприятий с соответствующими деталями, такими как рекомендуемая продолжительность и уровень важности для запроса пользователя. Первоначальный план хорошо адаптирован к интересам пользователя, но может иметь проблемы с осуществимостью, например, предлагать заведение, которое недавно закрылось.
Схема нашей гибридной системы LLM и оптимизации. Система LLM предлагает первоначальный план, а затем мы проводим оптимизацию с учетом реальных ограничений для получения окончательного маршрута.
Для решения проблем с осуществимостью мы добавляем несколько компонентов к модели LLM. Начинаем с привязки первоначального маршрута к актуальным данным о часах работы и времени в пути. Параллельно мы также используем поисковые системы для получения дополнительных релевантных мероприятий, которые могут служить потенциальными альтернативами в случае необходимости изменения предложенного моделью LLM плана. Затем первоначальный план, альтернативные мероприятия и данные о привязке передаются в алгоритм оптимизации для поиска плана поездки, аналогичного первоначальному, но также обеспечивающего осуществимость.
Алгоритм состоит из двух основных этапов. Первый этап работает на уровне одного дня в рамках поездки. Для каждого подмножества мероприятий (до разумного максимального размера) мы определяем оптимальное расписание этих мероприятий на день. Затем мы присваиваем ему оценку качества, определяемую в первую очередь на основе сходства с исходным планом и осуществимости расписания с учетом ограничений по времени работы и времени в пути (например, совершенно невыполнимое расписание получит оценку в ноль). Поскольку количество мероприятий в течение дня невелико, мы обнаружили, что оценки можно вычислить путем исчерпывающего поиска с достаточно оптимизированной реализацией на основе динамического программирования.
На втором этапе мы ищем общий маршрут (т.е. наборы действий для каждого дня), который максимизирует суммарный балл за дни, при условии, что действия двух дней не могут перекрываться. Это взвешенный вариант задачи упаковки множеств, которая, как известно, является NP-полной и, следовательно, вычислительно неразрешимой. Однако, учитывая, что наша целевая функция оптимизации по своей сути стремится оставаться близкой к исходному маршруту, мы обнаружили, что эвристические методы локального поиска оказались эффективными. Начиная с исходного маршрута, мы вносим локальные корректировки, обменивая действия между парами дней до тех пор, пока это увеличивает суммарный балл. Эта процедура повторяется до сходимости, в результате чего получается окончательный маршрут.
Иллюстрация оптимизации маршрута с учетом локальных корректировок. Первоначальный маршрут включает посещение научного музея после его закрытия. Алгоритм переносит его на первый день, в более раннее время. Это оставляет время для переноса утренней прогулки с третьего дня на второй, с географически более близкими мероприятиями, в результате чего формируется окончательный маршрут.
Примеры
Следующий запрос иллюстрирует, как детальное понимание, предоставляемое LLM-системами, может лучше удовлетворять потребности пользователя, чем традиционная система поиска информации.
Запрос: «Помогите мне спланировать поездку в Нью-Йорк на выходные с посещением множества малоизвестных музеев и избеганием больших скоплений людей».
Наша система формирует маршрут, соответствующий запросу пользователя, предлагая такие музеи, как Музей движущегося изображения и Нью-Йоркский музей транспорта. Если мы уберем предложение LLM и будем полагаться только на результаты поиска, то полученный маршрут будет включать в себя некоторые менее известные музеи, а также Метрополитен-музей и Музей Гуггенхайма — известные музеи, прямо противоречащие запросу пользователя.
Маршрут, созданный гибридной системой ( слева ), включает исключительно малоизвестные музеи по запросу пользователя. Опираясь исключительно на результаты поиска, в план поездки включаются некоторые известные музеи ( справа ).
С другой стороны, следующий запрос демонстрирует случай, когда гибридная система исправляет ошибку в исходном маршруте, предложенном LLM:
Запрос: «Спланируйте мне поездку в Сан-Франциско. Я хочу посетить художественные музеи и поехать куда-нибудь с панорамным видом на город».
В ходе тестирования LLM предложил ряд интересных достопримечательностей, таких как музей де Янг (в котором также есть смотровая башня) и культовая башня Койт. Однако маршрут распланировал мероприятия на один из дней неестественным образом, требуя от пользователя перемещения по городу. На этапе оптимизации мы смогли исправить это, получив логистически осуществимый план, сохраняющий первоначальный замысел.
Предложенный LLM маршрут ( слева ) включает в себя длительную поездку по городу в один из дней. После применения алгоритма оптимизации мы получаем более естественную группировку мероприятий ( справа ).
Дальнейшая работа
Помимо планирования поездок, навыки управления жизненным циклом могут применяться во многих других повседневных задачах, таких как организация мероприятий или планирование поручений. Для таких приложений крайне важно разработать системы, позволяющие навыкам управления жизненным циклом надежно ориентироваться в ограничениях реального мира. Наша работа по планированию поездок является частью более масштабных усилий по решению этой проблемы — следите за дальнейшими обновлениями в этой области.
Благодарности
Данная запись в блоге основана на работе, выполненной в сотрудничестве с Вэй Ченом, Лукасом Гусманом, Ширли Лоайзой Санчес и Вэйе Яо. Мы также благодарим Сриниваса Голлапуди, Костаса Коллиаса и Гокула Варадхана за полезные советы.
Источник: research.google
