Abstract
In studying robots and planning problems, a basic question is what is the minimal information a robot must obtain to guarantee task completion. Erdmann’s theory of action-based sensors is a classical approach to characterizing fundamental information requirements. That approach uses a plan to derive a type of virtual sensor which prescribes actions that make progress toward a goal. We show that the established theory is incomplete: the previous method for obtaining such sensors, using backchained plans, overlooks some sensors. Furthermore, there are plans, that are guaranteed to achieve goals, where the existing methods are unable to provide any action-based sensor. We identify the underlying feature common to all such plans. Then, we show how to produce action-based sensors even for plans where the existing treatment is inadequate, although for these cases they have no single canonical sensor. Consequently, the approach is generalized to produce sets of sensors. Finally, we show also that this is a complete characterization of action-based sensors for planning problems and discuss how an action-based sensor translates into the traditional conception of a sensor.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
For clarity when reading, we often refer to Erdmann by name when making reference to his theory of action-based sensors. Unless otherwise indicated, this is a reference to [5].
- 2.
Or perhaps resurrecting?
- 3.
In particular, knowledge of the starting location provides information in the form of context to incoming observations, allowing an agent to gather information it might not otherwise have.
- 4.
In this paper, we are considering fully observable planning problems and plans which may be at only one state in the world during any point of execution, for which an execution progress measure and vertex progress measure are equivalent. However, there exist plans in which an agent may be in multiple potential world states, for which both the execution progress measure and vertex progress measure are required to define progress-making actions.
References
Blum, M., Kozen, D.: On the power of the compass (or, why mazes are easier to search than graphs). In: Annual Symposium on Foundations of Computer Science, pp. 132–142 (1978)
Brooks, R., Matarić, M.: Real robots, real learning problems. In: Robot Learning, pp. 193–213. Springer, Heidelberg (1993)
Censi, A.: A mathematical theory of co-design. arXiv preprint arXiv:1512.08055 (2015)
Donald, B.R.: On information invariants in robotics. Artif. Intell. 72(1–2), 217–304 (1995). Special Volume on Computational Research on Interaction and Agency, Part 1
Erdmann, M.: Understanding action and sensing by designing action-based sensors. Int. J. Robot. Res. 14(5), 483–509 (1995)
O’Kane, J.M., LaValle, S.M.: Comparing the power of robots. Int. J. Robot. Res. 27(1), 5–23 (2008)
Acknowledgement
This work was supported, in part, by the National Science Foundation through awards IIS-1453652 and IIS-1849249, and from a graduate fellowship provided to Texas A&M University by the 3M Company and 3M Gives.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2021 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
McFassel, G., Shell, D.A. (2021). Every Action-Based Sensor. In: LaValle, S.M., Lin, M., Ojala, T., Shell, D., Yu, J. (eds) Algorithmic Foundations of Robotics XIV. WAFR 2020. Springer Proceedings in Advanced Robotics, vol 17. Springer, Cham. https://doi.org/10.1007/978-3-030-66723-8_11
Download citation
DOI: https://doi.org/10.1007/978-3-030-66723-8_11
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-66722-1
Online ISBN: 978-3-030-66723-8
eBook Packages: Intelligent Technologies and RoboticsIntelligent Technologies and Robotics (R0)