Bounded-rate multi-mode systems based motion planning

DOI10.1145/2728606.2728616MaRDI QIDQ2988914zbMATH OpenOpenAlexWikidataFDO

Authors Devendra Bhave, Sagar Jha, Shankara Narayanan Krishna, Sven Schewe, Ashutosh Trivedi

Publication date 19 May 2017

Published in Proceedings of the 18th International Conference on Hybrid Systems: Computation and Control (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1412.3670

zbMATH Keywords

hybrid automatamotion planningswitched systems

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Control/observation systems governed by functional relations other than differential equations (such as hybrid and switching systems) (93C30)

Abstract: Bounded-rate multi-mode systems are hybrid systems that can switch among a finite set of modes. Its dynamics is specified by a finite number of real-valued variables with mode-dependent rates that can vary within given bounded sets. Given an arbitrary piecewise linear trajectory, we study the problem of following the trajectory with arbitrary precision, using motion primitives given as bounded-rate multi-mode systems. We give an algorithm to solve the problem and show that the problem is co-NP complete. We further prove that the problem can be solved in polynomial time for multi-mode systems with fixed dimension. We study the problem with dwell-time requirement and show the decidability of the problem under certain positivity restriction on the rate vectors. Finally, we show that introducing structure to the multi-mode systems leads to undecidability, even when using only a single clock variable.

Recommendations

• Real-time motion planning for multibody systems
• Multi-modal motion planning in non-expansive spaces
• Constrained motion planning of nonholonomic systems
• A boundary-integral algorithm for adaptive motion planning
• Stochastic reachability based motion planning for multiple moving obstacle avoidance
• Unified Multirate Control: From Low-Level Actuation to High-Level Planning
• scientific article; zbMATH DE number 426006
• Pushing the boundaries of asymptotic optimality in integrated task and motion planning
• Optimal Multivehicle Motion Planning Using Bernstein Approximants
• Motion planning in velocity affine mechanical systems

Cites work

• Continuous system simulation
• scientific article; zbMATH DE number 1638973 (Why is no real title available?)
• Hybrid Systems: Computation and Control
• On fixed points of strictly causal functions
• Requirements for hybrid cosimulation standards
• THEORY OF QUANTIZED SYSTEMS: DEVS SIMULATION OF PERCEIVING AGENTS

Cited in

(3)

• Safe schedulability of bounded-rate multi-mode systems
• The Reach-Avoid Problem for Constant-Rate Multi-mode Systems
• The complexity of linear temporal verification for continuous counter systems

This page was built for publication: Bounded-rate multi-mode systems based motion planning

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2988914)