Турагенты помогают организовать всю логистику — транспорт, проживание, питание и жильё — для бизнесменов, отдыхающих и всех остальных. Для тех, кто хочет самостоятельно организовать своё путешествие, большие языковые модели (LLM) кажутся подходящим инструментом благодаря их способности итеративно взаимодействовать с использованием естественного языка, рассуждать логически, собирать информацию и вызывать другие инструменты для решения поставленной задачи. Однако недавние исследования показали, что современные LLM с трудом справляются со сложными логистическими и математическими задачами, а также с проблемами, имеющими множество ограничений, например, при планировании поездок, где они находят жизнеспособные решения лишь в 4% случаев или меньше, даже с дополнительными инструментами и интерфейсами прикладного программирования (API).
Исследование из MIT и MIT-IBM Watson AI Lab
Исследовательская группа из MIT и лаборатории MIT-IBM Watson AI Lab переосмыслила проблему, чтобы выяснить, можно ли повысить успешность решений LLM для сложных задач. «Мы считаем, что многие из этих задач планирования по своей природе являются задачами комбинаторной оптимизации», — говорит Чучу Фань, доцент кафедры аэронавтики и астронавтики MIT (AeroAstro) и Лаборатории информационных и управляющих систем (LIDS). Её команда применяет машинное обучение, теорию управления и формальные методы для разработки безопасных и проверяемых систем управления для робототехники, автономных систем, контроллеров и взаимодействия человека и машины.
Создание пользовательской системы
Отмечая возможность переноса своей работы для планирования путешествий, группа стремилась создать удобную для пользователя систему, которая может действовать как ИИ-брокер по путешествиям и помогать разрабатывать реалистичные, логичные и полные планы путешествий. Для этого исследователи объединили обычные LLM с алгоритмами и полным решателем выполнимости. Решатели — это математические инструменты, которые строго проверяют, можно ли выполнить критерии и как, но для их использования требуется сложное компьютерное программирование. Это делает их естественными компаньонами для LLM в таких задачах, где пользователи хотят получить помощь в планировании в кратчайшие сроки, без необходимости знания программирования или изучения вариантов путешествий.
Если ограничение пользователя не может быть выполнено, новая методика может определить и сформулировать, в чём заключается проблема, и предложить альтернативные меры пользователю, который затем может принять, отклонить или изменить их, пока не будет сформулирован действительный план, если таковой существует.
«Разные сложности планирования путешествий — это то, с чем каждому придётся столкнуться в какой-то момент. Есть разные потребности, требования, ограничения и реальная информация, которую можно собрать», — говорит Фань. «Наша идея состоит не в том, чтобы просить LLM предложить план путешествия. Вместо этого LLM здесь выступает в роли переводчика, который переводит это описание проблемы на естественном языке в задачу, с которой может справиться решатель».
Соавторами статьи о работе с Фань являются Ян Чжан из лаборатории MIT-IBM Watson AI Lab, аспирант AeroAstro Илюнь Хао и аспирант Yongchao Chen из MIT LIDS и Гарвардского университета. Эта работа была недавно представлена на конференции Американской ассоциации по вычислительной лингвистике.
Разбиение решателя
Математика, как правило, специфична для предметной области. Например, в обработке естественного языка LLM выполняют регрессию для прогнозирования следующего токена, известного как «слово», в серии для анализа или создания документа. Это хорошо работает для обобщения различных входных данных человека. Однако LLM сами по себе не подходят для приложений формальной верификации, например, в аэрокосмической отрасли или кибербезопасности, где необходимо полное и доказанное соединение схем и выполнение задач по ограничению, иначе могут появиться лазейки и уязвимости, которые могут привести к серьёзным проблемам с безопасностью. Здесь решатели преуспевают, но им нужны входные данные с фиксированным форматированием, и они борются с невыполнимыми запросами. Гибридная методика, однако, даёт возможность разрабатывать решения для сложных задач, таких как планирование поездок, интуитивно понятным для обычных людей.
«Решатель действительно является ключевым моментом здесь, потому что, когда мы разрабатываем эти алгоритмы, мы точно знаем, как решается проблема оптимизации», — говорит Фань. Исследовательская группа использовала решатель под названием «удовлетворимость по модулю теорий» (SMT), который определяет, может ли формула быть удовлетворена. «С помощью этого конкретного решателя мы не просто занимаемся оптимизацией. Мы рассуждаем над множеством различных алгоритмов, чтобы понять, возможно ли решить задачу планирования или нет. Это довольно важный момент в планировании путешествий. Это не очень традиционная математическая задача оптимизации, потому что люди придумывают всевозможные ограничения, ограничения, ограничения», — отмечает Фань.
Перевод в действии
«Турагент» работает в четыре шага, которые можно повторять по мере необходимости. Исследователи использовали GPT-4, Claude-3 или Mistral-Large в качестве LLM метода. Сначала LLM анализирует запрос пользователя о планировании путешествия, отмечая предпочтения по бюджету, отелям, транспорту, направлениям, достопримечательностям, ресторанам и продолжительности поездки в днях, а также любые другие предписания пользователя. Затем эти шаги преобразуются в исполняемый код Python (с аннотацией на естественном языке для каждого из ограничений), который вызывает API, такие как CitySearch, FlightSearch и т. д., для сбора данных, а решатель SMT начинает выполнять шаги, изложенные в задаче удовлетворения ограничений. Если можно найти обоснованное и полное решение, решатель выводит результат в LLM, который затем предоставляет согласованный маршрут пользователю.
Если одно или несколько ограничений не могут быть выполнены, система начинает искать альтернативу. Решатель выводит код, идентифицирующий конфликтующие ограничения (с соответствующей аннотацией), который LLM затем предоставляет пользователю с потенциальным средством устранения. Пользователь может решить, как действовать, пока не будет достигнуто решение (или максимальное количество итераций).
Обобщаемое и надёжное планирование
Исследователи протестировали свой метод, используя вышеупомянутые LLM, против других базовых показателей: GPT-4 сам по себе, OpenAI o1-preview сам по себе, GPT-4 с инструментом для сбора информации и алгоритм поиска, который оптимизирует общую стоимость. Используя набор данных TravelPlanner, который включает данные для жизнеспособных планов, команда изучила несколько показателей производительности: как часто метод может предоставить решение, соответствует ли решение критериям здравого смысла, таким как невозможность посещения двух городов за один день, способность метода соответствовать одному или нескольким ограничениям и окончательный процент прохождения, указывающий на то, что он может соответствовать всем ограничениям.
Новый метод в целом достиг более 90% процента прохождения по сравнению с 10% или ниже для базовых показателей. Команда также изучила возможность добавления представления JSON на этапе запроса, что ещё больше упростило для метода предоставление решений с процентом прохождения от 84,4% до 98,9%.
Команда MIT-IBM поставила перед своим методом дополнительные задачи. Они рассмотрели, насколько важен каждый компонент их решения, например, удаление обратной связи от человека или решателя, и как это влияет на корректировку плана для невыполнимых запросов в течение 10 или 20 итераций с использованием нового набора данных, который они создали под названием UnsatChristmas, который включает невидимые ограничения, и модифицированную версию TravelPlanner. В среднем группа MIT-IBM достигла 78,6% и 85% успеха, который возрастает до 81,6% и 91,7% при дополнительных раундах модификации плана.
Исследователи проанализировали, насколько хорошо он справляется с новыми, невидимыми ограничениями и перефразированными запросами на этапе запроса и пошаговыми подсказками кода. В обоих случаях он показал себя очень хорошо, особенно с 86,7% процентом прохождения для испытания по перефразированию.
Наконец, исследователи MIT-IBM применили свою систему к другим областям с такими задачами, как подбор блоков, распределение задач, задача коммивояжёра и складское хозяйство. Здесь метод должен выбрать пронумерованные, цветные блоки и максимизировать свой счёт; оптимизировать назначение задач робота для различных сценариев; спланировать поездки, минимизируя пройденное расстояние; и оптимизировать выполнение и оптимизацию задач робота.
«Я думаю, что это очень сильная и инновационная система, которая может сэкономить много времени для людей, и, кроме того, это очень новая комбинация LLM и решателя», — говорит Хао.
Эта работа была частично профинансирована Управлением военно-морских исследований и лабораторией MIT-IBM Watson AI Lab.