Moduł 16 · Rozszerzenia

Wielokryterialność i kompozycja zadań

Weighted sum, lexicographic, ε-constraint, Pareto-front interaktywny, funkcje kosztu (jerk/clearance/manipulability), TAMP/PDDLStream/LGP.

TL;DR

Klasyczne planery optymalizują jeden koszt (długość ścieżki, czas, energia). W rzeczywistości chcemy łączyć kilka kryteriów:

krótka ścieżka (długość)
gładka trajektoria (jerk)
daleko od przeszkód (clearance)
poza singularnościami (manipulability)
mała energia (sum of squared torques)
szybka (czas)

Multi-objective optimization: jak te kryteria łączyć? 4 standardowe podejścia + meta-poziom planowania sekwencji zadań (TAMP).

Pareto-front i weighted sum

Dwa kryteria $f_1, f_2$ . Rozwiązanie $x$ dominuje $y$ gdy $f_1(x) \leq f_1(y), f_2(x) \leq f_2(y)$ i co najmniej jedna nierówność jest ścisła. Rozwiązanie jest Pareto-optimal jeśli żadne inne go nie dominuje.

Pareto-front = zbiór wszystkich Pareto-optimal punktów w przestrzeni $(f_1, f_2)$ . Daje pełen trade-off.

1. Weighted sum

\min_x \lambda_1 f_1(x) + \lambda_2 f_2(x), \quad \lambda_i \geq 0, \sum \lambda_i = 1

Pojedyncza optymalizacja. Każde $\lambda$ daje jeden punkt na Pareto-front (jeśli front jest convex). Zmienna $\lambda$ generuje cały front.

Ograniczenie: dla NIE-convex Pareto-front, weighted sum nie wszystkie punkty osiąga.

2. Lexicographic

Priorytetuj kryteria. Najpierw minimalizuj $f_1$ bez ograniczeń. Wśród optimów $f_1$ , minimalizuj $f_2$ . Itd.

Stosowane gdy mamy hierarchię: bezpieczeństwo (najwyższe), potem długość, potem energia.

3. ε-constraint

\min_x f_1(x) \quad \text{s.t.} \; f_2(x) \leq \varepsilon

Zachowuj jedno kryterium jako twardy constraint, optymalizuj drugie. Zmienne $\varepsilon$ daje punkty na froncie, w tym dla NIE-convex.

4. Goal programming

Każde kryterium ma target. Minimalizuj sumę odchyleń od targets. Tłumi extreme wartości.

Pareto-front: jerk vs clearance (2 optimal / 60 total)

λ (waga jerk)0.50

Optimum przy λ = 0.50: jerk = 0.132, clearance = 0.800

dominated trajectoryPareto-optimalweighted-sum optimumPareto frontiso-cost dla bieżącej λ

Co zauważyć: Pareto-front = zbiór rozwiązań NIE-DOMINOWANYCH — żadne inne nie jest jednocześnie lepsze w obu kryteriach. Weighted sum z różnymi λ wybiera różne punkty na froncie: λ→0 maksymalizuje clearance (ignoruje jerk), λ→1 minimalizuje jerk (ignoruje clearance). λ=0.5 to balans. Pomarańczowa przerywana to iso-koszt — wszystkie punkty na niej mają ten sam koszt ważony. Tangentne do Pareto-front w punkcie optimum.

Pułapka weighted-sum: front non-convex

Weighted-sum scalarization wygląda na ogólną metodę, ale ma fundamentalną wadę: znajduje tylko punkty na convex hull frontu Pareto. Jeśli front zawiera wklęsłość (typowe dla problemów ze sprzecznymi ograniczeniami), to punkty w środku wklęsłości nigdy nie zostaną znalezione, nawet przy pełnym przemiataniu $\lambda \in [0,1]$ . Lekarstwo: ε-constraint method lub Chebyshev scalarization.

Non-convex Pareto-front — weighted-sum vs ε-constraint

Co pokazuje demo: (1) Pomarańczowe punkty to Pareto-optimal ale w wklęsłej części frontu — żadna wartość

\lambda \in [0,1]

nie znajdzie ich poprzez weighted-sum (iso-cost line przesuwa się równolegle, dotyka frontu tylko w punktach na convex hull). (2) ε-constraint na osi

f_2

może zlokalizować każdy Pareto-punkt — wystarczy odpowiednie

\varepsilon

. Przesuń ε na wartość odpowiadającą wklęsłemu punktowi i obserwuj że WS nadal nie tam trafia. (3) Dlatego w realnych problemach wielokryterialnych z non-convex frontami używa się: ε-constraint, NSGA-II, lub Chebyshev scalarization.

Dlaczego weighted-sum nie wystarcza

\min_\xi\, \lambda\,f_1(\xi) + (1-\lambda)\,f_2(\xi)

Geometrycznie: poziomice tej funkcji to linie proste o nachyleniu $-\lambda/(1-\lambda)$ . Minimum to punkt frontu styczny do najniższej takiej linii. Linia może być styczna tylko do wypukłej powłokifrontu — wklęsłości pozostają poza zasięgiem. Patrz Boyd & Vandenberghe, "Convex Optimization", rozdział 4.7.5.

ε-constraint method

\min_\xi\, f_1(\xi) \quad \text{s.t.}\quad f_2(\xi) \le \varepsilon

Iterując po $\varepsilon$ trafiamy w każdy Pareto-punkt (jeśli problem jest regularny). Wadą jest brak globalnej skalaryzacji — trzeba uruchomić optymalizację dla każdego $\varepsilon$ osobno. (Haimes, Lasdon, Wismer 1971).

Funkcje kosztu — szczegółowo

Długość ścieżki

L = \sum_i \|q_{i+1} - q_i\|

Najprostsze. Z metryką L2 lub ważoną.

Jerk (smoothness)

J_{\text{jerk}} = \int_0^T \|\dddot q\|^2 \, dt

Minimum-jerk to optymalna z Flash-Hogan (moduł 08). Quintic spline.

Clearance

J_{\text{clr}} = -\int_0^T \min(\Phi(q), \varepsilon) \, dt

Negatywny dla nagradzania większego SDF (większa odległość).

Manipulowalność

J_{\text{man}} = -\int_0^T w(q) \, dt

Negatywny by maksymalizować. Trzyma się z dala od singularności.

Energia

J_{\text{en}} = \int_0^T \|\tau(t)\|^2 \, dt

Minimum-effort. Wymaga inwersji dynamiki.

Czas

J_{\text{t}} = T

Time-optimal. Często trade-off z energią (faster = more torque).

Posture

J_{\text{post}} = \int_0^T \|q - q_{\text{nominal}}\|^2 \, dt

Trzyma się blisko „naturalnej" pozy. Przydatne dla HRI.

Kompozycja zadań — TAMP

Powyżej trade-off między continuous kryteriami. W realnych zadaniach manipulacyjnych mamy też discrete decisions:

Którym chwytakiem chwytać?
Z której strony obejść stół?
Najpierw kawałek A, potem B czy odwrotnie?
Trzymać obiekt w lewej czy prawej ręce?

TAMP (Task and Motion Planning) — kombinatorialne planowanie sekwencji symbolicznych akcji + ciągłe planowanie ruchu dla każdej.

PDDLStream (Garrett 2020)

Rozszerzenie PDDL (Planning Domain Definition Language) o streams — generatorów ciągłych parametrów (np. pozycji chwytaka). PDDLStream solver wybiera dyskretną akcję ORAZ parametry continuous razem.

LGP (Logic-Geometric Programming, Toussaint 2015)

Każda sekwencja akcji generuje NLP w continuous space. Optymalizuj LGP = kombinacja symboliczna + numeryczna. Klasyk dla manipulation TAMP.

HPN (Hierarchical Planning, Kaelbling-Lozano-Pérez 2010)

Plan w przestrzeni abstrakcji, decompoz na pre-conditions, każda rozwiązywana przez sub-planner. Skalowalne dla długich sekwencji.

Ściąga

Podejścia multi-objective

Weighted sum — λ daje pkt na front (jeśli convex)
Lexicographic — hierarchia kryteriów
ε-constraint — twardy constraint na jedno, optimize drugie
Goal programming — targety + odchylenia

Pareto-front

Zbiór rozwiązań niedominowanych. NIE-convex front wymaga ε-constraint, nie weighted-sum.

Funkcje kosztu

Długość — Σ‖Δq‖
Jerk — ∫‖q⃛‖²
Clearance — ∫min(Φ, ε)
Manipulowalność — ∫w(q)
Energia — ∫‖τ‖²
Czas — T
Posture — ∫‖q−q_nominal‖²

TAMP

PDDLStream — PDDL + continuous streams
LGP — logic + NLP per sequence
HPN — hierarchical abstrakcje

Referencje

Coello, „Evolutionary Algorithms for Solving Multi-Objective Problems" (Springer 2007).
Marler & Arora, „Survey of multi-objective optimization methods for engineering" (Struct. Multidiscip. Optim. 2004).
Garrett, Chitnis, Holladay, Kim, Silver, Kaelbling, Lozano-Pérez, „Integrated Task and Motion Planning" (Annual Review of Control, Robotics, and Autonomous Systems 2021).
Garrett, Lozano-Pérez, Kaelbling, „PDDLStream: Integrating Symbolic Planners and Blackbox Samplers via Optimistic Adaptive Planning" (ICAPS 2020).
Toussaint, „Logic-Geometric Programming: An Optimization-Based Approach to Combined Task and Motion Planning" (IJCAI 2015) — LGP.
Kaelbling & Lozano-Pérez, „Hierarchical Planning in the Now" (Workshops at AAAI 2010) — HPN.
Yoshikawa, „Manipulability of Robotic Mechanisms" (IJRR 1985) — origin of manipulability cost.