Scientific Research

An Academic Publisher

Application of Union of Fuzzy Automata on Target Tracking ()

**Author(s)**Leave a comment

^{1}School of Computer and Communication Engineering, Zhengzhou University of Light Industry, Zhengzhou, China.

^{2}Engineering Training Center, Zhengzhou University of Light Industry, Zhengzhou, China.

^{3}School of Electrical and Information Engineering, Zhengzhou University of Light Industry, Zhengzhou, China.

KEYWORDS

Cite this paper

*Journal of Intelligent Learning Systems and Applications*,

**9**, 47-54. doi: 10.4236/jilsa.2017.94005.

1. Introduction

There exist a lot of ambiguous things in real world. Then better fuzzy signal processing is required to further obtain the various fuzzy automata, because it can more objectively reflect and process various ambiguous cases in reality.

The extraction algorithm of various fuzzy automata had been discussed by using the neural networks in detail [1] [2] . To the extracted FA, its stability had been also described [1] . For better solving some complicated problems in fuzzy information processing, some information fusions were performed well by FA [3] [4] [5] . At the same time, some controls of fuzzy automata had been applied in mechanical engineering [6] [7] . People used the neural networks to deduce the automata [8] [9] [10] [11] [12] . Although the fuzzy systems and the neural networks are quite different, their functional forms are often similar.

In this paper, we will discuss the application of the associated fuzzy automata on target tracking. The automata had a partition according to recognizing and accepting the language feature that was certain, uncertain and fuzzy. The automata were classified into the deterministic finite-state automaton (DFA), the non-deterministic finite-state automaton (NFA) and the fuzzy automaton (FA) [1] [2] [3] [4] [5] . Correspondingly, the fuzzy automata were also classified into the finite-state deterministic fuzzy automaton (FDFA), the finite non-deterministic fuzzy automaton (FNFA), the fuzzy finite-state automaton (FFA) and the fuzzy infinite?state automaton (FIA) [1] . The non-deterministic and fuzzy automata could be transformed into the deterministic automata by studying the equivalent relation of these automata and by using the neural networks.

2. Discussion of Relation of Several Fuzzy Automata

Several fuzzy automata (FA), i.e., FDFA, FNFA, FFA and FIA had been introduced, as well as the equivalence among several FA was discussed in previous works [1] [2] . Thus, the partial relation of several FA is introduced as follows.

Theorem 1. For a fuzzy language L, the following three conditions are equivalent:

1) L is acceptable by a FDFA.

2) L is acceptable by a FNFA.

3) L is acceptable by a FFA.

Proof: (1) Þ (2) In fact, because a FDFA ${M}_{1}=\left(Q,\sum ,\delta ,{q}_{0},G,V\right)$ is a special case of a FNFA, we conclude that (1) implies (2).

(2) Þ (3) Consider the assertion that (2) implies (3).

Let a fuzzy language $L=\left(\omega ,\mu \right)$ be accepted by a FNFA ${M}_{2}=\left(Q,\sum ,{\delta}_{N},{Q}_{0},G,V\right)$ , i.e., $\left(\omega ,\mu \right)\in L\left({M}_{2}\right)$ , then there exists ${\delta}_{N}\left({q}_{0i},\omega ,{\mu}_{ij}\right)\stackrel{*}{=}\left\{{q}_{ij}\right\}$ for some ${q}_{0i}\in {Q}_{0}$ and $\forall {q}_{ij}\in G$ , $\forall {\mu}_{ij}\in V$ , where $\omega \in {\sum}^{*},\mu =\underset{j}{{\displaystyle \vee}}{\mu}_{ij}$ .

Define a FFA ${M}_{3}=\left(Q,\sum ,F,{Q}_{0},G,V\right)$ and make ${F}_{\omega}\left({q}_{0i},{q}_{ij}\right)\stackrel{*}{=}{\mu}_{ij}$ , thus there is $\left(\omega ,\mu \right)\in L\left({M}_{3}\right)$ , where $\omega \in {\sum}^{*},\mu =\underset{j}{{\displaystyle \vee}}{\mu}_{ij}$ .

(3) Þ (1) Now show that a FDFA ${M}_{1}$ can accept a fuzzy language L recognized by a FFA ${M}_{3}=\left(Q,\sum ,F,P,G,V\right)$ .

Let a fuzzy language $\left(\omega ,\mu \right)$ be accepted by a FFA ${M}_{3}=\left(Q,\sum ,F,P,G,V\right)$ .

Assume

$V=\left\{{\theta}_{i}|0<{\theta}_{i}\le 1,{\theta}_{i}<{\theta}_{i+1},i=1,\cdots ,T\right\}$

${Q}_{i}=\left\{{p}_{j}|\exists {\theta}_{i}\in V,{\theta}_{i}\le F\left({p}_{j},\sigma ,{p}_{m}\right)<{\theta}_{i+1},\sigma \in {\sum}^{*},\forall {p}_{j}\in Q,\forall {p}_{m}\in G\right\},\text{\hspace{0.17em}}i=1,\cdots ,T$

Define the set of the states ${Q}^{\prime}={2}^{{Q}_{1}}\cup \cdots \cup {2}^{{Q}_{T}}$ , where ${2}^{{Q}_{i}}\left(i=1,\cdots ,T\right)$ denotes all subsets of the state ${Q}_{i}$ , and

${Q}_{0}=\left\{{p}_{j}\in P|\sigma \in {\sum}^{*},F\left({p}_{j},\sigma ,{p}_{m}\right)=1,\forall {p}_{m}\in G\right\}$

Now, define ${q}_{0}=\left[{Q}_{0}\right]$ and a FDFA

${M}_{1}=\left({Q}^{\prime},\sum ,\delta ,{q}_{0},{G}^{\prime},V\right)$

where ${q}_{0}=\left[{Q}_{0}\right]$ denotes that ${q}_{0}={p}_{j}$ if $F\left({p}_{j},\sigma ,{p}_{m}\right)=1$ for some ${p}_{j}\in P$ and $\forall {p}_{m}\in G$ , $\sigma \in {\sum}^{*}$ . And the meaning of $[\xb7]$ is similar in the following.

At the same time, define $\delta \left(q,\sigma ,\mu \right)=q\circ {F}_{\sigma}$ for $q\in {Q}^{\prime}$ , $\sigma \in \sum $ , $\mu \in V$ , and define ${G}^{\prime}\left(q\right)={\mu}_{q}\circ G\left({p}_{m}\right)$ if there exists ${F}_{\sigma}\left(q,{p}_{m}\right)=\mu \in V$ , where $\forall {p}_{m}\in G$ , ${\mu}_{q}$ is the membership degree in the state $q$ , and $q\circ {F}_{\sigma}$ denotes a new state with the membership degree ${\mu}_{q}\circ {F}_{\sigma}$ .

For $q\in {Q}^{\prime}$ , we prove the equality ${\delta}^{*}\left(q,{\sigma}_{1}\cdots {\sigma}_{n},\mu \right)=q\circ {F}_{{\sigma}_{1}}\circ \cdots \circ {F}_{{\sigma}_{n}}$ is true.

By induction method: for n = 0 (i.e., the empty symbol), there is ${\delta}^{*}\left(q,\epsilon ,\mu \right)=q$ .

Assume that the assertion holds true for n − 1, i.e., there exists the following equality:

${\delta}^{*}\left(q,{\sigma}_{1}\cdots {\sigma}_{n-1},\mu \right)=q\circ {F}_{{\sigma}_{1}}\circ {F}_{{\sigma}_{2}}\circ \cdots \circ {F}_{{\sigma}_{n-1}}$

According to the induction and $\delta \left(q,\sigma ,\mu \right)=q\circ {F}_{\sigma}$ defined, then, for n, there is

$\begin{array}{c}{\delta}^{*}\left(q,{\sigma}_{1}\cdots {\sigma}_{n},\mu \right)={\delta}^{*}\left(\delta \left(q,{\sigma}_{1},{\mu}_{1}\right),{\sigma}_{2}\cdots {\sigma}_{n},{\mu}_{2}\right)\\ =\delta \left(q,{\sigma}_{1},{\mu}_{1}\right)\circ {F}_{{\sigma}_{2}}\circ \cdots \circ {F}_{{\sigma}_{n}}=q\circ {F}_{{\sigma}_{1}}\circ {F}_{{\sigma}_{2}}\circ \cdots \circ {F}_{{\sigma}_{n}}\end{array}$ (1)

where $\mu ,{\mu}_{1},{\mu}_{2}\in V$ .

So the equality ${\delta}^{*}\left(q,{\sigma}_{1}\cdots {\sigma}_{n},\mu \right)=q\circ {F}_{{\sigma}_{1}}\circ \cdots \circ {F}_{{\sigma}_{n}}$ is true.

Finally, we prove: if $\left(\omega ,\mu \right)\in L\left({M}_{3}\right)$ , then $\left(\omega ,\mu \right)\in L\left({M}_{1}\right)$ .

Assume $\left(\omega ,\mu \right)\in L\left({M}_{3}\right)$ , then

${F}_{\omega}\left({p}_{0},{p}_{m}\right)\stackrel{*}{=}{\mu}_{m}\in V$ for $\forall {p}_{0}\in P,\forall {p}_{m}\in G$

where $\omega ={\sigma}_{1}\cdots {\sigma}_{n}\in {\sum}^{*}$

$\mu =\underset{m}{{\displaystyle \vee}}{\mu}_{m}=\left(L\left({M}_{3}\right)\right)\left({\sigma}_{1}\cdots {\sigma}_{n}\right)=P\left({p}_{0}\right)\circ {F}_{{\sigma}_{1}}\circ \cdots \circ {F}_{{\sigma}_{n}}\circ G\left({p}_{n}\right)$

where ${p}_{n}\in G$ .

On the other hand, there is

${\delta}^{*}\left({q}_{0},{\sigma}_{1}\cdots {\sigma}_{n},\mu \right)={\delta}^{*}\left(\delta \left({q}_{0},{\sigma}_{1},{\mu}_{1}\right),{\sigma}_{2}\cdots {\sigma}_{n},{\mu}_{2}\right)=\cdots ={\delta}^{*}\left({q}_{n-1},{\sigma}_{n},{\mu}_{n}\right)={q}_{n}$

where ${q}_{0}=\left[{Q}_{0}\right]$ , ${q}_{n}\in {G}^{\prime}$ , ${q}_{j}\in {Q}^{\prime}$ , $\mu ,{\mu}_{j},{\mu}_{n}\in V$ , $j=1,\cdots ,n-1$ .

At the same time, according to the above Formula (1) again, there is

${\delta}^{*}\left({q}_{0},{\sigma}_{1}\cdots {\sigma}_{n},\mu \right)={q}_{0}\circ {F}_{{\sigma}_{1}}\circ \cdots \circ {F}_{{\sigma}_{n}}$

Then

$\begin{array}{c}{\mu}^{\prime}=\left(L\left({M}_{1}\right)\right)\left({\sigma}_{1}\cdots {\sigma}_{n}\right)={G}^{\prime}\left({\delta}^{*}\left({q}_{0},{\sigma}_{1}\cdots {\sigma}_{n},\mu \right)\right)\\ ={G}^{\prime}\left({q}_{0}\circ {F}_{{\sigma}_{1}}\circ \cdots \circ {F}_{{\sigma}_{n}}\right)={\mu}_{{q}_{0}}\circ {F}_{{\sigma}_{1}}\circ \cdots \circ {F}_{{\sigma}_{n}}\circ G\left({p}_{n}\right)\end{array}$

where ${q}_{0}=\left[{Q}_{0}\right]$ , ${p}_{n}\in G$ .

Since ${\mu}_{{q}_{0}}=P\left({p}_{0}\right)$ , then ${\mu}^{\prime}=\mu $ . Therefore, there is $\left(\omega ,\mu \right)\in L\left({M}_{1}\right)$ . Thus, we have shown that (3) implies (1).

Q.E.D.

Moreover, other several FA are also equivalent, such as, a language L is accepted by a NFA, iff, there exists a DFA that accepts the language L, i.e. L = L(DFA) = L(NFA) [1] ; a fuzzy language is accepted by some FDFA if it is accepted by some L-nested systems of DFA [3] ; the FFA is equally powerful as L-nested systems of NFA [4] .

3. Union of Fuzzy Automata

The algorithm consists of four parts:

1) Construct the associated network

Transform FA into a neural network with N recurrent neurons that computes the degree of membership $\mu $ of the state of FA for inputting the arbitrary string. Make the degree of membership in the state ${q}_{{i}^{\prime}}$ label $0<{\mu}_{{i}^{\prime}}\le 1$ . Let N recurrent neurons perform the union of FA in the first stage, and choose the

sigmoid discriminative function $g\left(x\right)=\frac{1}{1+{\text{e}}^{-x}}$ to compute the degree of

membership. Let M non-recurrent output neurons perform again the union of FA in the second stage, which compute the union value of FA. For each ${a}_{k}\in \sum $ , construct an input vector $\left(0,\cdots ,0,{I}_{k-}{}_{1},1,{I}_{k+}{}_{1},0,\cdots ,0\right)$ , where $\sum $ is a finite set of the input symbols. Thus, we perform the union algorithm of FA by using the networks.

2) Decision-making Model on Target Tracking

For
$\forall i\in S$ , the i ^{th} FA for target tracking is labeled a fuzzy set
${\underset{\u02dc}{F}}^{i}$ , i.e.,

${\underset{\u02dc}{F}}^{i}=\left\{\left({o}_{1},{f}_{i1}\right),\left({o}_{2},{f}_{i2}\right),\cdots ,\left({o}_{M},{f}_{iM}\right)\right\}$ (2)

where
${o}_{p}\left(p\in U\right)$ is the target that corresponds to the serial number p,
${f}_{ip}$ is the degree of membership that the i ^{th} FA judges the identified target belonging to the p^{th} target type, and
$0\le {f}_{ip}\le 1$ . For the target tracking results that are denoted by a fuzzy set, we may use a fuzzy distribution to describe it; S and U are the index sets of FA and target, respectively.

A fuzzy distribution ${\Xi}_{i}$ that corresponds to ${\underset{\u02dc}{F}}^{i}$ can be expressed as:

${\Xi}_{i}={\displaystyle \underset{p\in U}{\sum}{f}_{ip}/{o}_{p}},\text{\hspace{0.17em}}\text{\hspace{0.17em}}\forall i\in S$ (3)

Assume K is a variable in U. $\forall i\in S$ , for a given proposition “K is ${\underset{\u02dc}{F}}^{i}$ ”, a fuzzy distribution that corresponds to K will be derived as follows:

${\Xi}_{K}^{i}\left(p\right)={f}_{ip},\text{\hspace{0.17em}}\text{\hspace{0.17em}}\forall i\in S,\text{\hspace{0.17em}}p\in U$ (4)

It denotes that the possibility of the value of K is the degree of membership that p belongs to the fuzzy set ${\underset{\u02dc}{F}}^{i}$ .

For the usual hard judgement, i.e., a single type (e.g. ${p}_{1}$ type) is chosen as the solution of an identified target type, which it can be regarded as a special case of the above Formula (3).

3) Union of several FA

Let ${f}_{ip}\left(t\right)$ and ${\Xi}_{i}\left(t\right)$ denote the fuzzy degree of membership and fuzzy distribution that the identified target belongs to the p type by measuring of the FA i at time t respectively. ${f}_{ip}^{\left(l\right)}$ denotes the fuzzy degree of membership that the identified target belongs to the p type by the cumulative union of the FA i until time l. ${\Xi}_{i}^{l}$ denotes the fuzzy distribution of the identified target by the cumulative union of the FA i until time l, where $l=1,2,\cdots ,t$ , i.e.,

${\Xi}_{i}\left(t\right)={\displaystyle \underset{p\in U}{\sum}{f}_{ip}\left(t\right)/{o}_{p}}$ (5)

To integrate the fuzzy distribution that is obtained by cumulative union at time $t-1$ and the fuzzy distribution that is obtained by measuring at time t, we can obtain the fuzzy distribution ${\Xi}_{i}^{t}$ of the cumulative union of the FA i for target tracking until time t, and the distribution is

${\Xi}_{i}^{t}={\displaystyle \underset{p\in U}{\sum}{f}_{ip}^{\left(t\right)}/{o}_{p}}$ (6)

where ${f}_{ip}^{\left(t\right)}=H\left[{f}_{ip}^{\left(t-1\right)},{f}_{ip}\left(t\right)\right]$ . H is a fuzzy integration function, and H is usually obtained by the Formula (7) below.

Assume ${M}_{ip}\left(t\right)={\left({f}_{ip}\left(1\right),{f}_{ip}\left(2\right),\cdots ,{f}_{ip}\left(t\right)\right)}^{\prime}$ . Here, the fuzzy integration functions H may be selected as follows:

$H\left({M}_{ip}\left(t\right)\right)={\left(\frac{1}{t}{\displaystyle \underset{l=1}{\overset{t}{\sum}}{f}_{ip}^{q}\left(l\right)}\right)}^{\frac{1}{q}},\text{\hspace{0.17em}}q>0$ (7)

4) Initialization

Before processing a new signal, initialize the FA network first:

${S}^{0}=\left({S}_{0}^{0},{S}_{1}^{0},\cdots ,{S}_{N-1}^{0}\right)=\left({S}_{0}^{0},1,0,\cdots ,0\right)$

let $0<{S}_{0}^{0}<1$ be arbitrary.

5) Performance of union

The training of FA network and some calculation are mainly performed in the first stage, i.e., after processing a signal with a certain length, the output ${S}_{{i}^{\prime}}^{t}$ of FA network is the degree of membership ${\mu}_{{i}^{\prime}}$ of the states of FA at the time t.

The second stage is an output layer that performs the union of FA. The output values ${O}_{p-1}$ are determined by the output values of FA network.

4. Application of Associated Fuzzy Automata on Target Tracking

In positioning and navigation systems, the information provided by each sensor is generally inaccurate, ambiguous, incomplete or even contradictory, which includes a lot of uncertainty. In order to achieve better target tracking and identification, a target tracking department has to rely on uncertain information for computing and reasoning. The logical computation such as fuzzy automata tracking is a kind of better fuzzy logic processing method. This processing method can handle some unknown uncertainty information, since it is to make use of a fuzzy membership degree, fuzzy function and network learning method rather than using an exact computation that is difficult to obtain.

Because some influences of some distribution situations of the targets and their movement laws, measurement error of the sensor, some processing methods and other factors, to judge whether or not the track from two local nodes is corresponding to the same target is usually very difficult. Particularly, it is more difficult under more cross, more bifurcate, maneuvering track occasions or the dense target environment. When a system includes a sensor calibration, conversion, delay errors and larger navigation, the single FA tracking method looks not ability, so it needs to seek other methods, thus, the union of FA method is proposed.

In addition, because some targets usually locate in different complex environment, it is difficult to use only a kind of fuzzy automata to track them, thus, it also needs to develop a method that can better track the targets under multi-target interference cases. In here, a method on associated fuzzy automata is proposed for better target tracking in a multi-target case. Thus, it will be a theoretic base for application of any automata. These researches developed in this paper can lead to the development of the theories and the applications of fuzzy automata hierarchy in various fields.

To facilitate the discussion, here consider only two fuzzy automata. One group of targets that the number of targets is 100 in simulation is used. Simulate the targets movement with the intentionally or unintentionally maneuvering and speed change with the process noise in a two-dimensional flat. The initial positions of targets obey the normal distribution in the moving region. The initial velocity obeys the uniform distribution 10 m/s - 1000 m/s. Let the targets make rectilinear motion at a uniform velocity and take a turn to the left or the right motion at a uniform velocity, and the deviation turning rates be ${\omega}_{2}=-{6}^{\circ}$ and ${\omega}_{3}={6}^{\circ}$ . The sizes of deviation radius ${r}_{1}$ and ${r}_{2}$ of moving region are ${r}_{1}=100\text{\hspace{0.17em}}\text{km}$ and ${r}_{2}=130\text{\hspace{0.17em}}\text{km}$ , respectively. Based on a union of FA method, the target tracking is performed under a medium-density target environment with 100 targets.

In the union of FA, the target tracking is performed based on the Formula (7) of fuzzy integration function. The sampling is 160 times in simulation and sampling rate T is 1 second. The simulation results for the union of FA are shown in Figure 1(a) and Figure 1(b) respectively. From Figure 1, the tracking effect of union of FA is better than that of single FA on multiple-target tracking. When $q=1$ , the tracking curve of union of FA is basically same as the true curve of the target orbit, but the single FA for target tracking is not so good, which is shown in Figure 1(b). It signifies that the information on the target tracking can be almost completely utilized by the union of FA than using the single FA information.

5. Conclusion

For fully utilizing the information on fuzzy signal processing, this paper presents several FA and discusses their relation. According to the relation of FA discussed, the union of these automata is discussed, and also the application of the

(a)(b)

Figure 1. Comparison between union of FA and single FA on target tracking. (a) (q = 1/2) x-axis; (b) (q = 1) x-axis.

associated FA is given on target tracking. Then, it will be a theoretic base for extraction and application of any automata on the image processing and pattern recognition etc. Finally, some problems and development trends on the fuzzy automata will be studied for future researches.

Acknowledgements

This work is supported by National 973 Program (No. 613237), Henan Province Outstanding Youth on Science and Technology Innovation (No. 164100510017), National Natural Science Foundation of China (No. 61502435); Key Science and Technology Program of Henan Province Education Department (No. 14A520034); Doctorate Research Funding and project of key young teachers of ZZULI (No. 2013BSJJ041, 13300093), respectively.

Conflicts of Interest

The authors declare no conflicts of interest.

[1] |
Wu, Q.E., Wang, T., Huang, Y.X. and Li, J.S. (2006) Theory Research on a New Type Fuzzy Automaton. Fuzzy Systems and Knowledge Discovery, 4223, 1-10.
https://doi.org/10.1007/11881599_1 |

[2] | Wu, Q.E., Pang, X.M. and Han, Z.Y. (2011) Fuzzy Automata System with Application to Target Recognition Based on Image Processing. Computers & Mathematics with Applications, 61, 1267-1277. https://doi.org/10.1016/j.camwa.2010.08.101 |

[3] | Shamsizadeh, M. (2016) Intuitionistic General Fuzzy Automata. Soft Computing, 20, 3505-3519. https://doi.org/10.1007/s00500-015-1969-x |

[4] | Karthikeyan, V. (2015) Directable Fuzzy Automata. International Journal of Computer Applications, 125, 1-4. https://doi.org/10.5120/ijca2015906119 |

[5] | Cao, Y.Z. and Ezawa, Y. (2012) Nondeterministic Fuzzy Automata. Information Sciences, 191, 86-97. https://doi.org/10.1016/j.ins.2011.12.024 |

[6] | Micic, I., Jancic, Z., Ignjatovic, J. and Ciric, M. (2015) Determinization of Fuzzy Automata by Means of the Degrees of Language Inclusion. IEEE Transactions on Fuzzy Systems, 23, 2144-2153. https://doi.org/10.1109/TFUZZ.2015.2404348 |

[7] |
Garhwal, S. and Jiwari, R. (2016) Conversion of Fuzzy Automata into Fuzzy Regular Expressions Using Transitive Closure. Journal of Intelligent and Fuzzy Systems, 30, 3123-3129. https://doi.org/10.3233/IFS-152038 |

[8] | Radim, B. (2002) Determinism and Fuzzy Automata. Information Sciences, 143, 205-209. https://doi.org/10.1016/S0020-0255(02)00192-5 |

[9] |
Mockor, J. (1999) Fuzzy and Non-Deterministic Automata. Soft Computing, 3, 221-226. https://doi.org/10.1007/s005000050091 |

[10] |
Blanco, A., Delgado, M. and Pegalajar, M.C. (2001) Fuzzy Automaton Induction Using Neural Network. International Journal of Approximate Reasoning, 27, 1-26.
https://doi.org/10.1016/S0888-613X(01)00028-7 |

[11] | Li, Y.M. and Wang, Q. (2014) The Universal Fuzzy Automaton. Fuzzy Sets and Systems, 249, 27-48. https://doi.org/10.1016/j.fss.2013.08.002 |

[12] | Pan, H.Y., Li, Y.M., Cao, Y.Z. and Li, P. (2017) Nondeterministic Fuzzy Automata with Membership Values in Complete Residuated Lattices. International Journal of Approximate Reasoning, 82, 22-38. https://doi.org/10.1016/j.ijar.2016.11.020 |

Copyright © 2020 by authors and Scientific Research Publishing Inc.

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.