Your browser does not support JavaScript!
http://iet.metastore.ingenta.com
1887

access icon free Equilibrium with predictive routeing in the online version of the Braess paradox

The agents of a distributed adaptive system perceive the current state of their environment and make decisions which action to perform. The actions are both reactive and proactive. Reactivity can be supported by the availability of real-time data and proactivity can be supported by anticipatory techniques. Recent investigations proved that if the agents use selfish strategy, then in some situations sometimes the system maybe worst off with real-time data than without real-time data, even if anticipatory techniques are applied to predict the future state of the environment. This study investigates that version of the Braess paradox, where each subsequent agent of the flow may select a different route, using real-time data and anticipatory techniques. The authors contribute to the state-of-the-art by proving that the traffic distribution in this Braess paradox approximates the Nash equilibrium.

References

    1. 1)
      • 7. Varga, L.Z.: ‘On intention-propagation-based prediction in autonomously self-adapting navigation’, Scalable Comput., Pract. Exp., 2015, 16, (3), pp. 221232.
    2. 2)
      • 16. Blue, V.J., Adler, J.L., List, G.F.: ‘Real-time multiple-objective path search for in-vehicle route guidance systems’, Transp. Res. Rec. No. 1588, Intell. Transp. Syst. Artif. Intell., 1997, 1588, (3), pp. 1017.
    3. 3)
      • 12. Castle Rock Consultants: ‘Radio data system (RDS) traffic message channel (TMC)’. Final Report to the Commission of the European Communities, DRIVE Project V1029, 1988.
    4. 4)
      • 23. Parkes, D.C.: ‘Online mechanisms’, in Nisan, N., Roughgarden, T., Tardos, E., Vazirani, V.V. (EDs.): ‘Algorithmic game theory’ (Cambridge University Press, 2007), pp. 411439, New York.
    5. 5)
      • 13. Roughgarden, T.: ‘Routing games’, in Nisan, N., Roughgarden, T., Tardos, E., et al (EDs.): ‘Algorithmic game theory’ (Cambridge University Press, 2007), New York, pp. 461486.
    6. 6)
      • 9. An easily readable English description of the Braess paradox is available here. Available at http://www.vcp.med.harvard.edu/braess-paradox.html, accessed July 2016.
    7. 7)
      • 14. Wardrop, J.G.: ‘Some theoretical aspects of road traffic research’, Proc. Inst. Civil Eng. II, 1952, 1, (36), pp. 352378.
    8. 8)
      • 18. Montagna, S., Viroli, M., Fernandez-Marquez, J.L., et al: ‘Injecting self-organisation into pervasive service ecosystems’, Mob. Netw. Appl., 2013, 18, (3), pp. 398412.
    9. 9)
      • 24. Bazzan, A.L.C., Klügl, F.: ‘Reducing the effects of the Braess paradox with information manipulation’, in Klügl, F., Bazzan, A., Ossowski, S. (EDs.): ‘Applications of agent technology in traffic and transportation’, Whitestein Series in Software Agent Technologies, (Birkhäuser, Basel, 2005), pp. 8597.
    10. 10)
      • 20. Shoham, Y., Leyton-Brown, K.: ‘Multiagent systems: algorithmic, game-theoretic, and logical foundations’ (Cambridge University Press, 2009), New York.
    11. 11)
      • 25. Bazzan, A.L.C., Klügl, F.: ‘Case studies on the Braess paradox: simulating route recommendation and learning in abstract and microscopic models’, Transp. Res. C, 2005, 13, (4), pp. 299319.
    12. 12)
      • 17. Wolf, T.D., Holvoet, T.: ‘Design patterns for decentralised coordination in self-organising emergent systems’, in Brueckner, S.A., Hassas, S., Jelasity, M., et al (EDs.): ‘Engineering self-organising systems’, (Springer, Berlin, Heidelberg, 2007), (LNCS, 4335), pp. 2849.
    13. 13)
      • 5. Babaoglu, O., Canright, G., Deutsch, A., et al: ‘Design patterns from biology for distributed computing’, ACM Trans. Auton. Adapt. Syst., 2006, 1, (1), pp. 2666.
    14. 14)
      • 4. Rosen, R.: ‘Anticipatory systems: philosophical, mathematical, and methodological foundations (IFSR international series on systems science and engineering)’ (Pergamon Press, 1985), Oxford.
    15. 15)
      • 3. Varga, L.Z.: ‘Online routing games and the benefit of online data’. Proc. Eighth Int. Workshop on Agents in Traffic and Transportation, at 13th Int. Conf. on Autonomous Agents and Multiagent Systems (AAMAS 2014), Paris, France, May 2014, pp. 8895.
    16. 16)
      • 26. Blum, A., Even-Dar, E., Ligett, K.: ‘Routing without regret: on convergence to Nash equilibria of regret-minimizing algorithms in routing games’. Proc. 25th Annual ACM Symp. on Principles of distributed computing (PODC'06), New York, NY, USA, 2006, pp. 4552.
    17. 17)
      • 8. Braess, D.: ‘Über ein paradoxon der verkehrsplanung’, Unternehmensforschung, 1968, 12, (1), pp. 258268.
    18. 18)
      • 10. Varga, L.Z.: ‘Benefit of online real-time data in the Braess paradox with anticipatory routing’. Proc. Second Workshop on Distributed Adaptive Systems at 2016 IEEE Int. Conf. on Autonomic Computing, Würzburg, Germany, 19 July 2016, pp. 245250.
    19. 19)
      • 6. Claes, R., Holvoet, T., Weyns, D.: ‘A decentralized approach for anticipatory vehicle routing using delegate multi-agent systems’, IEEE Trans. Intell. Transp. Syst., 2011, 12, (2), pp. 364373.
    20. 20)
      • 22. Wooldridge, M.: ‘An introduction to multiAgent systems’ (John Wiley & Sons, 2009, 2nd edn.), Chichester.
    21. 21)
      • 2. Wahle, J., Bazzan, A.L.C., Klügl, F., et al: ‘Decision dynamics in a traffic scenario’, Phys. A, Stat. Mech. Appl., 2000, 287, (3-4), pp. 669681.
    22. 22)
      • 21. Rosenschein, J.S.: ‘Multiagent systems, and the search for appropriate foundations’. Proc. 12th Int. Conf. on Autonomous Agents and Multiagent Systems (AAMAS 2013), St. Paul, MN, USA, May 2013, pp. 56.
    23. 23)
      • 19. Fernandez-Marquez, J.L., Serugendo, G.D.M., Montagna, S., et al: ‘Description and composition of bio-inspired design patterns: a complete overview’, Nat. Comput., 2013, 12, (1), pp. 4367.
    24. 24)
      • 15. Beckmann, M.J., McGuire, C.B., Winsten, C.B.: ‘Studies in the economics of transportation’, in: ‘Published for the Cowles commission for research in economics’, (Yale University Press, 1956).
    25. 25)
      • 1. Çolak, S., Lima, A., González, M.C.: ‘Understanding congested travel in urban areas’, Nat. Commun., 2016, 7, Article number: 10793.
    26. 26)
      • 11. Varga, L.Z.: ‘How good is predictive routing in the online version of the Braess paradox?’. Proc. 22nd European Conf. on Artificial Intelligence (ECAI 2016), The Hague, The Netherlands, August 2016, pp. 16961697.
http://iet.metastore.ingenta.com/content/journals/10.1049/iet-sen.2016.0168
Loading

Related content

content/journals/10.1049/iet-sen.2016.0168
pub_keyword,iet_inspecKeyword,pub_concept
6
6
Loading
This is a required field
Please enter a valid email address