Approximating the Value of Collaborative Team Actions for Efficient Multiagent Navigation in Uncertain Graphs
Keywords:Multi-Robot Systems, Localization, Mapping, and Navigation, Motion and Path Planning
AbstractFor a team of collaborative agents navigating through an unknown environment, collaborative actions such as sensing the traversability of a route can have a large impact on aggregate team performance. However, planning over the full space of joint team actions is generally computationally intractable. Furthermore, typically only a small number of collaborative actions is useful for a given team task, but it is not obvious how to assess the usefulness of a given action. In this work, we model collaborative team policies on stochastic graphs using macro-actions, where each macro-action for a given agent can consist of a sequence of movements, sensing actions, and actions of waiting to receive information from other agents. To reduce the number of macro-actions considered during planning, we generate optimistic approximations of candidate future team states, then restrict the planning domain to a small policy class which consists of only macro-actions which are likely to lead to high-reward future team states. We optimize team plans over the small policy class, and demonstrate that the approach enables a team to find policies which actively balance between reducing task-relevant environmental uncertainty and efficiently navigating to goals in toy graph and island road network domains, finding better plans than policies that do not act to reduce environmental uncertainty.
How to Cite
Stadler, M., Banfi, J., & Roy, N. (2023). Approximating the Value of Collaborative Team Actions for Efficient Multiagent Navigation in Uncertain Graphs. Proceedings of the International Conference on Automated Planning and Scheduling, 33(1), 677-685. https://doi.org/10.1609/icaps.v33i1.27250