{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,29]],"date-time":"2025-10-29T06:25:37Z","timestamp":1761719137586,"version":"build-2065373602"},"reference-count":44,"publisher":"MDPI AG","issue":"6","license":[{"start":{"date-parts":[[2022,6,9]],"date-time":"2022-06-09T00:00:00Z","timestamp":1654732800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100000006","name":"Naval Research awards","doi-asserted-by":"publisher","award":["N00014-18-1-2375","N00014-18-1-2828","W911NF-17-2-0181"],"award-info":[{"award-number":["N00014-18-1-2375","N00014-18-1-2828","W911NF-17-2-0181"]}],"id":[{"id":"10.13039\/100000006","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Army Research Laboratory under DCIST CRA","award":["N00014-18-1-2375","N00014-18-1-2828","W911NF-17-2-0181"],"award-info":[{"award-number":["N00014-18-1-2375","N00014-18-1-2828","W911NF-17-2-0181"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Entropy"],"abstract":"<jats:p>In this paper, a generalized information-theoretic framework for the emergence of multi-resolution hierarchical tree abstractions is developed. By leveraging ideas from information-theoretic signal encoding with side information, this paper develops a tree search problem which considers the generation of multi-resolution tree abstractions when there are multiple sources of relevant and irrelevant, or possibly confidential, information. We rigorously formulate an information-theoretic driven tree abstraction problem and discuss its connections with information-theoretic privacy and resource-limited systems. The problem structure is investigated and a novel algorithm, called G-tree search, is proposed. The proposed algorithm is analyzed and a number of theoretical results are established, including the optimally of the G-tree search algorithm. To demonstrate the utility of the proposed framework, we apply our method to a real-world example and provide a discussion of the results from the viewpoint of designing hierarchical abstractions for autonomous systems.<\/jats:p>","DOI":"10.3390\/e24060809","type":"journal-article","created":{"date-parts":[[2022,6,10]],"date-time":"2022-06-10T00:22:39Z","timestamp":1654820559000},"page":"809","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["A Generalized Information-Theoretic Framework for the Emergence of Hierarchical Abstractions in Resource-Limited Systems"],"prefix":"10.3390","volume":"24","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2544-6709","authenticated-orcid":false,"given":"Daniel T.","family":"Larsson","sequence":"first","affiliation":[{"name":"D. Guggenheim School of Aerospace Engineering, Georgia Institute of Technology, Atlanta, GA 30332-0150, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7745-9405","authenticated-orcid":false,"given":"Dipankar","family":"Maity","sequence":"additional","affiliation":[{"name":"Department of Electrical and Computer Engineering, The University of North Carolina at Charlotte, Charlotte, NC 28223-0001, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7563-4129","authenticated-orcid":false,"given":"Panagiotis","family":"Tsiotras","sequence":"additional","affiliation":[{"name":"D. Guggenheim School of Aerospace Engineering, Institute for Robotics and Intelligent Machines, Georgia Institute of Technology, Atlanta, GA 30332-0150, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2022,6,9]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"1197","DOI":"10.1098\/rstb.2003.1317","article-title":"Abstraction and reformulation in artificial intelligence","volume":"358","author":"Holte","year":"2003","journal-title":"Philos. Trans. R. Soc. B"},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"1293","DOI":"10.1098\/rstb.2003.1308","article-title":"A grounded theory of abstraction in artificial intelligence","volume":"358","author":"Zucker","year":"2003","journal-title":"Philos. Trans. R. Soc. B"},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Ponsen, M., Taylor, M.E., and Tuyls, K. (2009, January 12). Abstraction and generalization in reinforcement learning: A summary and framework. Proceedings of the International Workshop on Adaptive and Learning Agents, Budapest, Hungary.","DOI":"10.1007\/978-3-642-11814-2_1"},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"1544","DOI":"10.1038\/s41593-019-0470-8","article-title":"Learning task-state representations","volume":"22","author":"Niv","year":"2019","journal-title":"Nat. Neurosci."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"139","DOI":"10.1016\/0004-3702(91)90053-M","article-title":"Intelligence without representation","volume":"47","author":"Brooks","year":"1991","journal-title":"Artif. Intell."},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Behnke, S. (2004). Local multiresolution path planning. RoboCup 2003: Robot Soccer World Cup VII, Springer.","DOI":"10.1007\/978-3-540-25940-4_29"},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"1455","DOI":"10.1109\/TSMCB.2012.2192268","article-title":"Multiresolution motion planning for autonomous agents via wavelet-based cell decompositions","volume":"42","author":"Cowlagi","year":"2012","journal-title":"IEEE Trans. Syst. Man Cybern. Part B Cybern."},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Cowlagi, R.V., and Tsiotras, P. (2010, January 15\u201317). Multi-resolution path planning: Theoretical analysis, efficient implementation, and extensions to dynamic environments. Proceedings of the IEEE Conference on Decision and Control, Atlanta, GA, USA.","DOI":"10.1109\/CDC.2010.5717915"},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Cowlagi, R.V., and Tsiotras, P. (2008, January 11\u201313). Multiresolution path planning with wavelets: A local replanning approach. Proceedings of the American Control Conference, Seattle, WA, USA.","DOI":"10.1109\/ACC.2008.4586659"},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Tsiotras, P., and Bakolas, E. (2007, January 2\u20135). A hierarchical on-line path planning scheme using wavelets. Proceedings of the European Control Conference, Kos, Greece.","DOI":"10.23919\/ECC.2007.7068634"},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"505","DOI":"10.1007\/s10846-011-9631-z","article-title":"Multiresolution hierarchical path-planning for small UAVs using wavelet decompositions","volume":"66","author":"Tsiotras","year":"2012","journal-title":"J. Intell. Robot. Syst."},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Hauer, F., Kundu, A., Rehg, J.M., and Tsiotras, P. (2015, January 26\u201330). Multi-scale perception and path planning on probabilistic obstacle maps. Proceedings of the IEEE International Conference on Robotics and Automation, Seattle, WA, USA.","DOI":"10.1109\/ICRA.2015.7139779"},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"Hauer, F., and Tsiotras, P. (2016, January 16\u201321). Reduced complexity multi-scale path-planning on probabilitic maps. Proceedings of the IEEE Conference on Robotics and Automation, Stockholm, Sweden.","DOI":"10.1109\/ICRA.2016.7487119"},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1109\/JRA.1986.1087051","article-title":"Multiresolution path planning for mobile robots","volume":"RA-2","author":"Kambhampati","year":"1986","journal-title":"IEEE J. Robot. Autom."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"675","DOI":"10.1016\/S1474-6670(17)32056-6","article-title":"Probabilistic quadtrees for variable-resolution mapping of large environments","volume":"37","author":"Kraetzschmar","year":"2004","journal-title":"IFAC Proc. Vol."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1007\/s10514-012-9321-0","article-title":"Octomap: An efficient probabilistic 3D mapping framework based on octrees","volume":"34","author":"Hornung","year":"2013","journal-title":"Auton. Robot."},{"key":"ref_17","unstructured":"Cover, T.M., and Thomas, J.A. (2006). Elements of Information Theory, John Wiley & Sons. [2nd ed.]."},{"key":"ref_18","unstructured":"Tishby, N., Pereira, F.C., and Bialek, W. (1999, January 22\u201324). The information bottleneck method. Proceedings of the Allerton Conference on Communication, Control and Computing, Monticello, IL, USA."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"1611","DOI":"10.1162\/NECO_a_00961","article-title":"The deterministic information bottleneck","volume":"29","author":"Strouse","year":"2017","journal-title":"Neural Comput."},{"key":"ref_20","unstructured":"Chechik, G., and Tishby, N. (2002, January 9\u201312). Extracting relevant structures with side information. Proceedings of the Advances in Neural Information Processing Systems, Vancouver, BC, Canada."},{"key":"ref_21","unstructured":"Friedman, N., Mosenzon, O., Slonim, N., and Tishby, N. (2001, January 2\u20135). Multivariate information bottleneck. Proceedings of the Uncertainty in Artificial Intelligence, Seattle, WA, USA."},{"key":"ref_22","unstructured":"Slonim, N., and Tishby, N. (December, January 29). Agglomerative information bottleneck. Proceedings of the Advances in Neural Information Processing Systems, Denver, CO, USA."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"1739","DOI":"10.1162\/neco.2006.18.8.1739","article-title":"Multivariate information bottleneck","volume":"18","author":"Slonim","year":"2006","journal-title":"Neural Comput."},{"key":"ref_24","first-page":"165","article-title":"Information bottleneck for Gaussian variables","volume":"6","author":"Chechik","year":"2005","journal-title":"J. Mach. Learn. Res."},{"key":"ref_25","unstructured":"Estella Aguerri, I., and Zaidi, A. (2018, January 21\u201323). Distributed information bottleneck method for discrete and Gaussian sources. Proceedings of the International Zurich Seminar on Information and Communication, Zurich, Switzerland."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"120","DOI":"10.1109\/TPAMI.2019.2928806","article-title":"Distributed variational representation learning","volume":"43","author":"Aguerri","year":"2019","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"ref_27","doi-asserted-by":"crossref","unstructured":"Cover, T.M., and Permuter, H.H. (2007, January 24\u201330). Capacity of coordinated actions. Proceedings of the IEEE International Symposium on Information Theory, Nice, France.","DOI":"10.1109\/ISIT.2007.4557184"},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"4181","DOI":"10.1109\/TIT.2010.2054651","article-title":"Coordination capacity","volume":"56","author":"Cuff","year":"2010","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"1601","DOI":"10.1109\/TIP.2009.2017823","article-title":"Image segmentation using information bottleneck method","volume":"18","author":"Bardera","year":"2009","journal-title":"IEEE Trans. Image Process."},{"key":"ref_30","doi-asserted-by":"crossref","unstructured":"Kolchinsky, A., Tracey, B.D., and Wolpert, D.H. (2019). Nonlinear information bottleneck. Entropy, 21.","DOI":"10.3390\/e21121181"},{"key":"ref_31","unstructured":"Alemi, A.A., Fischer, I., Dillon, J.V., and Murphy, K. (2017, January 24\u201326). Deep variational information bottleneck. Proceedings of the International Conference on Learning Representations, Toulon, France."},{"key":"ref_32","unstructured":"Chalk, M., Marre, O., and Tkacik, G. (2016, January 6\u201310). Relevant sparse codes with variational information bottleneck. Proceedings of the Advances in Neural Information Processing Systems, Barcelona, Spain."},{"key":"ref_33","doi-asserted-by":"crossref","unstructured":"Zaidi, A., Estella-Aguerri, I., and Shamai, S. (2020). On the information bottleneck problems: Models, connections, applications and information theoretic views. Entropy, 22.","DOI":"10.3390\/e22020151"},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"7651","DOI":"10.1109\/LRA.2021.3099995","article-title":"Information-theoretic abstractions for planning in agents with computational constraints","volume":"6","author":"Larsson","year":"2021","journal-title":"IEEE Robot. Autom. Lett."},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"257","DOI":"10.1007\/s10514-017-9669-2","article-title":"Environment model adaptation for mobile robot exploration","volume":"42","author":"Nelson","year":"2018","journal-title":"Auton. Robot."},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"1669","DOI":"10.1109\/TRO.2020.3003219","article-title":"Q-tree search: An information-theoretic approach toward hierarchical abstractions for agents with computational limitations","volume":"36","author":"Larsson","year":"2020","journal-title":"IEEE Trans. Robot."},{"key":"ref_37","doi-asserted-by":"crossref","unstructured":"Larsson, D.T., Maity, D., and Tsiotras, P. (2021, January 18). Information-theoretic abstractions for resource-constrained agents via mixed-integer linear programming. Proceedings of the Proceedings of the Workshop on Computation-Aware Algorithmic Design for Cyber-Physical Systems, Nashville, TN, USA.","DOI":"10.1145\/3457335.3461704"},{"key":"ref_38","unstructured":"Gallager, R.G. (1968). Information Theory and Reliable Communication, Wiley."},{"key":"ref_39","unstructured":"Slonim, N. (2002). The Information Bottleneck: Theory and Applications. [Ph.D. Thesis, The Hebrew University]."},{"key":"ref_40","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1109\/18.61115","article-title":"Divergence measures based on the Shannon entropy","volume":"37","author":"Lin","year":"1991","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_41","doi-asserted-by":"crossref","unstructured":"Bondy, J.A., and Murty, U.S.R. (1976). Graph Theory with Applications, Elsevier Science.","DOI":"10.1007\/978-1-349-03521-2"},{"key":"ref_42","doi-asserted-by":"crossref","first-page":"412","DOI":"10.1016\/j.arcontrol.2019.04.006","article-title":"Information-theoretic approaches to privacy in estimation and control","volume":"47","author":"Nekouei","year":"2019","journal-title":"Annu. Rev. Control."},{"key":"ref_43","doi-asserted-by":"crossref","unstructured":"Makhdoumi, A., Salamatian, S., Fawaz, N., and M\u00e9dard, M. (2014, January 2\u20135). From the information bottleneck to the privacy funnel. Proceedings of the IEEE Information Theory Workshop, Hobart, NSW, Australia.","DOI":"10.1109\/ITW.2014.6970882"},{"key":"ref_44","doi-asserted-by":"crossref","unstructured":"Du Pin Calmon, F., and Fawaz, N. (2012, January 1\u20135). Privacy against statistical inference. Proceedings of the Allerton Conference on Communication, Control and Computing, Monticello, IL, USA.","DOI":"10.1109\/Allerton.2012.6483382"}],"container-title":["Entropy"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1099-4300\/24\/6\/809\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T23:27:17Z","timestamp":1760138837000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1099-4300\/24\/6\/809"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,6,9]]},"references-count":44,"journal-issue":{"issue":"6","published-online":{"date-parts":[[2022,6]]}},"alternative-id":["e24060809"],"URL":"https:\/\/doi.org\/10.3390\/e24060809","relation":{},"ISSN":["1099-4300"],"issn-type":[{"type":"electronic","value":"1099-4300"}],"subject":[],"published":{"date-parts":[[2022,6,9]]}}}