Inteligentní plánování cest s umělou inteligencí

Plánování cest, ať už pro obchodní cesty nebo dovolenou, může být náročné. Velké jazykové modely (LLM) se zdají být ideálním nástrojem pro tento úkol díky své schopnosti iterativně interagovat pomocí přirozeného jazyka, provádět běžný úsudek, shromažďovat informace a využívat další nástroje. Nicméně, nedávné studie ukázaly, že špičkové LLMy bojují s komplexním logistickým a matematickým uvažováním a problémy s více omezeními, jako je právě plánování cest. Úspěšnost dosahovala pouhých 4 %.

Výzkumný tým z MIT a MIT-IBM Watson AI Lab proto přeformuloval problém. „Věříme, že mnoho těchto plánovacích problémů je v podstatě kombinatorickým optimalizačním problémem,“ říká Chuchu Fan, docentka na MIT Department of Aeronautics and Astronautics (AeroAstro) a Laboratory for Information and Decision Systems (LIDS). Její tým aplikuje strojové učení, teorii řízení a formální metody k vývoji bezpečných a ověřitelných řídicích systémů pro robotiku, autonomní systémy, regulátory a interakci člověk-stroj.

Tým vytvořil uživatelsky přívětivý rámec, který funguje jako AI cestovní agent a pomáhá vytvářet realistické, logické a kompletní cestovní plány. K tomu kombinují běžné LLMy s algoritmy a řešičem uspokojitelnosti (solver). Řešiče jsou matematické nástroje, které rigorózně ověřují, zda lze kritéria splnit a jak, ale vyžadují komplexní počítačové programování. To z nich dělá přirozené spojence LLMů pro problémy, kde uživatelé chtějí pomoc s plánováním včas, bez nutnosti programovacích znalostí nebo výzkumu cestovních možností.

Pokud nelze splnit omezení uživatele, nová technika dokáže identifikovat a vysvětlit, kde je problém, a navrhnout uživateli alternativní řešení. Uživatel se pak může rozhodnout, zda je přijme, zamítne nebo upraví, dokud se nenajde platný plán (pokud existuje).

„Různé složitosti plánování cest se každý z nás bude muset vypořádat. Existují různé potřeby, požadavky, omezení a informace ze skutečného světa, které můžete shromáždit,“ říká Fan. „Naším záměrem není požádat LLMy, aby navrhly cestovní plán. Místo toho LLM zde funguje jako překladatel, který přeloží přirozeně jazykový popis problému do problému, který může řešič zpracovat, a poté ho poskytne uživateli,“ dodává Fan.

Spoluautoři článku o této práci s Fan jsou Yang Zhang z MIT-IBM Watson AI Lab, postgraduální student AeroAstro Yilun Hao a postgraduální student Yongchao Chen z MIT LIDS a Harvard University. Tato práce byla nedávno představena na konferenci Společnosti pro počítačovou lingvistiku (Association for Computational Linguistics).

Rozklad řešiče

Matematika má tendenci být doménově specifická. Například v zpracování přirozeného jazyka LLMy provádějí regrese k předpovědi dalšího tokenu (tj. slova) v sérii, aby analyzovaly nebo vytvořily dokument. To funguje dobře pro zobecnění rozmanitých lidských vstupů. Samotné LLMy však nebudou fungovat pro aplikace formálního ověřování, jako je letectví nebo kybernetická bezpečnost, kde je nutné, aby spojení obvodů a úlohy s omezeními byly úplné a prokázané, jinak mohou proklouznout mezery a zranitelnosti a způsobit kritické problémy s bezpečností. Zde vynikají řešiče, ale potřebují pevně formátované vstupy a bojují s neuspokojivými dotazy. Hybridní technika však nabízí možnost vyvíjet řešení komplexních problémů, jako je plánování cest, způsobem, který je intuitivní pro běžné lidi.

„Řešič je zde skutečně klíčový, protože když vyvíjíme tyto algoritmy, přesně víme, jak se problém řeší jako optimalizační problém,“ říká Fan. Konkrétně výzkumná skupina použila řešič zvaný satisfiability modulo theories (SMT), který určuje, zda lze formuli uspokojit. „S tímto konkrétním řešičem se nejedná jen o optimalizaci. Provádí úsudek nad mnoha různými algoritmy, aby pochopil, zda je plánovací problém řešitelný či nikoliv. To je v plánování cest docela významná věc. Není to tradiční matematický optimalizační problém, protože lidé přicházejí se všemi těmito limity, omezeními a restrikcemi,“ poznamenává Fan.

Překlad v akci

„Cestovní agent“ pracuje ve čtyřech krocích, které se podle potřeby opakují. Vědci použili jako LLM metody GPT-4, Claude-3 nebo Mistral-Large. Nejprve LLM analyzuje výzvu uživatele k cestovnímu plánu na plánovací kroky a zaznamenává preference týkající se rozpočtu, hotelů, dopravy, destinací, atrakcí, restaurací a délky cesty ve dnech, stejně jako další požadavky uživatele. Tyto kroky se poté převedou na spustitelný kód Pythonu (s anotací přirozeného jazyka pro každé z omezení), který volá rozhraní API, jako je CitySearch, FlightSearch atd., ke shromažďování dat a řešič SMT k zahájení provádění kroků uvedených v problému uspokojení omezení.

Pokud lze nalézt správné a úplné řešení, řešič odešle výsledek do LLM, který poté poskytne uživateli soudržný itinerář. Pokud nelze splnit jedno nebo více omezení, rámec začne hledat alternativu. Řešič vygeneruje kód, který identifikuje konfliktní omezení (s odpovídající anotací), které LLM poté poskytne uživateli s možným řešením. Uživatel se pak může rozhodnout, jak postupovat, dokud se nedosáhne řešení (nebo maximálního počtu iterací).

Zobecnitelné a robustní plánování

Vědci ověřili svou metodu pomocí výše zmíněných LLM proti dalším základním metodám: samotný GPT-4, samotný OpenAI o1-preview, GPT-4 s nástrojem pro shromažďování informací a vyhledávací algoritmus, který optimalizuje celkové náklady. Pomocí datové sady TravelPlanner, která zahrnuje data pro proveditelné plány, tým zkoumal několik metrik výkonu: jak často metoda mohla doručit řešení, zda řešení splňovala kritéria zdravého rozumu, jako je nenavštěvování dvou měst v jeden den, schopnost metody splnit jedno nebo více omezení a konečná úspěšnost, která ukazuje, že dokáže splnit všechna omezení. Nová technika obecně dosáhla úspěšnosti přes 90 %, ve srovnání s 10 % nebo méně u základních metod. Tým také zkoumal přidání JSON reprezentace v kroku dotazu, což metodě dále usnadnilo poskytování řešení s úspěšností 84,4–98,9 %.

Tým MIT-IBM dal své metodě další výzvy. Zkoumali, jak důležitá je každá součást jejich řešení – například odstranění lidské zpětné vazby nebo řešiče – a jak to ovlivnilo úpravy plánu u neuspokojivých dotazů do 10 nebo 20 iterací pomocí nové datové sady, kterou vytvořili, nazvané UnsatChristmas, která zahrnuje neviditelná omezení, a upravené verze TravelPlanner. V průměru rámec skupiny MIT-IBM dosáhl 78,6 a 85% úspěšnosti, což stoupá na 81,6 a 91,7 % s dalšími koly úprav plánu. Vědci analyzovali, jak dobře se vypořádala s novými, neviditelnými omezeními a parafrázovanými výzvami kroků dotazu a kódu. V obou případech si vedla velmi dobře, zejména s 86,7% úspěšností u testu parafrázování.

Nakonec vědci z MIT-IBM aplikovali svůj rámec na další oblasti s úkoly jako výběr bloků, přidělování úkolů, problém obchodního cestujícího a sklad. Zde metoda musí vybrat očíslované, barevné bloky a maximalizovat své skóre; optimalizovat přidělování úkolů robotů pro různé scénáře; plánovat cesty s minimalizací ujeté vzdálenosti; a dokončení a optimalizaci úkolů robotů.

„Myslím si, že se jedná o velmi silný a inovativní rámec, který může lidem ušetřit spoustu času, a také je to velmi nová kombinace LLM a řešiče,“ říká Hao.

Tato práce byla částečně financována Úřadem námořního výzkumu a MIT-IBM Watson AI Lab.