Canada Spends Logo

Explore our Budget 2026 analysis

Grant: Engage Grants Program

University of Manitoba

$25,000.00

Kinetic collision detection and geometric covering problems related to robotic simulation

FY 2012-13

Summary
This research proposal considers algorithmic problems that arise in robotic simulation that are potentially solvable by adapting and applying solutions from the field of computational geometry. Specifically, we are interested in kinetic collision detection and geometric covering. Funding for this project will support two HQP for six months at the University of Manitoba in collaboration with Cogmation Robotics, also located in Winnipeg, Manitoba. This is a new industry-academia partnership. The first problem involves improving collision detection algorithms during simulation of moving robots. Current collision detection techniques employed by Cogmation Robotics' simulator are responsible for a significant fraction of the software's computation time. Capitalizing on various properties specific to robotic simulation data allows recently developed geometric data structures for moving objects to be applied, enabling more efficient and more precise prediction of future collisions between objects. The second problem involves designing an algorithm for decomposing the surface of a polyhedral robot model into a set of primitive polyhedral shapes whose union covers the model. The objective is to use as few primitive shapes as possible while faithfully representing the model. A collision detection algorithm is then applied on the set of primitive polyhedra, for which detecting collisions is a significantly simpler computational task. In general, such geometric covering problems are unlikely to be solvable optimally, requiring approximation techniques to be applied. Cogmation Robotics' products include a robotic simulator, a robotic modelling design tool, and a robotic control interface. This research will directly assist Cogmation Robotics in identifying and applying new algorithmic techniques to implement their products more efficiently. An improved product will help attract new clients and increase sales for this Canadian corporation, leading to additional job openings for software developers in the Winnipeg region.
Program
Engage Grants Program
Location
Manitoba, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data

As published

Application id
430538-2012
Name nom
Durocher, Stephane
Department département
Computer Science
Organization id
19
Institution établissement
University of Manitoba
Province en
Manitoba
Province fr
Manitoba
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2012
Competition year année de concours
2012
Award amount
25000
Program id
EGP
Program name en
Engage Grants Program
Program name fr
Programme de subventions d'engagement partenariat
Group en
Research partnerships programs
Group fr
Programmes de partenariat
Committee code
1555
Committee name en
Prairie Internal Decision Committee
Committee name fr
Comité de décision interne pour les Prairies
Area of application code
802
Area of application group en
Information and communication services
Area of application group fr
Services d'information et de télécommunications
Area of application en
Information systems and technology
Area of application fr
Systèmes d'information et technologie de l'information
Research subject code
2713
Research subject group en
Information technology
Research subject group fr
Technologie de l'information
Research subject en
Algorithms
Research subject fr
Algorithmes
Partie
1
Nb partie
1
Application title
Kinetic collision detection and geometric covering problems related to robotic simulation
Keyword
NSERC
Application summary
This research proposal considers algorithmic problems that arise in robotic simulation that are potentially solvable by adapting and applying solutions from the field of computational geometry. Specifically, we are interested in kinetic collision detection and geometric covering. Funding for this project will support two HQP for six months at the University of Manitoba in collaboration with Cogmation Robotics, also located in Winnipeg, Manitoba. This is a new industry-academia partnership. The first problem involves improving collision detection algorithms during simulation of moving robots. Current collision detection techniques employed by Cogmation Robotics' simulator are responsible for a significant fraction of the software's computation time. Capitalizing on various properties specific to robotic simulation data allows recently developed geometric data structures for moving objects to be applied, enabling more efficient and more precise prediction of future collisions between objects. The second problem involves designing an algorithm for decomposing the surface of a polyhedral robot model into a set of primitive polyhedral shapes whose union covers the model. The objective is to use as few primitive shapes as possible while faithfully representing the model. A collision detection algorithm is then applied on the set of primitive polyhedra, for which detecting collisions is a significantly simpler computational task. In general, such geometric covering problems are unlikely to be solvable optimally, requiring approximation techniques to be applied. Cogmation Robotics' products include a robotic simulator, a robotic modelling design tool, and a robotic control interface. This research will directly assist Cogmation Robotics in identifying and applying new algorithmic techniques to implement their products more efficiently. An improved product will help attract new clients and increase sales for this Canadian corporation, leading to additional job openings for software developers in the Winnipeg region.