Paraméter nélküli mintavételes fiktív játék a determinisztikus dinamikus programozási problémák megoldásához

Absztrakt

Ebben a cikkben bemutatjuk a mintavételezett fiktív játék algoritmusának paraméter nélküli variációját, amely megkönnyíti a determinisztikus dinamikus programozási problémák gyors megoldását. Véletlenszerű megkötési eljárása természetes véletlenszerűséget kölcsönöz az algoritmusnak, amely megakadályozza, hogy „elakadjon” egy helyi optimális megoldásnál, és lehetővé teszi az optimális út felfedezését véges számú iterációban. Továbbá szemléltetjük a tengeri navigáció alkalmazásán keresztül, hogy a gyakorlatban egy paraméter nélküli mintavételes fiktív lejátszási algoritmus csak néhány ismétlés után talál kiváló minőségű megoldást, ellentétben a hagyományos módszerekkel.

Ez az előfizetéses tartalom előnézete. Jelentkezzen be a hozzáférés ellenőrzéséhez.

Hozzáférési lehetőségek

Vásároljon egyetlen cikket

Azonnali hozzáférés a teljes cikk PDF-hez.

Az adószámítás a fizetés során véglegesül.

Feliratkozás naplóra

Azonnali online hozzáférés minden kérdéshez 2019-től. Az előfizetés évente automatikusan megújul.

Az adószámítás a fizetés során véglegesül.

Hivatkozások

Denardo, E.V .: Dinamikus programozás. Dover Publications Inc., Mineola, NY (2003)

Bertsekas, D.P .: Dinamikus programozás és optimális vezérlés, 3. edn. Athena Scientific, Belmont (2007)

Androulakis, I.P .: Dinamikus programozás: készletellenőrzés dinamikus programozás: Készletszabályozás. In: Floudas, C. A., Pardalos, P.M. (szerk.) Optimalizálási enciklopédia, 853–856. Springer, USA (2009). doi: 10.1007/978-0-387-74759-0_149

Khaledi, H., Reisi-Nafchi, M .: Dinamikus gyártástervezési modell: dinamikus programozási megközelítés. Int J Adv Manuf Technol 67(5–8), 1675–1681 (2013). doi: 10.1007/s00170-012-4600-7

Sancho, N .: A legrövidebb út problémájának dinamikus programozási megoldása a mozgás és a parkolás időbeli korlátozásával. J. Math. Anális. Appl. 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 .: Új dinamikus programozási algoritmusok az erőforrás által korlátozott elemi legrövidebb út problémához. Hálózatok 51(3), 155–170 (2008). doi: 10,1002/nettó. v51: 3

Plant, W. J., Keller, W. C., Hayes, K .: Az óceáni szelek és hullámok egyidejű mérése levegőben lévő koherens valódi rekesznyílás radarral. J. Atmos. Óceáni Technol. 22., 832–846 (2005)

Johnson, J. T., Burkholder, R. J., Toporkov, J. V., Lyzenga, D. R., Plant, W. J.: A tengerfelszín magassági profiljának visszaszerzésének numerikus vizsgálata alacsony legeltetési szögű radaradatokból. IEEE Trans. Geosci. Távérzékelő. 47(6), 1641–1650 (2009)

Alford, L. K., Beck, R. F., Johnson, J.T., Lyzenga, D., Nwogu, O., Zundel, A .: Környezeti és hajómozgás-előrejelzési rendszer tervezése, megvalósítása és értékelése. In: 30. szimpózium a haditengerészeti hidrodinamikáról. Hobart, Tasmania, Ausztrália (2014)

Nwogu, O.G .: Véges amplitúdójú hullámok kölcsönhatása függőlegesen nyírt áramterekkel. J. Fluid Mech. 627, 179–213 (2009)

Nwogu, O.G., Lyzenga, D.R .: Felszíni hullámtér becslése koherens tengeri radarokból. IEEE Geosci. Távérzékelő. Lett. 7(4), 631–635 (2010)

Zhang, X., Bandyk, P., Beck, R.F .: Háztartási számítások kettős test alapú áramlásokkal. Appl. Ocean Res. 32(4), 471–482 (2010)

Dreyfus, S.E .: Néhány legrövidebb útú algoritmus értékelése. Oper. Res. 17.(3), 395–412 (1969)

Ahuja, R.K., Mehlhorn, K., Orlin, J., Tarjan, R.E .: Gyorsabb algoritmusok a legrövidebb út problémájához. JACM 37(2), 213–223 (1990). doi: 10.1145/77600.77615

Ahuja, R. K., Magnanti, T. L., Orlin, J. B. .: Hálózati áramlások. Prentice Hall, Englewood Cliffs (1993)

Schrijver, A .: Combinatorial Optimization: Polyhedra and Efficiency, vol. 24. Springer Science & Business Media, Berlin (2003)

Pearl, J .: Heurisztika: Intelligens keresési stratégiák a számítógépes problémamegoldáshoz. Addison-Wesley, Reading (1984)

Gubichev, A., Bedathur, S., Seufert, S., Weikum, G .: A legrövidebb utak gyors és pontos becslése nagy grafikonokban. In: A 19. ACM nemzetközi konferencia az információ- és tudásmenedzsmentről, CIKM ’10, 499–508. ACM, New York, NY (2010). doi: 10.1145/1871437.1871503

Brown, G.W .: A játékok iteratív megoldása fiktív játékkal. In: Koopmans, T.C. (szerk.) A termelés és az allokáció tevékenységelemzése, fej. XXIV, 374–376. Wiley, New York (1951)

Robinson, J .: A játék megoldásának iteratív módszere. Ann. Math. 54.(2), 296–301 (1951)

Monderer, D., Shapley, L.S .: Fiktív játéktulajdon azonos érdeklődésű játékokhoz. J. Econ. Elmélet 68(14), 258–265 (1996)

Lambert, T.J.I., Epelman, M.A., Smith, R.L .: Fiktív játékszemlélet a nagyszabású optimalizáláshoz. Oper. Res. 53(3), 477–489 (2005)

Cheng, S. F., Epelman, M. A., Smith, R. L.: CoSIGN: párhuzamos algoritmus a koordinált forgalmi jel vezérléséhez. IEEE Trans. Intell. Ford. Syst. 7(4), 551–564 (2006)

Garcia, A., Reaume, D., Smith, R.L .: Fiktív játék a rendszer optimális útválasztásának megtalálásához a dinamikus forgalmi hálózatokban. Ford. Res. B 34(2), 147–156 (2000)

Garcia, A., Patek, S. D., Sinha, K .: A diszkrét optimalizálás decentralizált megközelítése szimulációval: alkalmazás a hálózati áramláshoz. Oper. Res. 55(4), 717–732 (2007)

Ghate, A., Cheng, S.F., Baumert, S., Reaume, D., Sharma, D., Smith, R.L .: Mintavételes fiktív játék több cselekvésű sztochasztikus dinamikus programokhoz. IIE Trans. 46(7), 742–756 (2014)

Sisikoglu, E .: Fiktív játékon alapuló elosztott algoritmusok az optimális szekvenciális döntéshozatalhoz. Ph.D. szakdolgozat, Michigani Egyetem, Ann Arbor, MI (2009)

Epelman, M. A., Ghate, A., Smith, R. L.: Mintavételezett fiktív játék a hozzávetőleges dinamikus programozáshoz. Comput. Oper. Res. 36(12), 1705–1718 (2011)

Sisikoglu, E., Epelman, M. A., Smith, R. L.: Mintavételes fiktív játékalapú tanulási algoritmus a végtelen horizont horizontbeli döntési folyamataira. In: S. Jain, R. R. Creasey, J. Himmelspach, K. P. White, M. Fu (szerk.) A 2011. évi téli szimulációs konferencia anyagai, 4086–4097 (2011)

Powell, W.B .: Hozzávetőleges dinamikus programozás: A dimenzió átkainak megoldása, vol. 703. Wiley, Hoboken (2007)

Si, J., Barto, A. G., Powell, W. B., Wunsch, D .: A tanulás és a hozzávetőleges dinamikus programozás kézikönyve (IEEE Press Series on Computational Intelligence). Wiley-IEEE Press, New York (2004)

Marden, J. R., Young, H. P., Arslan, G., Shamma, J. S.: Kifizetés alapú dinamika a többjátékos gyengén aciklusos játékaihoz. SIAM J. Control Optim. 48(1), 373–396 (2009). doi: 10.1137/070680199

Buşoniu, L., Babuška, R., De Schutter, B., Ernst, D .: Megerősítő tanulás és dinamikus programozás a funkció-közelítők használatával. CRC Press, Boca Raton (2010) doi: 10.1201/9781439821091

Vrabie, D., Vamvoudakis, K.G., Lewis, F.L .: Optimális adaptív vezérlés és differenciáljátékok a tanulási elvek megerősítésével. Mérnöki és Technológiai Intézet, London (2012)

Zermelo, E .: Über das navigationsproblem bei ruhender oder veränderlicher windverteilung. Z. Angew. Math. Mech. 11.(2), 114–124 (1931)

Faulkner, F.D .: Általános numerikus módszer az optimális hajóútvonalak meghatározására. Navigáció 10.(2), 143–148 (1963)

Faulkner, F.D .: Numerikus módszerek az optimális hajóútvonalak meghatározására. Navigáció 10.(4), 351–367 (1963)

Papadakis, N.A., Perakis, A.N .: Determinisztikus minimális időtartamú hajóútválasztás. Oper. Res. 38(3), 426–438 (1990)

Perakis, A. N., Papadakis, N. A.: Új modellek a hajó időjárásának minimális időzítéséhez. Soc. Haditengerészeti Arch. Marine Eng. Ford. 96, 247–269 (1988)

Perakis, A. N., Papadakis, N. A.: A hajó minimális útvonala egy időtől függő környezetben. Ford. Sci. 23(4), 266–276 (1989)

Kimball, J. C., Story, H .: Fermat-elv, Huygens-elv, Hamilton optikája és vitorlázási stratégiája. Eur. J. Phys. 19., 15–24 (1998)

Philpott, A. B., Sullivan, R. M., Jackson, P. S.: Yacht sebességének előrejelzése matematikai programozással. Eur. J. Oper. Res. 67(1), 13–24 (1993)

Allsopp, T., Mason, A., Philpott, A.B .: Optimális vitorlázási út bizonytalan időjárással. In: Új-Zéland operatív kutatótársaságának 35. éves konferenciájának anyagai, 65–74. Oldal (2000)

Philpott, A.B .: Sztochasztikus optimalizálás és jachtverseny. In: A sztochasztikus programozás alkalmazásai, MPS/SIAM Ser. Optim., köt. 5, 315–336. SIAM, Philadelphia, PA (2005)

Philpott, A. B., Mason, A .: A jachtutak optimalizálása bizonytalanság alatt. In: A 15. Cheasapeake Vitorlás Jacht Szimpózium (2001)

Mitchell, J.S.B .: Geometriai legrövidebb utak és hálózatoptimalizálás. In: A számítási geometria kézikönyve, 633–701. Észak-Hollandia, Amszterdam (2000)

Lanthier, M., Maheshwari, A., Sack, J. R.: A legrövidebb anizotróp utak terepeken. In: Automaták, nyelvek és programozás (Prága, 1999), Előadási jegyzetek a Comput-ban. Sci., köt. 1644, 524–533. Springer, Berlin (1999)

Rowe, N.C .: Optimális mobil-robot útvonalak elérése nem egyenletes anizotróp költségfüggvényekkel kvalitatív állapotú érvelés segítségével. Int. J. Rob. Res. 16.(3), 375–399 (1997)

Rowe, N. C., Ross, R. S.: Optimális rács nélküli útvonaltervezés tetszőlegesen kontúrozott terepen, anizotrop súrlódási és gravitációs hatásokkal. IEEE Trans. Rob. Autom. 6.(5), 540–553 (1990)

Sun, Z., Rief, J.H .: Energiaminimalizáló utak megtalálásáról a terepeken. IEEE Trans. Rob. 21(1), 102–114 (2005)

Nilim, A., El Ghaoui, L., Hansen, M., Duong, V .: Trajektor alapú légiforgalmi irányítás (TB-ATM) az időjárási bizonytalanság alatt. In: A negyedik nemzetközi légiforgalmi szolgáltató K + F szeminárium ATM-je. Santa Fe, Új-Mexikó (2001)

Nilim, A., El Ghaoui, L .: Algoritmusok a légiforgalmi áramlás menedzselésére sztochasztikus környezetekben. Amerikai ellenőrző konferencia anyagai 4, 3429–3434 (2004)

Fang, M. C., Luo, J. H.: A hajó vágánymegtartásáról és gördüléscsökkentéséről véletlenszerű hullámokban, különböző csúszó üzemmódú vezérlőkkel. Ocean Eng. 34, 479–488 (2007)

Treakle, T.W.I., Mook, D.T., Liapis, S.I., Nayfeh, A.H .: Időtartományos módszer a mozgó súlyok használatának értékelésére a hajó gördülési mozgásának csökkentésére. Ocean Eng. 27.(12), 1321–1343 (2000)

Smith, T. C., Thomas III, W. L.: A hajó mozgáscsökkentő eszközeinek felmérése. Osztályi jelentés SHD-1338-01, David Taylor Kutatóközpont, Bethesda, Maryland, 20084-5000 (1990)

Dolinskaya, I. S.: Optimális útkeresés irány, hely és idő függő környezetekben. Nav. Res. Logista. Kvart. 59(5), 325–339 (2012)

Dijkstra, E.W .: Megjegyzés két problémáról a grafikonokkal való összefüggésben. Szám. Math. 1(1), 269–271 (1959)

Ross, S.M .: Sztochasztikus folyamatok, 2. kiadás. Wiley, New York (1995)

Zwillinger, D., Kokoska, S .: CRC standard valószínűségi és statisztikai táblázatok és képletek. CRC Press, Boca Raton (1999)

Fossen, T.I .: Óceánjárművek irányítása és ellenőrzése. Wiley, New York (1994)

Dubins, L.E .: Minimális hosszúságú íveken, az átlagos görbület korlátozásával, előírt kezdő- és véghelyzetekkel és érintőkkel. Amer. J. Math. 79, 497–516 (1957)

Sussmann, H. J., Tang, G .: A Reeds-Shepp autó legrövidebb útja: kidolgozott példa a geometriai technikák alkalmazására a nemlineáris optimális szabályozásban. Tech. SYCON-91-10. Képviselő, Rutgers Rendszer- és Vezérlési Központ (1991)

Boissonnat, J. D., Cérézo, A., Leblond, J .: A korlátozott görbület legrövidebb útjai a síkban. J. Intell. Rob. Syst. 11.(1–2), 5–20 (1994)

Alden, J. M., Smith, R. L.: Rolling horizon eljárások nem homogén Markov döntési folyamatokban. Oper. Res. 40(2. kiegészítés), S183 – S194 (1992)

Lee, C.Y., Denardo, E.V .: Gördülő tervezési horizontok: hibakorlátok a dinamikus tételméret-modellhez. Math. Oper. Res. 11.(3), 423–432 (1986)

Ovacikt, I. M., Uzsoy, R .: Rolling horizon algoritmusok egygépes dinamikus ütemezési problémához szekvenciafüggő beállítási időkkel. Int. J. Prod. Res. 32(6), 1243–1263 (1994)

Haditengerészeti Kutatási Iroda: MURI-optimális hajó manőverezése a fejlődő nemlineáris hullámterekben: Végső találkozó Arlington, VA (2011)

Köszönetnyilvánítás

A szerzők köszönetet mondanak Okey Nwogu-nak és Fernando Tavares-nek a megvalósításhoz nyújtott segítségért és a számszerű eredményekért. Ezt a munkát részben a Haditengerészeti Kutatási Iroda támogatta a Multidiszciplináris Egyetemi Kutatási Kezdeményezés (MURI) révén, az optimális edényteljesítmény a fejlődő nemlineáris hullámmezők támogatásában (N00014-05-1-0537).

Szerzői információk

Hovatartozások

Ipari Mérnöki és Menedzsmenttudományi Tanszék, Northwestern University, Evanston, IL, 60208, USA

Irina S. Dolinskaya

Ipari és Műszaki Műszaki Tanszék, University of Michigan, Ann Arbor, MI, 48109, USA

Marina A. Epelman és Robert L. Smith

Office of Access Management, Mayo Clinic, Rochester, MN, 55905, USA

Esra Şişikoğlu uram

A PubMed Google Scholar alkalmazásban is kereshet erre a szerzőre