{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T02:58:56Z","timestamp":1760237936762,"version":"build-2065373602"},"reference-count":37,"publisher":"MDPI AG","issue":"2","license":[{"start":{"date-parts":[[2020,6,25]],"date-time":"2020-06-25T00:00:00Z","timestamp":1593043200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["407378162"],"award-info":[{"award-number":["407378162"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Robotics"],"abstract":"<jats:p>We present an efficient and generic algorithm for approximating second-order linear boundary value problems through spline collocation. In contrast to the majority of other approaches, our algorithm is designed for over-determined problems. These typically occur in control theory, where a system, e.g., a robot, should be transferred from a certain initial state to a desired target state while respecting characteristic system dynamics. Our method uses polynomials of maximum degree three\/five as base functions and generates a cubic\/quintic spline, which is     C 2    \/    C 4     continuous and satisfies the underlying ordinary differential equation at user-defined collocation sites. Moreover, the approximation is forced to fulfill an over-determined set of two-point boundary conditions, which are specified by the given control problem. The algorithm is suitable for time-critical applications, where accuracy only plays a secondary role. For consistent boundary conditions, we experimentally validate convergence towards the analytic solution, while for inconsistent boundary conditions our algorithm is still able to find a \u201creasonable\u201d approximation. However, to avoid divergence, collocation sites have to be appropriately chosen. The proposed scheme is evaluated experimentally through comparison with the analytical solution of a simple test system. Furthermore, a fully documented C++ implementation with unit tests as example applications is provided.<\/jats:p>","DOI":"10.3390\/robotics9020048","type":"journal-article","created":{"date-parts":[[2020,6,25]],"date-time":"2020-06-25T10:36:54Z","timestamp":1593081414000},"page":"48","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Fast Approximation of Over-Determined Second-Order Linear Boundary Value Problems by Cubic and Quintic Spline Collocation"],"prefix":"10.3390","volume":"9","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9464-041X","authenticated-orcid":false,"given":"Philipp","family":"Seiwald","sequence":"first","affiliation":[{"name":"Department of Mechanical Engineering, Chair of Applied Mechanics, Technical University of Munich, Boltzmannstra\u00dfe 15, 85748 Garching, Germany"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2303-4292","authenticated-orcid":false,"given":"Daniel J.","family":"Rixen","sequence":"additional","affiliation":[{"name":"Department of Mechanical Engineering, Chair of Applied Mechanics, Technical University of Munich, Boltzmannstra\u00dfe 15, 85748 Garching, Germany"}]}],"member":"1968","published-online":{"date-parts":[[2020,6,25]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"430","DOI":"10.1109\/8.558658","article-title":"Time-Domain Finite-Element Methods","volume":"45","author":"Lee","year":"1997","journal-title":"IEEE Trans. Antennas Propag."},{"key":"ref_2","unstructured":"Ahlberg, J.H., Nilson, E.N., and Walsh, J.L. (1967). The Theory of Splines and Their Applications, Academic Press. Mathematics in Science and Engineering."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"582","DOI":"10.1137\/0710052","article-title":"Collocation at Gaussian Points","volume":"10","author":"Swartz","year":"1973","journal-title":"SIAM J. Numer. Anal."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"761","DOI":"10.1090\/S0025-5718-1975-0375785-7","article-title":"A Collocation Method for Two-Point Boundary Value Problems","volume":"29","author":"Ahlberg","year":"1975","journal-title":"Math. Comput."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"227","DOI":"10.1007\/s00607-005-0140-4","article-title":"Optimal Quadratic and Cubic Spline Collocation on Nonuniform Partitions","volume":"76","author":"Christara","year":"2005","journal-title":"Computing"},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1016\/S0377-0427(00)00509-4","article-title":"Orthogonal spline collocation methods for partial differential equations","volume":"128","author":"Bialecki","year":"2001","journal-title":"J. Comput. Appl. Math."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"935","DOI":"10.1002\/nme.1620260412","article-title":"Quadratic-Spline Collocation Methods for Two-Point Boundary Value Problems","volume":"26","author":"Houstis","year":"1988","journal-title":"Int. J. Numer. Methods Eng."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"288","DOI":"10.1007\/BF01934092","article-title":"An O(h6) Quintic Spline Collocation Method for Fourth Order Two-Point Boundary Value Problems","volume":"28","author":"Houstis","year":"1988","journal-title":"BIT Numer. Math."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"401","DOI":"10.1016\/0021-9991(80)90097-2","article-title":"Solving Boundary-Value Problems with a Spline-Collocation Code","volume":"34","author":"Ascher","year":"1980","journal-title":"J. Comput. Phys."},{"key":"ref_10","first-page":"6565","article-title":"Quintic B-spline collocation method for fourth order partial integro-differential equations with a weakly singular kernel","volume":"219","author":"Zhang","year":"2013","journal-title":"Appl. Math. Comput."},{"key":"ref_11","first-page":"57","article-title":"Quintic spline collocation method for fractional boundary value problems","volume":"23","author":"Akram","year":"2017","journal-title":"J. Assoc. Arab Univ. Basic Appl. Sci."},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Ascher, U., and Spiteri, R. (1995). Collocation Software for Boundary Value Differential-Algebraic Equations. SIAM J. Sci. Comput., 15.","DOI":"10.1137\/0915056"},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"Seiwald, P., Sygulla, F., Staufenberg, N.S., and Rixen, D. (2019, January 15\u201317). Quintic Spline Collocation for Real-Time Biped Walking-Pattern Generation with variable Torso Height. Proceedings of the IEEE-RAS 19th International Conference on Humanoid Robots (Humanoids), Toronto, ON, Canada.","DOI":"10.1109\/Humanoids43949.2019.9035076"},{"key":"ref_14","unstructured":"Seiwald, P. (2020, June 22). Video: Smooth Real-Time Walking-Pattern Generation for Humanoid Robot LOLA. Available online: https:\/\/youtu.be\/piQm_oTYXIc."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"742","DOI":"10.1137\/0913044","article-title":"Stable Parallel Algorithms for Two-Point Boundary Value Problems","volume":"13","author":"Wright","year":"1992","journal-title":"SIAM J. Sci. Statistical Comput."},{"key":"ref_16","doi-asserted-by":"crossref","unstructured":"Magoul\u00e9s, F., Roux, F.X., and Houzeaux, G. (2015). Parallel Scientific Computing, Wiley & Sons.","DOI":"10.1002\/9781118761687"},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1016\/0771-050X(80)90002-9","article-title":"Smooth spline approximations for the solution of a boundary value problem with engineering applications","volume":"6","author":"Usmani","year":"1980","journal-title":"J. Comput. Appl. Math."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"279","DOI":"10.1016\/0771-050X(75)90020-0","article-title":"An algorithm for the interpolation of functions using quintic splines","volume":"1","author":"Mund","year":"1975","journal-title":"J. Comput. Appl. Math."},{"key":"ref_19","unstructured":"Buschmann, T., Lohmeier, S., Bachmayer, M., Ulbrich, H., and Pfeiffer, F. (December, January 29). A Collocation Method for Real-Time Walking Pattern Generation. Proceedings of the IEEE-RAS 7th International Conference on Humanoid Robots, Pittsburgh, PA, USA."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1137\/0720009","article-title":"On Spline Basis Selection for Solving Differential Equations","volume":"20","author":"Ascher","year":"1983","journal-title":"SIAM J. Numer. Anal."},{"key":"ref_21","unstructured":"De Boor, C. (2001). A Practical Guide to Splines, Springer."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"80","DOI":"10.1145\/355873.355880","article-title":"SOLVEBLOK: A Package for Solving Almost Block Diagonal Linear Systems","volume":"6","author":"Weiss","year":"1980","journal-title":"ACM Trans. Math. Software"},{"key":"ref_23","unstructured":"Majaess, F., Keast, P., and Fairweather, G. (1988). The Packages for solving almost block diagonal linear systems arising in spline collocation at Gaussian points with monomial basis functions. Scientific Software Systems, Springer."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"50","DOI":"10.1016\/0021-9045(72)90080-9","article-title":"On calculating with B-splines","volume":"6","year":"1972","journal-title":"J. Approximation Theor."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"171","DOI":"10.1007\/BF02240188","article-title":"Efficient Evaluation of Splines","volume":"33","year":"1984","journal-title":"Computing"},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"365","DOI":"10.1007\/BF02246763","article-title":"A Simplified B-Spline Computation Routine","volume":"29","author":"Lee","year":"1982","journal-title":"Computing"},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1007\/BF02240069","article-title":"Comments on Some B-Spline Algorithms","volume":"36","author":"Lee","year":"1986","journal-title":"Computing"},{"key":"ref_28","unstructured":"Horner, W.G., and Gilbert, D. (1819). A New Method of Solving Numerical Equations of All Orders, by Continuous Approximation, Philosophical Transactions of the Royal Society of London."},{"key":"ref_29","doi-asserted-by":"crossref","unstructured":"Higham, N.J. (2002). Accuracy and Stability of Numerical Algorithms, Society for Industrial and Applied Mathematics. [2nd ed.].","DOI":"10.1137\/1.9780898718027"},{"key":"ref_30","doi-asserted-by":"crossref","unstructured":"Quarteroni, A., Sacco, R., and Saler, F. (2007). Numerical Mathematics, Springer. [2nd ed.].","DOI":"10.1007\/978-0-387-22750-4"},{"key":"ref_31","unstructured":"Isaacson, E., and Keller, H.B. (1966). Analysis of Numerical Methods, Dover Publications, Inc."},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"707","DOI":"10.1137\/0613045","article-title":"A Review on the Inverse of Symmetric Tridiagonal and Block Tridiagonal Matrices","volume":"13","author":"Meurant","year":"1992","journal-title":"SIAM J. Matrix Anal. Appl."},{"key":"ref_33","unstructured":"Buschmann, T. (2010). Simulation and Control of Biped Walking Robots. [Ph.D. Thesis, Technical University of Munich]. Available online: https:\/\/mediatum.ub.tum.de\/997204."},{"key":"ref_34","unstructured":"Seiwald, P., and Sygulla, F. (2020, June 22). Broccoli: Beautiful Robot C++ Code Library. Available online: https:\/\/gitlab.lrz.de\/AM\/broccoli."},{"key":"ref_35","unstructured":"Guennebaud, G., and Jacob, B. (2020, June 22). Eigen. Available online: http:\/\/eigen.tuxfamily.org."},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"259","DOI":"10.1007\/s00607-005-0141-3","article-title":"Adaptive Techniques for Spline Collocation","volume":"76","author":"Christara","year":"2006","journal-title":"Computing"},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"859","DOI":"10.1090\/S0025-5718-1972-0323087-4","article-title":"On the Solution of Block-Tridiagonal Systems Arising from Certain Finite-Difference Equations","volume":"26","author":"Varah","year":"1972","journal-title":"Math. Comput."}],"container-title":["Robotics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2218-6581\/9\/2\/48\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T09:42:49Z","timestamp":1760175769000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2218-6581\/9\/2\/48"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6,25]]},"references-count":37,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2020,6]]}},"alternative-id":["robotics9020048"],"URL":"https:\/\/doi.org\/10.3390\/robotics9020048","relation":{},"ISSN":["2218-6581"],"issn-type":[{"type":"electronic","value":"2218-6581"}],"subject":[],"published":{"date-parts":[[2020,6,25]]}}}