Вибіркова фіктивна гра без параметрів для вирішення детермінованих проблем динамічного програмування

Анотація

У цій роботі ми представляємо варіацію алгоритму вибіркової фіктивної гри без параметрів, що сприяє швидкому вирішенню детермінованих задач динамічного програмування. Його процедура випадкового розриву зв'язків надає алгоритму природну випадковість, яка запобігає його "застряганню" при локальному оптимальному рішенні та дозволяє виявити оптимальний шлях у кінцевій кількості ітерацій. Крім того, ми ілюструємо за допомогою програми для морської навігації, що на практиці алгоритм вибіркової фіктивної гри без параметрів знаходить високоякісне рішення лише за кілька ітерацій, на відміну від традиційних методів.

Це попередній перегляд вмісту передплати, увійдіть, щоб перевірити доступ.

Параметри доступу

Придбайте одну статтю

Миттєвий доступ до повної статті PDF.

Розрахунок податку буде завершено під час оформлення замовлення.

Підпишіться на журнал

Негайний онлайн-доступ до всіх випусків з 2019 року. Підписка буде автоматично поновлюватися щороку.

Розрахунок податку буде завершено під час оформлення замовлення.

Список літератури

Денардо, Е. В.: Динамічне програмування. Dover Publications Inc, Мінеола, Нью-Йорк (2003)

Берцекас, Д.П .: Динамічне програмування та оптимальне управління, 3-е вид. Афіна Наукова, Белмонт (2007)

Андрулакіс, І.П .: Динамічне програмування: контроль запасів динамічне програмування: Управління запасами. У: Флоудас, К.А., Пардалос, П.М. (ред.) Енциклопедія оптимізації, с. 853–856. Спрінгер, США (2009). doi: 10.1007/978-0-387-74759-0_149

Халеді Х., Рейзі-Нафчі, М .: Модель динамічного планування виробництва: підхід динамічного програмування. Int J Adv Manuf Technol 67(5–8), 1675–1681 (2013). doi: 10.1007/s00170-012-4600-7

Санчо, Н.: Динамічне програмування рішення найкоротшого шляху із обмеженнями часу на рух та паркування. Дж. Математика. Анальний Заяв. 166(1), 192–198 (1992). doi: 10.1016/0022-247X (92) 90335-B. http://www.sciencedirect.com/science/article/pii/0022247X9290335B

Righini, G., Salani, M .: Нові алгоритми динамічного програмування для елементарної задачі найкоротшого шляху, обмеженої ресурсами. Мережі 51(3), 155–170 (2008). doi: 10.1002/net.v51: 3

Plant, W.J., Keller, W.C., Hayes, K .: Одночасне вимірювання океанічних вітрів та хвиль за допомогою повітряного когерентного радару реальної апертури. Дж. Атмос. Океанічний Технол. 22, 832–846 (2005)

Johnson, J.T., Burkholder, R.J., Toporkov, J.V., Lyzenga, D.R., Plant, W.J. IEEE Trans. Геосці. Віддалений сенсор. 47(6), 1641–1650 (2009)

Alford, L.K., Beck, R.F., Johnson, J.T., Lyzenga, D., Nwogu, O., Zundel, A .: Розробка, впровадження та оцінка системи прогнозування довкілля та руху суден. У: 30-й симпозіум з морської гідродинаміки. Хобарт, Тасманія, Австралія (2014)

Нвогу, О.Г .: Взаємодія хвиль кінцевої амплітуди з вертикально зрізаними струмовими полями. J. Fluid Mech. 627, 179–213 (2009)

Нвогу, О.Г., Лизенга, Д.Р .: Оцінка поверхневого хвильового поля за допомогою когерентних морських радарів. IEEE Geosci. Віддалений сенсор. 7(4), 631–635 (2010)

Чжан, X., Бандик, П., Бек, Р.Ф .: Обчислення морського обслуговування з використанням потоків на основі двох тіл. Заяв. Ocean Res. 32(4), 471–482 (2010)

Дрейфус, С. Е .: Оцінка деяких найкоротших алгоритмів. Опер. Рез. 17(3), 395–412 (1969)

Ahuja, R.K., Mehlhorn, K., Orlin, J., Tarjan, R.E .: Швидші алгоритми для задачі найкоротшого шляху. JACM 37(2), 213–223 (1990). doi: 10.1145/77600.77615

Ahuja, R.K., Magnanti, T.L., Orlin, J.B .: Network Flows. Прентис Холл, Енглвудські скелі (1993)

Шрейвер, А.: Комбінаційна оптимізація: багатогранники та ефективність, вип. 24. Springer Science & Business Media, Берлін (2003)

Перл, Дж .: Евристика: інтелектуальні стратегії пошуку для вирішення комп’ютерних проблем. Аддісон-Веслі, Редінг (1984)

Губічев А., Бедатур С., Сойферт С., Вейкум Г.: Швидка та точна оцінка найкоротших шляхів у великих графіках. В: Матеріали 19-ї міжнародної конференції ACM з питань управління інформацією та знаннями, CIKM ’10, с. 499–508. ACM, Нью-Йорк, Нью-Йорк (2010). doi: 10.1145/1871437.1871503

Браун, Г.В.: Ітеративне вирішення ігор фіктивною грою. У: Koopmans, T.C. (ред.) Аналіз діяльності виробництва та розподілу, розд. XXIV, с. 374–376. Уайлі, Нью-Йорк (1951)

Робінсон, Дж .: Ітераційний метод розв’язання гри. Енн Математика. 54(2), 296–301 (1951)

Мондерер Д., Шаплі Л.С .: Фіктивне властивість гри для ігор з однаковими інтересами. Дж. Екон. Теорія 68(14), 258–265 (1996)

Ламберт, T.J.I., Epelman, M.A., Smith, R.L .: Фіктивний ігровий підхід до масштабної оптимізації. Опер. Рез. 53(3), 477–489 (2005)

Cheng, S.F., Epelman, M.A., Smith, R.L .: CoSIGN: паралельний алгоритм для координованого управління сигналами дорожнього руху. IEEE Trans. Інтелл. Транс. Сист. 7(4), 551–564 (2006)

Гарсія, А., Реум, Д., Сміт, Р.Л .: Фіктивна гра для пошуку оптимальної маршрутизації системи в мережах динамічного трафіку. Транс. Рез. B 34(2), 147–156 (2000)

Гарсія, А., Патек, С.Д., Сіньха, К.: Децентралізований підхід до дискретної оптимізації за допомогою моделювання: застосування до мережевого потоку. Опер. Рез. 55(4), 717–732 (2007)

Гате, А., Ченг, С.Ф., Баумерт, С., Реум, Д., Шарма, Д., Сміт, Р.Л .: Зразки фіктивної гри для стохастичних динамічних програм із багатьма діями. IIE Trans. 46(7), 742–756 (2014)

Сісікоглу, Е .: Розподілені алгоритми, засновані на вигаданій грі для майже оптимального послідовного прийняття рішень. Доктор філософії дисертація, Мічиганський університет, Ен-Арбор, Мічиган (2009)

Епельман, М.А., Гете, А., Сміт, Р.Л .: Вибірка фіктивної гри для наближеного динамічного програмування. Обчислення. Опер. Рез. 36(12), 1705–1718 (2011)

Сісікоглу, Е., Епельман, М.А., Сміт, Р.Л .: Зразок фіктивного алгоритму навчання на основі гри для нескінченних процесів прийняття рішень Маркова. У: С. Джейн, Р. Р. Крейсі, Дж. Гіммельспах, К.П. Уайт, М. Фу (ред.) Матеріали зимової симуляційної конференції 2011 р., С. 4086–4097 (2011)

Пауелл, В.Б .: Приблизне динамічне програмування: розв’язання проклять мірності, вип. 703. Вілі, Хобокен (2007)

Si, J., Barto, A.G., Powell, W.B., Wunsch, D .: Посібник з навчання та наближеного динамічного програмування (IEEE Press Series on Computational Intelligence). Wiley-IEEE Press, Нью-Йорк (2004)

Марден, Дж. Р., Янг, Х. П., Арслан, Г., Шамма, Дж. С.: Динаміка на основі виплат для багатокористувацьких слабкоциклічних ігор. SIAM J. Control Optim. 48(1), 373–396 (2009). doi: 10.1137/070680199

Бушоніу, Л., Бабушка, Р., Де Шуттер, Б., Ернст, Д.: Підсилення навчання та динамічне програмування за допомогою функціональних апроксиматорів. CRC Press, Boca Raton (2010) doi: 10.1201/9781439821091

Врабіе Д., Вамвудакіс, К.Г., Льюїс, Ф.Л .: Оптимальний адаптивний контроль та диференціальні ігри за принципами підкріплення навчання. Інститут техніки та технологій, Лондон (2012)

Zermelo, E .: Über das navigationproblem bei ruhender oder veränderlicher windverteilung. З. Енджу. Математика Мех. 11(2), 114–124 (1931)

Фолкнер, Ф.Д .: Загальний чисельний метод для визначення оптимальних маршрутів суден. Навігація 10(2), 143–148 (1963)

Фолкнер, Ф. Д.: Чисельні методи визначення оптимальних маршрутів суден. Навігація 10(4), 351–367 (1963)

Пападакіс, Н.А., Перекіс, А.Н .: Детермінований мінімальний час маршруту судна. Опер. Рез. 38(3), 426–438 (1990)

Перекіс, А.Н., Пападакіс, Н.А .: Нові моделі для мінімальної тривалості погоди судна. Соц. Морська арка. Морський інж. Транс. 96, 247–269 (1988)

Перекіс, А.Н., Пападакіс, Н.А .: Мінімальна часова маршрутність судна в залежному від часу середовищі. Транс. Наук. 23(4), 266–276 (1989)

Kimball, J.C., Story, H .: принцип Ферма, принцип Гюйгенса, оптика Гамільтона та стратегія вітрильного спорту. Євро. J. Phys. 19, 15–24 (1998)

Філпот, А.Б., Салліван, Р.М., Джексон, П.С .: Прогнозування швидкості руху яхт за допомогою математичного програмування. Євро. Дж. Опер. Рез. 67(1), 13–24 (1993)

Олсопп, Т., Мейсон, А., Філпотт, А.Б .: Оптимальні маршрути плавання з невизначеною погодою. У: Матеріали 35-ї щорічної конференції Товариства оперативних досліджень Нової Зеландії, с. 65–74 (2000)

Філпот, А.Б .: Стохастична оптимізація та гонки на яхтах. В: Застосування стохастичного програмування, MPS/SIAM Сер. Оптим., вип. 5, с. 315–336. SIAM, Філадельфія, Пенсильванія (2005)

Філпот, А.Б., Мейсон, А.: Оптимізація маршрутів яхт в умовах невизначеності. В: 15-й симпозіум вітрильних яхт Cheasapeake (2001)

Мітчелл, Дж. Б .: Геометричні найкоротші шляхи та оптимізація мережі. У: Довідник з обчислювальної геометрії, с. 633–701. Північна Голландія, Амстердам (2000)

Lanthier, M., Maheshwari, A., Sack, J.R .: Найкоротші анізотропні стежки на місцевостях. У: Автомати, мови та програмування (Прага, 1999), Конспект лекцій з обчислення. Наук., вип. 1644, с. 524–533. Спрінгер, Берлін (1999)

Роу, штат Нью-Йорк: Отримання оптимальних шляхів руху мобільних роботів з негладкими анізотропними функціями витрат за допомогою міркувань якісного стану. Міжнародний Дж. Роб. Рез. 16(3), 375–399 (1997)

Роу, Н.К., Росс, Р.С .: Оптимальне планування шляху без сітки по довільно контурній місцевості з анізотропним ефектом тертя та гравітації. IEEE Trans. Роб. Автомат. 6(5), 540–553 (1990)

Sun, Z., Rief, J.H .: Про пошук шляхів, що мінімізують енергію, на місцевостях. IEEE Trans. Роб. 21(1), 102–114 (2005)

Нілім, А., Ель-Гауї, Л., Хансен, М., Дуонг, В.: Управління повітряним рухом на основі траєкторії (TB-ATM) в умовах погоди. В: Матеріали четвертого міжнародного семінару з досліджень та розробок управління повітряним рухом ATM. Санта-Фе, штат Нью-Мексико (2001)

Нілім, А., Ель-Гауї, Л.: Алгоритми управління потоком повітряного руху в стохастичних середовищах. Матеріали американської контрольної конференції 4, 3429–3434 (2004)

Fang, M.C., Luo, J.H .: Про утримання колії та зменшення крену корабля у випадкових хвилях за допомогою різних контролерів ковзного режиму. Ocean Eng. 34, 479–488 (2007)

Treakle, T.W.I., Mook, D.T., Liapis, S.I., Nayfeh, A.H .: Метод часової області для оцінки використання рухомих ваг для зменшення руху крену корабля. Ocean Eng. 27(12), 1321–1343 (2000)

Сміт, Т.К., Томас III, В.Л .: Обстеження пристроїв зменшення руху судна. Департаментський звіт SHD-1338-01, Дослідницький центр Девіда Тейлора, Бетесда, штат Меріленд, 20084-5000 (1990)

Долінська, І.С .: Оптимальний пошук шляху у середовищах, що залежать від напрямку, місця та часу. Нав. Рез. Логіст. Кварта. 59(5), 325–339 (2012)

Дейкстра, Е. У .: Примітка щодо двох проблем у зв'язку з графіками. Число. Математика. 1(1), 269–271 (1959)

Росс, С.М .: Стохастичні процеси, 2-е вид. Уайлі, Нью-Йорк (1995)

Цвілінгер Д., Кокоська, С .: Таблиці й формули стандартних ймовірностей та статистичних даних CRC. CRC Press, Boca Raton (1999)

Фоссен, Т.І .: Керівництво та контроль за океанськими транспортними засобами. Уайлі, Нью-Йорк (1994)

Дубінс, Л. Е .: На кривих мінімальної довжини з обмеженням на середню кривизну та із встановленими початковим та кінцевим положеннями та дотичними. Амер. Дж. Математика. 79, 497–516 (1957)

Sussmann, H.J., Tang, G .: Найкоротший шлях для автомобіля Рідса-Шеппа: відпрацьований приклад використання геометричних методів у нелінійному оптимальному контролі. Тех. Представник SYCON-91-10, Центр систем і управління Рутгерса (1991)

Boissonnat, J.D., Cérézo, A., Leblond, J .: Найкоротші шляхи обмеженої кривизни в площині. Дж. Інтелл. Роб. Сист. 11(1–2), 5–20 (1994)

Alden, J.M., Smith, R.L .: Процедури кочення горизонту в неоднорідних процесах рішення Маркова. Опер. Рез. 40(додаток 2), S183 – S194 (1992)

Лі, C.Y., Денардо, E.V .: Горизонти планомірного планування: межі помилок для динамічної моделі розміру партії. Математика Опер. Рез. 11(3), 423–432 (1986)

Ovacikt, I.M., Uzsoy, R .: Алгоритми кочення горизонту для одномашинної задачі динамічного планування із залежним від послідовності часом налаштування. Міжнародний J. Prod. Рез. 32(6), 1243–1263 (1994)

Управління морських досліджень: Оптимальне MURI маневрування судном у нових нелінійних хвильових полях: Підсумкове засідання. Арлінгтон, Вірджинія (2011)

Подяки

Автори висловлюють подяку Окі Нвогу та Фернандо Таваресу за допомогу у впровадженні та чисельні результати. Ця робота була частково підтримана Управлінням морських досліджень за допомогою Мультидисциплінарної університетської дослідницької ініціативи (MURI) Оптимальна продуктивність суден у гранті, що розвивається нелінійних хвильових полях (N00014-05-1-0537).

Інформація про автора

Приналежності

Кафедра промислової техніки та наук про управління, Північно-Західний університет, Еванстон, Іллінойс, 60208, США

Долина Ірина Сергіївна

Департамент промислового та експлуатаційного машинобудування, Мічиганський університет, Ен-Арбор, штат Мічиган, 48109, США

Марина А. Епельман та Роберт Л. Сміт

Управління управління доступом, клініка Майо, Рочестер, Міннесота, 55905, США

Есра Шисікоглу сер

Ви також можете шукати цього автора в PubMed Google Scholar