Development of Parallel Parking System

Executive Summary

Introduction/Background

Traditionally development of microprocessor based control systems involved the following steps. The control algorithm was designed by a systems or a control engineer. The algorithm would then be coded in programming languages like assembly, C or C++ which would be implemented on a microprocessor based hardware – the controller.

The problem with this method was the verification of the algorithm would be possible only once the whole system was developed. Any errors in design would prove extremely costly. Also in converting control logic specification into software there is a high probability of translation errors that would lead to erroneous results.

mModel Based Design is a software methodology which addresses these issues and is gaining a lot of popularity currently in the industry.

The scope of this project is to apply the Model Based Design methodology to develop a control algorithm that eases the parallel parking of a car problem for a novice driver.

Aims and Objectives

The aim of this project is to develop a parallel parking system using Model Based Design. The objectives are to understand the parallel parking problem and methods to solve it, steps involved in Model Based Design and explore the possibility of implementation of a parallel parking algorithm on a Lego Mindstorms Robotics Kit.

Acheivements

A fuzzy logic based parallel parking algorithm was successfully simulated. Model Based Design concepts were explored and implemented in the design. Programs developed in Simulink were successfully tested on the Lego Mindstorms KIT using Real Time Workshop Embedded Coder, EC Robot Toolbox, nxtOSEK and other associated tools.

Conclusions/Recommendations

The parallel parking strategy implemented did show good results. However, real life scenarios may be different than the one discussed. For example, the controller depends on wall following. This implies there has to be 3 sides closed in a gap for the parking controller to work.

The development of the algorithm was with the intent of being able to execute it on a Lego Mindstorms Kit. However, there were some issues regarding this. The main being lack of a floating point unit on the NXT Brick. Though it is possible to execute floating point programs on the NXT, it causes severe performance issues.

The controller developed used the fuzzy logic blockset which inherently uses a lot of floating point variables. One method to overcome this draw back could be developing a fixed point version of the fuzzy logic blockset.

Other parking strategies involving classical control could be experimented with Lego Mindstorms. Complex tasks like path planning could be executed on a computer communicating with the NXT via Bluetooth and the control tasks could be implemented on the NXT using fixed point math.

Introduction

Problem Description

The parallel parking manoeuvre of a car has been a topic of academic and industry interest. The car or a car-like mobile robot hence referred to as CLMR has inherently a constraint known as a nonholonomic constraint. This is problem can be summarised as follows (Pushkin Kachroo and Patricia Mellodge, 2004.). If a system has restrictions on its velocity, but those restrictions does not cause restrictions in its positioning the systems is said to be nonholonomically constrained. Viewed in another way, the systems local movement is restricted, but its global movement is not.

Mathematically, this means that the velocity constraints cannot be integrated. For e.g. during a parallel parking manoeuvre, when a driver arrives next to a parking space, he cannot simply slide his car sideways into the spot. The car is not capable of sliding sideways and this is the velocity restriction. However by moving the car backward and forward and turning the wheels the car can be moved into the parking space. Ignoring the restrictions caused by the external objects the car can be located at any position with any orientation, despite the lack of sideways movement (Pushkin Kachroo and Patricia Mellodge, 2004.).

The challenge in this project is to not only address the parallel parking problem but also to develop it using advanced software design techniques involving Model Based Design

Literature Survey

The parallel parking problem can be viewed as a subtask of robot motion planning and control. There is has been considerable research in this area. De Luca et al (1998) classifies all robot motion tasks into 3 subtasks as follows.

Point-to-point motion: The robot must reach a desired goal configuration starting from a given initial configuration.

Path following: The robot must reach and follow a geometric path in the Cartesian space starting from a given initial configuration (on or off the path).

Trajectory tracking: The robot must reach and follow a trajectory in the Cartesian space (i.e., a geometric path with an associated timing law) starting from a given initial configuration (on or off the trajectory)

A parallel parking problem can then considered as a point to point motion task or a path following task and a feedback control law if proposed for the same.

(Dongbing and Huosheng 2000) have developed more advanced control strategies involving Generalized Predictive Control and Neural Networks based predictive control.

Fuzzy Logic based controllers have also been used to solve the parallel parking problem. Shih-Jie and Tzuu-Hseng (2002) proposes a rule base based on the distance of the CLMR edge’s to the parking spot.

Kuang-Yow et al (1999) proposes a fuzzy sliding mode controller to solve the parallel parking problem.

Holve and Protzel (1996) suggest another fuzzy logic based controller and a parking algorithm based on human experience. It involves finding an appropriate space for parking, stopping at the right place, executing the parking procedure and to do so without colliding with any obstacles.

Summary

The classical control methods discussed above are generally more complex compared to other ones. Most of them rely on trajectory generation and then a control algorithm for trajectory tracking or path following. The success of the algorithm in a real time implementation also depends upon the accuracy of the positioning systems which increases the complexity and the hardware cost of this method.

While the fuzzy logic based controllers are more intuitive and easier to design the performance is suboptimal compared to the classical controllers. But they are more robust to sensor uncertainties (Holve, R. & Protzel, P. 1996).

The goal of this project is to develop a parallel parking algorithm suitable for implementation on a Lego Mindstorms robotics kit. Being able to solve the parallel parking problem and take this design rapidly from concept to implementation is the motivation behind this project.

Parallel Parking of a Car like Mobile Robot (CLMR)

Introduction

The following chapter discusses the kinematics model of a CLMR and investigates a feasible parking strategy using a fuzzy logic based controller.

Kinematic Model of a CLMR

The kinematic model of a CLMR is as shown (Shih-Jie and Tzuu-Hseng 2002).The model assumes that the car wheels are in contact with the ground at all time i.e. no slip exists.

: is a mid point on the rear axle of the car

: is mid point on the line joining the front wheels

: is the angle between the X axis with respect to the vehicle frame

: is the steering angle with respect to the vehicle frame

: is the distance between the front and rear axle

The non-holonomic constraint equation is given by

(2.1)

The equation of the rear wheel is given by

(2.2)

(2.3)

(2.4)

The relationship between the rear and the front wheels are given by

And (2.5)

(2.6)

The above equations are useful while finding the future positions of the CLMR.

The physical layout of the CLMR is a three wheeled one. A three wheel robot and a four wheeled one have the same non- holonomic constraint. A three wheeled robot is chosen here for simplicity.

The sensor positions are chosen with the assumption that the parking position is always going to be to the right of the vehicle. 4 ultrasonic sensors are used. 2 sensors (s2 and s1) are placed on the right front and rear edge and the other 2 (s3 and s0) are placed at the front and rear sides of the car as shown in the Fig 2.2.

The position of sensors s1 and s2 with respect toand described by the following equations.

S1 – (2.7)

S2 – (2.8)

The position of the sensors is used to determine the distance of the CLMR from an obstacle during simulation.

Parking Strategy

The parking strategy is developed intuitively as a human driver would do. The assumption is that a parking spot is somewhere to the right side of the vehicle to be parked (Holve and Protzel,1996). The vehicle would be moving parallel to the line of cars. The algorithm is as follows.

Search for an obstacle free area on the right side of the car. The distance should be greater than the minimum distance required to park the car. This could be set at twice the length of the car.

Once a sufficiently large parking spot is found, the car is reversed into the gap using a wall following algorithm. This algorithm aligns the car as parallel as possible in the gap without colliding with the rear wall.

The car is then driven forward to align itself in the centre of the gap.

Steps 2 and 3 can be repeated until the desired position is reached

Wall Following Controller (Shih-Jie and Tzuu-Hseng , 2002)

The heart of the parking strategy is a wall following controller.

Shih-Jie and Tzuu-Hseng (2002) proposes a fuzzy logic scheme as follows.

The variables shown in the figure represents the following

d1 – distance between the rear end of the CLMR and the wall

d2 – distance between the front end of the CLMR and the wall

Dist – is the desired distance between the wall and the CLMR

The objective of the controller is get d1 equal to d2 which is the desired distance from the wall Dist .

The scheme suggested is a 2 input one output scheme which controls the steering angle of the CLMR. Since the CLMR in this project is a three wheeled one the turning is done by varying the speeds of each wheel. The input variables to this control scheme are as follows if the CLMR is moving forward .

Input1 = d2 – Dist (2.9)

Input 2 = d2 – d1 (2.10)

and if the CLMR is moving backward

Input1 = d1 – Dist (2.11)

Input 2 = d1 – d2

The output of the controller is the amount by which the CLMR needs to turn in a given direction.

The fuzzy membership functions for Input1, Input2 and Steer are shown below

The membership functions are equally divided triangular membership functions.

The Rule Base for the wall following is shown in the table below. It is based on sliding mode control (Li et al, 2000)

The rules can be an represented linguistically as

If (Input1 is Positive Big) and (Input2 is Negative Big) then (steer is Zero)

If (Input1 is Positive Big) and (Input2 is Negative Small) then (steer is Positive Small) and so on

25. If (Input1 is Negative Big) and (Input2 is Positive Big) then (steer is Zero)

The defuzzication method used here is centre of gravity which is good for fine control

The final fuzzy logic entire controller can be summarized as follows

Summary

With the kinematic equations of the CLMR and the equations describing the sensor positions, a model can be constructed. With the parking strategies and a fuzzy logic controller now developed we shall discuss an efficient methodology in taking these designs into implementation.

Model Based Design Methodology

Overview

The advances in microprocessor technology in the early 70’s brought about a change in the way control systems were developed. From electrical relays built into ladder like networks and programmable logic controllers , controllers were being developed around a computer built with adequate hardware and software. Traditionally most of these control software development was based on paper designs and manual programming followed by verification activities such as code inspections and a unit/integration test (Guido Sandmann and Richard Thompson 2008).

Many of these activities lack tool automation, and are very time consuming. Thus they are error prone and time consuming. Lack of tool chain integration provides another opportunity for errors to be injected into the software that are often detected late and at high costs to the development process and so involve manual interaction. Model Based Design is software design methodology used to address these issues.

The steps involved are in MBD ,some of the commercially available tools and the tool chain choices for this project are discussed below

Model Based Design Process

The Model Based Design process can be divided into the following steps (NI Developer Zone, 2006).

System Definition

System definition involves the design process of a particular problem in consideration. It is mostly a conceptual design where in the problem and solutions are analyzed.

Modelling & Simulation

The step implies that the analyzed design is simulated using a graphical based simulation tool. MATLAB-SIMULINK, ASCET-MD etc are some examples of modelling tools. Designs here can be easily changed verified and re designed if necessary.

Rapid Prototyping

If the hardware of production controller is not available during the design phase a generalized hardware controller maybe used to test some of the simulations. This is the rapid prototyping phase.

Targeting

Targeting refers to getting the software code executing on the production hardware.

This stage involves the use of auto coders – tools that generate C code directly of graphical models, cross compilers and other tool chains that facilitate this.

Hardware in the loop Testing

Hardware in the Loop testing is used while developing control strategies for plant models like engines. It provides real time simulation of a real world plant model.

System Testing

This is the last step in the design process wherein the controller is tested on the real plant.

Summary

Of the stages in Model Based Design discussed above, only the most relevant one will be applied to this project. Beginning with system definition, modelling & simulation proceeding to targeting and finally onto system testing will be the stages followed in this project. MATLAB/SIMULINK, Stateflow, Virtual Reality Toolbox, Fuzzy Logic Blockset would be the tools used for modelling and simulation while Real Time Workshop Embedded Coder would be used during targeting. A detailed list of other tools will be dealt in the next chapter.

Introduction

Lego Mindstorms NXT is a robotics kit which consists of mechanical building blocks and electronic sensors. The highlight of this kit is the programmable brick called the NXT. The NXT is a 32bit ARM7 based microcontroller which allows motors and electronic sensors to be easily interfaced .Users can also run custom programs written via a GUI based programming language. The language provided by Lego, though very simple and intuitive to use does not exploit the true potential of NXT. Over the years, advanced users of the Lego Mindstorms have been successful in creating custom tools that apply every imaginable concept of embedded systems.

The following chapter discuss some of these software tools and hardware details relevant to this project. The most important part of this is to be able to design , simulate and test the robot using MATLAB Simulink.

Ultrasonic Sensor

The Lego Ultrasonic Sensor is shown below. It is mainly used for distance measurement. It has a range of 255 cm and is accurate to about +/- 3cm

One of the tasks of Model Based Design is to be able to program the NXT from Matlab – Simulink environment. The tools required to automate this process are discussed below

John Hansen’s Enhanced Firmware

Firmware in embedded systems term is referred to the basic software that is initially run on a hardware device. It performs basics factions like initialization of devices , integrity checks on memory and so on similar to BIOS on a standard PC.

The NXT brick , out of the box , has a standard firmware installed. This is designed to be used with the software provided. In order to write programs in C and realize the true potential of the NXT, a custom firmware has been written by John Hansen. This allows the NXT to be programmed by either using the provided software or by programming in C and using other tools which will be explained later.

The NeXTTool

The NeXTTool is a program that allows communication between the host PC and the NXT brick. It can do various tasks, but most importantly it is used to download custom programs onto the NXT.

The nxtOSEK

nxtOSEK (previously known as LEJOS OSEK) is an open source real time operating system for LEGO MINDSTORMS NXT. It contains device drivers from leJOS NXJ, an open source program that allows users to write Java programs on the NXT and a real time operating system source know as a TOPPERS OSEK. C or C++ can be used to write custom programs and compiled with the nxtOSEK using the GCC tool chain (Takashi Chikamasa, 2008)

The Embedded Coder Robot NXT Blockset is one of the key elements in applying Model Based Design Techniques to the Lego Mindstorms NXT. These blocks are custom Simulink blocks used in the controller side and serve as inputs and outputs to the real world. A word of caution. Custom blocks – especially hardware related blocks behave different behaviour in simulation and code generation . For e.g. an ultrasonic sensor block will not directly give sensor readings. The behaviour of the ultrasonic sensor will have to be separately emulated.

During code generation process, a function call to the ultrasonic device is placed where the block is used. This ensures the program using the block gets the value directly from the sensor. The details of the blocks used for this project are discussed below

There are two blocks that have to be for an ultrasonic sensor blocks consist of two blocks. The Ultrasonic Sensor Interface block and the Ultrasonic Sensor Read block.

Servo Motor Blocks

Fig 4.5 Servo Motor Blocks

The working of the Servo Motor is similar to the ultrasonic block as explained above.

The details of the block are given below.

Summary

Tools concerning with the implementation of a Matlab – Simulink design on a Lego Mindstorms NXT were explored here. However the most important of all is to simulate a working design. The next chapter discusses the implementation of the parallel parking strategy and the simulation results.

Parallel Parking Simulation

An integral part of Model Based Design is being able to simulate and get the desired results before implementation. The following chapter discusses the results of the controller developed in Chapter 2. For verification of the controller a Simulink model developed by Takashi Chikamasa, (2006) was used. The model was of a 3 wheeled robot with the motor dynamics included. A 3-D environment was provided using the Virtual Reality Toolbox. The environment however has been changed to suit the parallel parking problem.

Parallel Parking Strategy

The controller algorithm was developed in Simulink using Stateflow and the Fuzzy Logic Toolbox.

A 2-D plot of the trajectory path traversed by the CLMR is shown below.

Conclusion and Recommendations

The parallel parking strategy implemented did show good results. However, real life scenarios may be very different. For example, the controller depends on wall following. This implies there has to be 3 sides closed in a gap for the parking controller to work.

The development of the algorithm was with the intent of being able to execute it on a Lego Mindstorms Kit. However, there were some issues regarding this. The main being lack of a floating point unit on the NXT Brick. Though it is possible to execute floating point programs on the NXT, it causes severe performance issues.

The controller developed used the fuzzy logic blockset which inherently uses a lot of floating point variables. One method to overcome this draw back could be developing a fixed point version of the fuzzy logic blockset.

Other parking strategies involving classical control could be experimented with Lego Mindstorms. Complex tasks like path planning could be executed on a computer communicating with the NXT via Bluetooth and the control tasks could be implemented on the NXT using fixed point math.

However, with Model Based Design, being able to write programs in Simulink, simulate it and be able to execute this on the Lego Mindstorms opens a whole new dimension of what can be done ; limited only by our creativity!

Bibliography

C., Ho, C., Lin, S. & Li, T. (2005). Omni-Directional Vision-Based Parallel-Parking Control Design for Car-Like Mobile Robot. Proceedings of the 2005 IEEE International Conference on Mechatronics, 562-567.

De Luca, A., Oriolo, G., and Samson, C. 1998. Feedback control of a nonholonomic car-like robot. In Robot Motion Planning and Control, ed. J.-P. Laumond, 171-253. Berlin: Springer-Verlag

Dongbing, G. and H. Huosheng (2000). Wavelet neural network based predictive control for mobile robots. Systems, Man, and Cybernetics, 2000 IEEE International Conference on.

Galijasevic, A. M. a. Z. (2006). “Model-Based Design Shortens Development Time of Motor Control Applications.” Embedded Technology Journal.

Guido Sandmann and Richard Thompson (2008). Development of AUTOSAR Software Components within Model-Based Design. The Math Works, Inc.

Holve, R. & Protzel, P. (1996). Reverse Parking of a Model Car with Fuzzy Control. Proceedings of the 4th European Congress on Intelligent Techniques and Soft Computing – EUFIT’96, 2171-2175

Kuang-Yow, L., C. Chian-Song, et al. (1999). Parallel parking a car-like robot using fuzzy gain scheduling. Control Applications, 1999. Proceedings of the 1999 IEEE International Conference on.

Li, T.-H. S. and Shieh, M.-Y. (2000). Switching-type fuzzy sliding mode control of a cart-pole system, Mechatronics 10, 91-101.

NI Developer Zone (2006). Shortening the Embedded Design Cycle with Model-Based Design, Sep 6, 2006. Available from World Wide Web: http://zone.ni.com/devzone/cda/tut/p/id/4074

Pushkin Kachroo and Patricia Mellodge (2004). Mobile Robotic Car Design, McGraw-Hill,

Shih-Jie, C. and S. L. Tzuu-Hseng (2002). Design and Implementation of Fuzzy Parallel-Parking Control for a Car-Type Mobile Robot, Kluwer Academic Publishers. 34: 175-194.

Takashi Chikamasa, (2006). Embedded Coder Robot NXT Demo. Dec 2006. Available from World Wide Web: http://www.mathworks.com/matlabcentral/fileexchange/loadFile.do?objectId=13399

Takashi Chikamasa, (2008). What is nxtOSEK? June 2008. Available from World Wide Web: http://lejos-osek.sourceforge.net/whatislejososek.htm

Yanan, Z., E. G. Collins, et al. (2003). Design of genetic fuzzy parallel parking control systems. American Control Conference, 2003. Proceedings of the 2003.