kth.sePublications
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Topological Methods for Motion Prediction and Caging
KTH, School of Electrical Engineering and Computer Science (EECS), Intelligent systems, Robotics, Perception and Learning, RPL. KTH, School of Electrical Engineering and Computer Science (EECS), Centres, Centre for Autonomous Systems, CAS.ORCID iD: 0000-0002-8750-0897
2020 (English)Doctoral thesis, comprehensive summary (Other academic)
Abstract [en]

To fulfill the requirements of automation in unstructured environmentsit will be necessary to endow robots with the ability to plan actions thatcan handle the dynamic nature of changing environments and are robust toperceptual errors. This thesis focuses on the design of algorithms to facilitatemotion planning in human environments and rigid object manipulation.Understanding human motion is a necessary first step to be able to performmotion planning in spaces that are inhabited by humans. Specifically throughlong-term prediction a robot should be able to plan collision-avoiding paths tocarry out whatever tasks are required of it. In this thesis we present a methodto classify motions by clustering paths, together with a method to translatethe resulting clusters into motion patterns that can be used to predict motion.Another challenge of robotics is the manipulation of everyday objects.Even in the realm of rigid objects, safe object-manipulation by either grippersor dexterous robotic hands requires complex physical parameter estimation.Such estimations are often error-prone and misestimations may cause completefailure to execute the desired task. Caging is presented as an alternativeapproach to classical manipulation by employing topological invariants todetermine whether an object is secured with only bounded mobility. Wepresent a method to decide whether a rigid object is in fact caged by a givengrasp or not, relying only on a rough approximation of the object and thegripper.

Abstract [sv]

För att uppfylla kraven för automatisering i ostrukturerade miljöer ärdet nödvändigt att förse robotar med förmågan att planera i föränderligamiljöer. Denna avhandling fokuserar på design av algoritmer för att underlättarörelseplanering i mänskliga miljöer och manipulering av rigida objekt.För att planera handlingar i utrymmen där människor rör sig är detnödvändigt, som ett första steg, att förstå hur människor rör sig. Genom långsiktigaprognoser om människors rörelser kan en robot planera undvikande avkollisioner, samtidigt som en given uppgift kan planeras. Den här avhandlingenpresenterar både metoder för klassificering av rörelser, samt metoder för attanvända dessa klasser för förutsägelse av rörelser.En annan stor utmaning för robotik är manipulering av vardagliga objekt.För att manipulera rigida objekt med enkla gripdon, så väl som avanceraderobothänder, är det nödvändigt att uppskatta komplexa fysiska parametrar.Sådana uppskattningar innehar ofta fel som kan leda till misslyckande med attutföra den givna uppgiften. Caging är ett alternativ till klassisk manipulering,där topologiska invarianter används för att avgöra om ett objekt är säkratmed endast begränsad rörlighet. Vi presenterar en metod för att bestämmaom en konfiguration kan hålla ett objekt fast eller inte, som bara förlitar sigpå en förenklad modell av objekt och gripdon.

Place, publisher, year, edition, pages
KTH Royal Institute of Technology, 2020.
Series
TRITA-EECS-AVL ; 2020:11
National Category
Robotics
Research subject
Computer Science
Identifiers
URN: urn:nbn:se:kth:diva-268370ISBN: 978-91-7873-450-4 (print)OAI: oai:DiVA.org:kth-268370DiVA, id: diva2:1394301
Public defence
2020-03-17, F3, Lindstedtsvägen 26, 114 28 Stockholm, 10:00 (English)
Opponent
Supervisors
Note

QC 20200221

Available from: 2020-02-21 Created: 2020-02-18 Last updated: 2022-06-26Bibliographically approved
List of papers
1. An algorithm for calculating top-dimensional bounding chains
Open this publication in new window or tab >>An algorithm for calculating top-dimensional bounding chains
2018 (English)In: PEERJ COMPUTER SCIENCE, ISSN 2376-5992, article id e153Article in journal (Refereed) Published
Abstract [en]

We describe the Coefficient-Flow algorithm for calculating the bounding chain of an (n-1)-boundary on an n-manifold-like simplicial complex S. We prove its correctness and show that it has a computational time complexity of O(vertical bar S(n-1)vertical bar) (where S(n-1) is the set of (n-1)-faces of S). We estimate the big-O coefficient which depends on the dimension of S and the implementation. We present an implementation, experimentally evaluate the complexity of our algorithm, and compare its performance with that of solving the underlying linear system.

Place, publisher, year, edition, pages
PEERJ INC, 2018
Keywords
Homology, Computational algebraic topology
National Category
Computational Mathematics
Identifiers
urn:nbn:se:kth:diva-232420 (URN)10.7717/peerj-cs.153 (DOI)000437236300001 ()33816807 (PubMedID)2-s2.0-85074143181 (Scopus ID)
Funder
Knut and Alice Wallenberg FoundationSwedish Research Council
Note

QC 20180725

Available from: 2018-07-25 Created: 2018-07-25 Last updated: 2022-06-26Bibliographically approved
2. Path Clustering with Homology Area
Open this publication in new window or tab >>Path Clustering with Homology Area
2018 (English)In: 2018 IEEE INTERNATIONAL CONFERENCE ON ROBOTICS AND AUTOMATION (ICRA), IEEE Computer Society, 2018, p. 7346-7353Conference paper, Published paper (Refereed)
Abstract [en]

Path clustering has found many applications in recent years. Common approaches to this problem use aggregates of the distances between points to provide a measure of dissimilarity between paths which do not satisfy the triangle inequality. Furthermore, they do not take into account the topology of the space where the paths are embedded. To tackle this, we extend previous work in path clustering with relative homology, by employing minimum homology area as a measure of distance between homologous paths in a triangulated mesh. Further, we show that the resulting distance satisfies the triangle inequality, and how we can exploit the properties of homology to reduce the amount of pairwise distance calculations necessary to cluster a set of paths. We further compare the output of our algorithm with that of DTW on a toy dataset of paths, as well as on a dataset of real-world paths.

Place, publisher, year, edition, pages
IEEE Computer Society, 2018
Series
IEEE International Conference on Robotics and Automation ICRA, ISSN 1050-4729
National Category
Geometry Computer Sciences
Identifiers
urn:nbn:se:kth:diva-237170 (URN)10.1109/ICRA.2018.8460939 (DOI)000446394505086 ()2-s2.0-85063140347 (Scopus ID)978-1-5386-3081-5 (ISBN)
Conference
IEEE International Conference on Robotics and Automation (ICRA), MAY 21-25, 2018, Brisbane, AUSTRALIA
Note

QC 20181024

Available from: 2018-10-24 Created: 2018-10-24 Last updated: 2024-03-15Bibliographically approved
3. Long-term Prediction of Motion Trajectories Using Path Homology Clusters
Open this publication in new window or tab >>Long-term Prediction of Motion Trajectories Using Path Homology Clusters
2019 (English)In: 2019 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), Institute of Electrical and Electronics Engineers (IEEE), 2019Conference paper, Published paper (Refereed)
Abstract [en]

In order for robots to share their workspace with people, they need to reason about human motion efficiently. In this work we leverage large datasets of paths in order to infer local models that are able to perform long-term predictions of human motion. Further, since our method is based on simple dynamics, it is conceptually simple to understand and allows one to interpret the predictions produced, as well as to extract a cost function that can be used for planning. The main difference between our method and similar systems, is that we employ a map of the space and translate the motion of groups of paths into vector fields on that map. We test our method on synthetic data and show its performance on the Edinburgh forum pedestrian long-term tracking dataset [1] where we were able to outperform a Gaussian Mixture Model tasked with extracting dynamics from the paths.

Place, publisher, year, edition, pages
Institute of Electrical and Electronics Engineers (IEEE), 2019
National Category
Computer Sciences
Identifiers
urn:nbn:se:kth:diva-266956 (URN)10.1109/IROS40897.2019.8968125 (DOI)000544658400089 ()2-s2.0-85081156994 (Scopus ID)
Conference
IEEE/RSJ International Conference on Intelligent Robots and Systems,3-8 Nov. 2019, Macau, China, China
Funder
Knut and Alice Wallenberg Foundation
Note

QC 20200203  QC 20200903

Available from: 2020-01-27 Created: 2020-01-27 Last updated: 2022-06-26Bibliographically approved
4. Free Space of Rigid Objects: Caging, Path Non-Existence, and Narrow Passage Detection
Open this publication in new window or tab >>Free Space of Rigid Objects: Caging, Path Non-Existence, and Narrow Passage Detection
(English)In: The international journal of robotics research, ISSN 0278-3649, E-ISSN 1741-3176Article in journal (Refereed) Submitted
Abstract [en]

In this work we propose algorithms to explicitly construct a conservative estimate of the configuration spaces of rigid objects in 2D and 3D. Our approach is able to detect compact path components and narrow passages in configuration space which are important for applications in robotic manipulation and path planning. Moreover, as we demonstrate, they are also applicable to identification of molecular cages in chemistry. Our algorithms are based on a decomposition of the resulting 3 and 6 dimensional configuration spaces into slices corresponding to a finite sample of fixed orientations in configuration space. We utilize dual diagrams of unions of balls and uniform grids of orientations to approximate the configuration space. We carry out experiments to evaluate the computational efficiency on a set of objects with different geometric features thus demonstrating that our approach is applicable to different object shapes. We investigate the performance of our algorithm by computing increasingly fine-grained approximations of the object's configuration space.

National Category
Robotics
Identifiers
urn:nbn:se:kth:diva-268368 (URN)
Note

QC 20200506

Available from: 2020-02-18 Created: 2020-02-18 Last updated: 2022-06-26Bibliographically approved

Open Access in DiVA

fulltext(14984 kB)290 downloads
File information
File name FULLTEXT01.pdfFile size 14984 kBChecksum SHA-512
48f2c1c2e8a77341a7a5fa137576e908f5e0ad0a4c7460ed2723c443138ae385ea9d396ed9fc31bf587bc37c2e43e47c62b3d5a5a003698a39d748cd6c5ae038
Type fulltextMimetype application/pdf

Authority records

Pinto Basto de Carvalho, Joao Frederico

Search in DiVA

By author/editor
Pinto Basto de Carvalho, Joao Frederico
By organisation
Robotics, Perception and Learning, RPLCentre for Autonomous Systems, CAS
Robotics

Search outside of DiVA

GoogleGoogle Scholar
Total: 292 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

isbn
urn-nbn

Altmetric score

isbn
urn-nbn
Total: 424 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf