Collision avoidance with bipartite arrangements

ABSTRACT

We demonstrate that qualitative spatial reasoning techniquesprovide useful means for autonomous systems in the context of collision avoidance. A qualitative spatial representation is presented which relies on quite abstract distinctions which describe how two objects can be aligned relative to each other. Possible alignments involve left and right, front and back, during, contains, and overlaps. It is shown how such qualitative relations already allow to make important decisions,for instance, in order to predict collisions. While the proposed calculus guarantees that predictions about collision-free situations never lead to collisions, predictions about collisions do not necessarily lead to collisions (though they occur more likely when they are predicted). We shall learn that it is by no means necessary to utilise precise measurements in order to predict collisions.

REFERENCES

• 1: James F. Allen, Maintaining knowledge about temporal intervals, Communications of the ACM, v.26 n.11, p.832-843, Nov. 1983 [doi>10.1145/182.358434]
• 2: Anthony G. Cohn, Qualitative Spatial Representation and Reasoning Techniques, Proceedings of the 21st Annual German Conference on Artificial Intelligence: Advances in Artificial Intelligence, p.1-30, September 09-12, 1997
• 3: A. G. Cohn , S. M. Hazarika, Qualitative spatial representation and reasoning: an overview, Fundamenta Informaticae, v.46 n.1-2, p.1-29, May 2001
• 4: M. Egenhofer. Definitions of line-line relations for geographic databases. In 16th Int. Conf. on Data Engineering, pages 40--46, 1993.
• 5: Kenneth D. Forbus, Qualitative process theory, Artificial Intelligence, v.24 n.1-3, p.85-168, Dec. 1984 [doi>10.1016/0004-3702(84)90038-9]
• 6: C. Freksa and K. Zimmermann. On the utilization of spatial structures for cognitively plausible and efficient reasoning. In IEEE International Conference on Systems, Man and Cybernetics, pages 261--266, Chicago, 1992.
• 7: C. Freksa and K. Zimmermann. On the utilization of spatial structures for cognitively plausible and efficient reasoning. In IEEE International Conference on Systems, Man and Cybernetics, pages 261--266, Chicago, 1992.
• 8: B. Gottfried. Singularities in Qualitative Reasoning. In B. Buchberger and J. Campbell, editors, AISC 2004, 7 th Int. Conference on Artificial Intelligence and Symbolic Mathematical Computation, LNAI, pages 276--280, Castle of Hagenberg, Linz, Austria, 2004. Springer-Verlag.
• 9: B. Gottfried. Shape from Positional-Contrast --- Characterising Sketches with Qualitative Line Arrangements, Dissertation, University of Bremen, Germany, 2005.
• 10: R. Moratz, J. Renz, and D. Wolter. Qualitative spatial reasoning about line segments. In ECAI 2000 Proceedings of the 14th European Conference on Artificial Intelligence, Amsterdam, 2000. IOS Press.
• 11: D. A. Randell, Z. Cui, and A. G. Cohn. A spatial logic based on regions and connection. In Proc 3rd Int. Conf. on Knowledge Representation and Reasoning, pages 165--176, San Mateo, 1992. Morgan Kaufman.
• 12: C. Schlenoff, R. Madhavan, and S. Balakirsky. An approach to predicting the location of moving objects during on-road navigation. In Proc. of IJCAI-03-Workshop on Issues in Designing Physical Agents for Dynamic Real-Time Environments: World modeling, planning, learning, an communicating, pages 71--79, 2003.
• 13: C. Schlieder. Reasoning about ordering. In A. Frank and W. Kuhn, editors, Spatial Information Theory: A Theoretical Basis for GIS, International Conference, volume 988, pages 341--349, Semmering, September 21-23 1995. Springer.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.9 Robotics
          Subjects: Autonomous vehicles

General Terms:
Algorithms

Keywords:
collision avoidance, line segment relations, orientation, position, qualitative spatial reasoning, relation algebra